Tìm ước chung lớn nhất Viết chương trình nhập vào hai số tự nhiên a, b không đồng thời

Đào Đình Đại Ngày: 13-06-2023 Lớp 10

1.7 K

Với giải Câu F43 trang 32 SBT Tin học lớp 10 Cánh diều chi tiết trong Bài 8, 9 (Cánh diều): Câu lệnh lặp thực hành câu lệnh lặp giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập trong SBT Tin học 10. Mời các bạn đón xem:

Giải SBT Tin học lớp 10 Bài 8, 9 (Cánh diều): Câu lệnh lặp thực hành câu lệnh lặp

Câu F43 trang 32 SBT Tin 10: Tìm ước chung lớn nhất

Viết chương trình nhập vào hai số tự nhiên a, b không đồng thời bằng 0 và in ra ước số chung lớn nhất của a, b.

Trả lời:

Ước chung lớn nhất (GCD — Greatest Common Divisor) là một khái niệm quan trọng trong số học và nhiều lĩnh vực khác. Mục đích của bài toán là tìm số nguyên Z lớn nhất đồng thời là ước số của cả a và b.

Một cách tiếp cận đơn giản là khi b > 0 ta có thể thử tất cả các giá trị số nguyên d = b, b - 1, b - 2, ..., 1 và dừng lại ngay khi gặp số nguyên d là ước số của cả a và b. Còn tất nhiên khi b == 0, ước số chung lớn nhất của a và b chính là a

Phương pháp này tuy đúng nhưng có hiệu suất rất kém. Một phương pháp khác hiệu quả hơn là thuật toán Euclid (được nhà toán học người Hy Lạp đưa ra vào khoảng thế kỉ III trước công nguyên). Thuật toán Euclid như sau:

Lặp cho đến khi b ≠ 0

+ Tính r là số dư của phép chia a cho b.

+ Thay cặp số (a, b) bởi cặp số (b, r).

- Kết thúc: Giá trị a sau vòng lặp là ước chung lớn nhất của hai số ban đầu. Tham khảo chương trình sau: