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ới Giải Câu F43 trang 32 SBT Tin học 10 Cánh diều trong Bài 8, 9: Câu lệnh lặp. Thực hành câu lệnh lặp Sách bài tập Tin học 10 Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập trong SBT Tin học 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

Câu F43 trang 32 SBT Tin học 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.

Lời giả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

(ảnh 10)

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:

(ảnh 11)