Ướ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ó t...
Ướ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)
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
hay quá, bài này giúp tôi ôn lại kiến thức hồi xưa đã lãng quên.
ReplyDeletePs: trong cái bài viết có từ "kỉ thuật" hình như đúng chính tả phải là "kỹ thuật" xin tác giả vui lòng kiểm tra lại.
tui đã kiểm tra nhưng trong bài ko có từ "kỉ thuật", tuy nhiên thì từ này lại có ở nhiều nơi khác :), tui đã sửa lại những chổ tui có thể thấy. Cảm ơn bạn, tiếng Việt của tui có vấn đề về chính tả, tui sẽ cố gắng khắc phục.
ReplyDeleteco phuong phap nao tim uoc chung lon nhat nua khong Bioz says?
ReplyDelete