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
Giải sách bài tập Tin học 10 Bài 8, 9: Câu lệnh lặp. Thực hành câu lệnh lặp
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
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:
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:
Tủ sách VIETJACK shopee lớp 10-11 cho học sinh và giáo viên (cả 3 bộ sách):
Săn shopee siêu SALE :
- Sổ lò xo Art of Nature Thiên Long màu xinh xỉu
- Biti's ra mẫu mới xinh lắm
- Tsubaki 199k/3 chai
- L'Oreal mua 1 tặng 3
Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.
Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:Nếu thấy hay, hãy động viên và chia sẻ nhé! Các bình luận không phù hợp với nội quy bình luận trang web sẽ bị cấm bình luận vĩnh viễn.
- Soạn văn lớp 10 (hay nhất) - CD
- Giải Toán lớp 10 - CD
- Giải Tiếng Anh lớp 10 - CD
- Giải Vật lí lớp 10 - CD
- Giải Hóa học lớp 10 - CD
- Giải Sinh học lớp 10 - CD
- Giải Giáo dục Kinh tế và Pháp luật lớp 10 - CD
- Giải Địa lí lớp 10 - CD
- Giải Lịch sử lớp 10 - CD
- Giải Giáo dục quốc phòng lớp 10 - CD
- Giải Tin học lớp 10 - CD