Câu hỏi:

13/07/2024 1,632 Lưu

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.

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Ủ ĐỀ

Lời giải

 Bài này có thể có nhiều cách viết vòng lặp.

Cách 1: Sử dụng vòng lặp while: Khởi tạo x = 1 là số nguyên dương lẻ nhỏ nhất, cho đến khi xn ta in ra x sau đó tăng x lên 2 đơn vị. Tham khảo chương trình sau:

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

Cách 2: Sử dụng vòng lặp for: Dãy số lẻ cần in ra là 0 × 2 + 1, 1 × 2 + 1, 2 × 2 + 1, ..., k × 2+ 1, trong đó k là giá trị số nguyên lớn nhất thoả mãn: k × 2 + 1≤ n, tức là k=[n12] . Tham khảo chương trình sau:

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

Cách 3: Sử dụng vòng lặp for nhưng sửa lại khai báo range (..) để mỗi bước giá trị số in ra được tăng lên 2 đơn vị. Tham khảo chương trình sau:

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

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP