Thuat toan oclit

Ví dụ
Tính ước số chung lớn nhất của 91 và 287.
Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:
287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)
Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:
91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)
Cuối cùng ta có: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).
[sửa]Bổ đề
Giả sử a = bq + r, với a, b, q, r là các số nguyên, ta có:


[sửa]Mã giải =
[sửa]Chương trình đệ quy
procedure USCLN(a, b : positive integers)
Begin
if a mod b = 0 then USCLN := b
else USCLN(b; a mod b);
End
[sửa]Chương trình dùng vòng lặp
procedure USCLN(a, b : positive integers)
Begin
x := a
y := b
while y ≠ 0
begin
r := x mod y
x := y
y := r
end{x la USCLN cần tìm}




Chuyên đề :  Thuật toán Ơclit 1. Thuật toán Ơclit Để tìm USCLN của hai số a và b ta có thể dùng cách chia liên tiếp gọi là thuật toán Ơclit như sau: Bước 1: Lấy a chia cho b Nếu a b thì ƯSCLN (a, b) =b Nếu a b (dư r) thì làm tiếp bước 2 Bước 2: Lấy b chia cho số dư r Nếu b r thì ƯSCLN (a, b) =r Nếu b r (dư r1) thì làm tiếp bước 3 Bước 3: Lấy r chia cho số dư r1 Nếu r r1 thì ƯSCLN (a, b) =r1 Nếu r r1 (dư r2) thì làm tiếp bước 4 Bước 4: Lấy r1 chia cho số dư r2 Nếu r1 r2 thì ƯSCLN (a, b) =r2 Nếu r1 r2 (dư r3) thì làm tiếp tục như trên cho đến khi số dư bằng 0 Số dư cuối cùng khác 0 trong dãy phép chia liên tiếp như trên là ƯSCLN (a, b) 2. Thí dụ: Thí dụ 1:  Tìm ƯSCLN (450; 198) Giải Bước 1: Lấy 450 chia cho 198 450 : 198 = 2 (dư 54)  Bước 2: Lấy 198 chia cho số dư 54 198 : 54 = 3 (dư 36)  Bước 3: Lấy 54 chia cho số dư 36 54 : 36 = 1 (dư 18) Số dư cuối cùng khác 0 Bước 4: Lấy 36 chia cho số dư 18 36 : 18 = 2 (dư 0) Số dư cuối cùng bằng 0 ƯSCLN (450; 198) =18 . Thí dụ 2: Tìm hai số tự nhiên biết rằng ƯSCLN của là 15 và phép chia liên tiếp của thuật toán Ơclit các thương lần lượt là 2; 15; 9 .  Giải Gọi hai số tự nhiên phải tìm là a, b (a>b)  Theo đầu bài ta có 3 phép chia liên tiếp nên số dư trong phép chia thứ hai cho ta ƯSCLN (a, b)  Ta có các phép chia sau: a = 2b + r (1)  b = 2r + r1 (trong đó r1=15) (2)  r = r1.9 (3)  Vậy r = 15.9 = 135  b = 3.135 +15 = 420 a = 2.420 + 135 = 975 Hai số cần tìm là 975 và 420 . 

Có lẽ nhiều bạn trong diễn đàn vẫn chưa biết đến thuật toán Euclide tìm ƯCLN. Mình cũng mới biết đến nó thôi. Hôm nay mình quyết định Post một bài để chia sẻ với các bạn về thuật toán này. Ta xét 2 trường hợp sau: a) Nếu b là ước của a thì (a, b) = b b) Nếu b không là ước của a, giả sử a = bp + c thì (a, b) = (b, c). Thuật toán: a = bp + r1; 0 < r1 < b