Câu hỏi:
13/07/2024 1,207
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.
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.
Câu hỏi trong đề:
Giải SBT Tin 10 Bài 8, 9: Câu lệnh lặp có đáp án !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Ướ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:
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
In ra tổng các số chia hết cho 3 hoặc chia hết cho 5
Với n nhập từ bàn phím, viết chương trình đưa ra màn hình tổng các số tự nhiên nhỏ hơn n và chia hết cho 3 hoặc chia hết cho 5.
In ra tổng các số chia hết cho 3 hoặc chia hết cho 5
Với n nhập từ bàn phím, viết chương trình đưa ra màn hình tổng các số tự nhiên nhỏ hơn n và chia hết cho 3 hoặc chia hết cho 5.
Xem đáp án »
13/07/2024
41,316
Câu 2:
Tổng chữ số
Viết chương trình nhập vào số nguyên dương n và in ra tổng các chữ số trong biểu diễn thập phân của n.
Tổng chữ số
Viết chương trình nhập vào số nguyên dương n và in ra tổng các chữ số trong biểu diễn thập phân của n.
Xem đáp án »
13/07/2024
7,865
Câu 3:
In ra các số lẻ
Viết chương trình nhập vào số nguyên n và in ra các số nguyên dương lẻ không lớn hơn n theo thứ tự tăng dần.
In ra các số lẻ
Viết chương trình nhập vào số nguyên n và in ra các số nguyên dương lẻ không lớn hơn n theo thứ tự tăng dần.
Xem đáp án »
13/07/2024
7,497
Câu 4:
In ra các số chẵn
Viết chương trình nhập vào số nguyên n và in ra các số nguyên dương chẵn không lớn hơn n theo thứ tự giảm dần.
In ra các số chẵn
Viết chương trình nhập vào số nguyên n và in ra các số nguyên dương chẵn không lớn hơn n theo thứ tự giảm dần.
Xem đáp án »
13/07/2024
6,771
Câu 5:
Tính giai thừa
Viết chương trình nhập vào một số nguyên dương n và in ra giá trị giai thừa của n.
Tính giai thừa
Viết chương trình nhập vào một số nguyên dương n và in ra giá trị giai thừa của n.
Xem đáp án »
13/07/2024
3,188
Câu 6:
Liệt kê ước số
Viết chương trình nhập vào một số nguyên dương n và in ra tất cả các ước số của n.
Liệt kê ước số
Viết chương trình nhập vào một số nguyên dương n và in ra tất cả các ước số của n.
Xem đáp án »
13/07/2024
3,041
Câu 7:
In ra tổng các số chỉ chia hết cho 3 hoặc 5
Viết chương trình đưa ra màn hình tổng các số nguyên chỉ chia hết cho 3 hoặc 5 nhưng không đồng thời chia hết cho cả 3 và 5 trong phạm vi các số nguyên từ m đến n-1. Ngừng tính tổng khi nhận được tổng lớn hơn hoặc bằng b cho trước. Các số nguyên m, n, b được nhập vào từ bàn phím với m < n.
In ra tổng các số chỉ chia hết cho 3 hoặc 5
Viết chương trình đưa ra màn hình tổng các số nguyên chỉ chia hết cho 3 hoặc 5 nhưng không đồng thời chia hết cho cả 3 và 5 trong phạm vi các số nguyên từ m đến n-1. Ngừng tính tổng khi nhận được tổng lớn hơn hoặc bằng b cho trước. Các số nguyên m, n, b được nhập vào từ bàn phím với m < n.
Xem đáp án »
13/07/2024
2,824
Bình luận
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học Kết nối tri thức Bài 16: Ngôn ngữ lập trình bậc cao và Python có đáp án
-
15 câu Trắc nghiệm Tin học Kết nối tri thức Bài 17: Biến và lệnh gán có đáp án
-
15 câu Trắc nghiệm Tin học Kết nối tri thức Bài 12: Phần mềm thiết kế đồ họa có đáp án
-
15 câu Trắc nghiệm Tin học Kết nối tri thức Bài 13: Bổ sung các đối tượng đồ họa có đáp án
-
15 câu Trắc nghiệm Tin học Kết nối tri thức Bài 11: Ứng xử trên môi trường số. Nghĩa vụ tôn trọng bản quyền có đáp án
-
15 câu Trắc nghiệm Tin học Kết nối tri thức Bài 18: Các lệnh vào ra đơn giản có đáp án
-
15 câu trắc nghiệm Tin học Kết nối tri thức Bài 1: Thông tin và xử lí thông tin có đáp án
-
15 câu Trắc nghiệm Tin học Kết nối tri thức Bài 14: Làm việc với đối tượng đường và văn bản có đáp án
về câu hỏi!