dàn âm thanh hội trường, âm thanh lớp học, âm thanh phòng họp, loa trợ giảng

Thuật toán tìm UCLN của hai số nguyên dương

Thuật toán tìm UCLN của hai số nguyên dương

UCLN (ước chung lớn nhất) của 2 số là gì?

Ước chung lớn nhất (UCLN, tiếng Anh là GCD – Greatest Common Divisor) của 2 số nguyên dương ab là số nguyên lớn nhất d thỏa mãn tính chất cả ab đều chia hết cho d.

Ví dụ, UCLN của 103555 là số nguyên lớn nhất mà cả 1035 đều chia hết cho 5.

Thuật toán tìm UCLN của hai số nguyên dương

Có nhiều thuật toán tìm UCLN của hai số nguyên, bạn có thể tham khảo thêm ở Wikipedia. Dưới đây, chúng tôi giới thiệu thuật toán tìm UCLN của hai số nguyên giải thuật Euclid. Cơ sở của giải thuật Euclid tìm UCLN của hai số nguyên ab dựa trên tính chất sau.

Giả sử a >= b thì khi chia a cho b ta được thương q và số dư r, tức là

a = b*q + r

Khi đó:

  • Nếu r = 0 thì UCLN(a,b) = b
  • Nếu r >0 thì UCLN(a,b) = UCLN(b,r)

Tìm UCLN của hai số nguyên bằng phép chia

Áp dụng giải thuật Euclid để tính ƯCLN của a = 1071 và b = 462. Đầu tiên, ta chia 1071 cho 462 thì được thương là 2 và số dư là 147:

1071 = 2 × 462 + 147.

Do đó, UCLN(1071,462) = UCLN(462, 147). Tiếp tục chia 462 cho 147 thì được thương bằng 3 và số dư là 21:

462 = 3 × 147 + 21.

Do đó, UCLN(462,147) = UCLN(147, 21). Tiếp tục chia 147 cho 21 thì được thương là 7 và số dư là 0:

147 = 7 × 21 + 0.

Do đó, UCLN(1071,462)=21.

Giả mã của thuật toán này như sau:

function gcd(a, b)
    while b ≠ 0
        t:= b
        b:= a mod b
        a:= t
    return a

Một cách ngắn gọn, để tìm UCLN của hai số xy có thể xem trong hình sau:

Thuật toán tìm UCLN của hai số nguyên dương 1

Đối với chương trình viết bằng Dart, bạn có thể tham khảo code tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-15.html

Nếu sử dụng hàm, hoặc đệ quy, mời bạn tham khảo trong bài…

Tìm UCLN của hai số nguyên bằng phép trừ

Tìm UCLN của hai số nguyên bằng cách phép trừ. Ở đây, chúng ta sử dụng không sử dụng phép chia mà sử dụng tính chất sau nếu ab cùng chia hết cho d thì hiệu a-b cũng chia hết cho d.

Ví dụ, xét hai số nguyên 15 và 9 thì UCLN(15,9) = UCLN(15-9,9).

Giả mã của thuật toán này như sau:

function gcd(a, b)
    while a ≠ b 
        if a > b
            a:= a − b
        else
            b:= b − a
    return a

Bạn có thể tham khảo mã nguồn tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-15.html

Xem thêm: Thuật toán quay lui và minh họa


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *