Top Ad unit 728 × 90

Latest news

recent

Ước chung lớn nhất (The Greatest Common Divisor (GCD))

Ước chung lớn nhất (The Greatest Common Divisor (GCD) hay Greatest Common Factor (GCF)) của 2 số nguyên là số lớn nhất mà cả hai số đó có thể chia hết.
Ví dụ số lớn nhất có thể được chia hết bởi cả 20 và 16 là 4 (tuy cả 16 và 20 đều có thể chia hết cho những số lớn hơn nhưng không có số nào lớn hơn 4 mà cả hai đều chia hết – ví dụ 8 là ước số của 16, nhưng không phải là ước (factor) của 20) trong trường hợp này 4 được gọi là Ước chung lớn nhất của 16 và 20. Có một vài phương pháp để tìm ra Ước chung lớn nhất của 2 số nguyên tuy nhiên ở đây xin được giới thiệu một phương pháp đơn giản gọi là giải thuật Euclid (Euclid’s Algorithm).
Cho hai số nguyên a và b, các bước thuật tóan được giải thích như sau:

Bước 1: Loại bỏ dấu “–“ của 2 số a và b.
Bước 2: Chúng ta sẽ giải thích một chút về một số thuật ngữ quan trọng: khi bạn chia 32 cho 5 thì
•    32 là số bị chia (dividend)
•    5 là số chia (divisor)
•    6 là số thương (quotient)
•    2 là phần dư (remainder hay modulo)
 

Bước 3: Giữa a và b chọn ra số lớn hơn dùng làm số bị chia (dividend), số nhỏ hơn làm số chia (divisor) rối tính thành phần remainder trong công thức (dividend) = (divisor) * (quotient) + (remainder).
Bước 4: Nếu phần dư (remainder) khác 0 thì Sử dụng số chia (divisor) củ làm số bị chia (dividend) và phần dư làm số chia mới rồi tính lại giá trị remainder.
Bước 5: Lặp lại bước 4 cho tới khi phần dư bằng 0.
Bước 6: Số chia cuối cùng là ước số chung lớn nhất của a và b.
Bước 7: Ví dụ kiểm chứng: Tìm GCD của  108 và 30


Mã chương trình bằng C:


hay cũng có thể thay vì dùng mod thì dùng phép trừ:


Binh Nguyen - Bioz
Ước chung lớn nhất (The Greatest Common Divisor (GCD)) Reviewed by Bioz Nguyen on 10:32:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.