Câu hỏi:

13/07/2024 1,258

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.

Sale Tết giảm 50% 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).

20 đề Toán 20 đề Văn Các môn khác

Quảng cáo

Trả lời:

verified
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ả ab.

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ả ab. Còn tất nhiên khi b == 0, ước số chung lớn nhất của ab 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  (ảnh 1)

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  (ảnh 2)

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.

Xem đáp án » 13/07/2024 46,278

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.

Xem đáp án » 13/07/2024 8,438

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.

Xem đáp án » 13/07/2024 7,892

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.

Xem đáp án » 13/07/2024 7,694

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.

Xem đáp án » 13/07/2024 3,526

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.

Xem đáp án » 13/07/2024 3,219

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.

Xem đáp án » 13/07/2024 3,046

Bình luận


Bình luận