Thuật toán Euclid

Euclid là một thuật toán giúp tìm ra Ước số chung lớn nhất của hai số. Euclid đã viết thuật toán này trong cuốn Elements, được biết đến từ khoảng 300 năm trước Công nguyên.

Ước chung là một số mà cả hai số kia đều chia hết cho nó, không dư. Ước chung lớn nhất là số bị chia lớn nhất có thể. Ví dụ: ước chung của 10 và 8 là: 1, 2, 4. Trong đó 4 là ước chung lớn nhất.

Cách tính:

– Bước 1: Lấy số lớn chia cho số nhỏ.

– Bước 2: Lấy số bị chia, chia cho số dư.

– Bước 3: Lặp lại bước 2 cho tới khi nào không còn số dư thì thôi. (vòng lặp)

Ví dụ: Tính ước số chung của 287 và 91:

Bước 1: Lấy số lớn hơn chia cho số còn lại.

287 = 91 * 3 + 14

Giải thích:

Lấy 287 / 91 = 3.15

Lấy 3 * 91 = 273

Lấy 287 – 273 = 14

Bước 2: Lấy số bị chia, chia tiếp cho số dư.

91 = 14 * 6 + 7

Bước 3: Lấy số bị chia, chia tiếp cho số dư.

14 = 7 * 2

Tới đây là hết, không còn số dư. Vậy là ta có ước số chung là 7 cho cả 2 số 287 và 91:

287 / 7 = 41 (không dư)

91 / 7 = 13 (không dư)

Ví dụ trong java:

Tính ước số chung lớn nhất của hai số nguyên dương x và y như sau:

– Nếu x = 0, thì kết quả là y. Nếu không thì lấy x chia y, ra z.

– Sau đó lặp lại vòng tính với hai số y và z. Tiếp tục như vậy cho tới khi nào kết quả cuối cùng bằng 0 thì thôi.

public static int gcd(int x, int y)
{
   if (x == 0) return y;
   int z = x % y;
   return gcd(y, z);
}

Author
Recent Posts

Trần Thành

Tôi là nhà sáng lập Kênh Tin Học - Một người luôn có niềm đam mê với mọi thứ liên quan đến công nghệ và đổi mới.

1 thought on “Thuật toán Euclid”

Leave a Comment Cancel reply