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

Trang trước Trang sau

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

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

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:

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

Xem thêm các bài giải sách bài tập Tin học lớp 10 sách Cánh diều hay, chi tiết khác:

Trang trước Trang sau
Giải bài tập lớp 10 Cánh diều khác