//
you're reading...
01 - Chủ đề thuật toán, Dùng cho cấp THCS, Dùng cho cấp THPT

Thuật toán Euclid và bài toán ước chung lớn nhất

Trong lý thuyết số, thuật toán Euclid là một thuật toán để xác định ước số chung lớn nhất (GCD – Greatest Common Divisor) của 2 phần tử thuộc vùng Euclid (ví dụ: các số nguyên). Điều quan trọng chủ yếu là nó không yêu cầu việc phân tích thành thừa số 2 số nguyên, và nó cũng mang ý nghĩa lớn vì nó là một trong những thuật toán cổ nhất được biết đến, từ thời Hy Lạp cổ đại.

Lịch sử của thuật toán Euclid

Thuật toán Euclid là một trong những thuật toán cổ nhất được biết đến, từ khi nó xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid khởi đầu đã trình bày rõ ràng vấn đề về phương diện hình học, như vấn đề tìm ra một thước đo chung cho độ dài hai đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Tuy nhiên, thuật toán đã hầu như không được phát hiện ra bởi Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được biết đến bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên). Đúng là quá sớm !

Thuật toán nguyên bản

Thuật toán nguyên bản được mô tả bởi Euclid đã giải quyết vấn đề về phương diện hình học, sử dụng lặp phép trừ.

1
2
3
4
5
6
7
8
9

int UCLN(int a, int b)

{
while(b!=0)
{
if(a>b) a-=b;
else b-=a;
}
return a;
}

Chú ý rằng trong khi b có thể là 0 thì a không thể là 0, nếu không nó sẽ trở thành vòng lặp vô hạn.

Mô tả thuật toán với phép chia
Cho 2 số tự nhiên a và b, không đồng thời bằng 0: kiểm tra nếu b bằng 0, thì a là ước chung lớn nhất (UCLN). Nếu không, lặp lại xử lý sử dụng b và phần còn lại sau khi lấy a chia cho b. Phần còn lại sau khi chia a cho b thường được viết là a mod b.

Các thuật toán này có thể sử dụng trong bất kì hoàn cảnh nào khi còn phần dư. Điều này bao gồm các nhóm đa thức như nhóm số nguyên Gauxơ. Thuật toán không chỉ áp dụng cho số tự nhiên mà còn áp dụng cho nhiều trường hợp tổng quát khác (số nguyên Gaussian, đa thức, … )

Sử dụng đệ quy

Sử dụng đệ quy, thuật toán có thể phát biểu như sau:1

1
2
3
4
5

int UCLN(int a, int b)
{
if(b==0) return a;
else return UCLN(b,a%b);
}

Sử dụng vòng lặp

1
2
3
4
5
6
7
8
9
10

int UCLN(int a, int b)

{
while(b!=0)
{
int t=b;
b=a%b;
a=t;
}
return a;
}

Thuật toán tìm Bội chung nhỏ nhất và Ước chung lớn của 2 số trong Pascal:

Cách 1: Dưới đây là thuật toán tìm UCLN bằng cách trừ đi nhau, được trình bày trong SGK tin học 10.

var x,y,UCLN,BCNN:integer;
begin
readln(x,y);
BCNN:=x*y;
While x<>y do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;
write(UCLN,’ ‘,BCNN);

end.

Cách 2: Thuật toán Euclide: Ngoài cách tìm UCLN như trên. Các bạn có thể sử dụng cách chia lấy dư (mod), chương trình sẽ tối ưu do phải thực hiện ít phép tính hơn.

Ý tưởng: UCLN của 2 số x, y cũng là UCLN của 2 số y và x mod y, vậy ta sẽ đổi x là y, y là x mod y cho đến khi y bằng 0. Khi đó UCLN là x.

var x,y,UCLN,BCNN,t:integer;
begin
readln(x,y);
BCNN:=x*y;
t:= y mod x;
While t <> 0 do
Begin
t:= x MOD y;
x:= y;
y:= t;
End;
ucln:=x;
BCNN:=BCNN div UCLN;
write(UCLN,’ ‘,BCNN);

end.

Cách 3: Tìm UCLN bằng cách dùng đệ quy: Đệ quy được hiểu đơn giản là sự gọi nhiều lần chương trình con trong chương trình. Thực sự, đối với bài toán đơn giản, không ai sử dụng đệ quy vì sẽ làm phức tạp vấn đề và làm chương trình trở nên rắc rối, phải thực hiện nhiều phép tính hơn. Tuy nhiên, nếu bắt buộc phải dùng đệ quy, các bạn có thể tham khảo cách làm dưới đây:

function ucln(x,y:integer):integer;
begin
if x = y then
ucln:=x
else if x > y then
ucln:=ucln(x mod y,y)
else
ucln:=ucln(x, y mod x);
end;
var x,y:integer;
begin
readln(x,y);
write(‘Ước chung lớn nhất là: ‘, UCLN(x,y), ‘ Bội chung nhỏ nhất là: ‘, (x*y) div UCLN(x,y));
end.

Thuật toán Euclid mở rộng

Bằng cách theo dõi thương tìm được trong suốt thuật toán, ta có thể xác định các số nguyên p và q với ap+bq=gcd(a,b). Điều này được biết đến như là thuật toán Euclid mở rộng.

Một ví dụ

Giả sử tính toán UCLN của 1071 và 1029 là 21.

Với thuật toán đệ quy sau:

Với thuật toán lặp:
Nhận xét rằng a

b trong mỗi lần gọi. Nếu ban đầu, b > a, không có vấn đề gì, trước hết ta chỉ cần hoán đổi 2 giá trị cho nhau, sau đó các bước hoàn toàn tương tự.

Chứng minh

Giả thiết a và b là các số tự nhiên mà UCLN phải xác định. Bây giờ, giả thiết b > 0, và phần dư của phép chia a cho b là r. Do đó a = qb + r với q là thương của phép chia.

Bất kì phép chia thông thường nào của a và b cũng cho một số dư r. Để thấy sự đúng đắn đó, ta coi r có thể được viết là r = a – qb. Bây giờ nếu có một ước chung d của a và b, như vậy a = sd và b = td, khi đó r = (s-qt)d, ta có thể thấy rằng r chia hết cho d.

Những phân tích trên là đúng cho bất kì số chia d nào, vì thế, UCLN của a và b cũng là UCLN của b và r. Do đó nếu ta tiếp tục tìm UCLN với các số b và r ta sẽ có kết quả

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Tám 2015
H B T N S B C
« Th1   Th9 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 209,568 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: