THUẬT TOÁN ƠCLIT TÌM ƯCLN, BCNN
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (521.97 KB, 10 trang )
Thuật toán
Thuật toán
Euclide
Euclide
Giới thiệu
Giới thiệu
Điều quan trọng chủ yếu là nó không yêu cầu việc phân tích
thành các thừa số nguyên tố.
Hơn thế, nó còn mang ý nghĩa lớn vì đây 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
Chương trình toán THCS có phần tính ƯSCLN & BSCNN
nhưng HS ít biết đến thuật toán này.
Trong lý thuyết số học , thuật
Trong lý thuyết số học , thuật
toán Euclid là một thuật toán cổ
toán Euclid là một thuật toán cổ
để xác định ước số chung lớn
để xác định ước số chung lớn
nhất (ƯSCLNN-tắt tiếng Việt;
nhất (ƯSCLNN-tắt tiếng Việt;
hoặc tiếng Anh GCD – Greatest
hoặc tiếng Anh GCD – Greatest
Common Divisor) của 2 phần tử
Common Divisor) của 2 phần tử
thuộc vùng Euclid (ví dụ: các số
thuộc vùng Euclid (ví dụ: các số
nguyên).
nguyên).
Lịch sử của thuật toán
Lịch sử của thuật toán
Thuật toán Euclid là một thuật toán cổ
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 thuật toán này được biết đến sóm hơ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), nhưng
Euclide vẫn là người có công lớn nhất nên
thuật toán được mang tên ông.
Aristotle
Aristotle
Euclid
Euclid
Tính ước số chung lớn nhất
Tính ước số chung lớn nhất
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ế)
Ta thấy 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ả)
ta có: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).
Cuối cùng
Cuối cùng
ƯSCLN(287,91)
ƯSCLN(287,91)
= 7
= 7
Tính
Tính
BSCNN nhanh nhất
BSCNN nhanh nhất
Để việc giải toán về BCNN & UCLN được nhanh, Nếu
biết áp dụng “Thuật toán Euclid” :
hai số nguyên a, b có BCNN là [ a,b] và ƯCLN là (a,b) thì
(Công thức trên giúp tính nhanh , không phải làm theo cách
phân tích ra thừa số nguyên tố)
Bổ đề Euclide
Giả sử
a = bq + r, với a, b, q, r là các số nguyên,
ta có
Từ bổ đề trên, người ta đã chứng minh thuật toán
Chứng minh
Chứng minh
Giả thiết a và b là các số tự nhiên mà UCLN phải xác định.
Nếu b > 0, và phần dư của phép chia a cho b là r.
Thì 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. Khi giá trị tuyệt đối
của r nhỏ hơn b, ta sẽ tiến tới rn+1 = 0 sau nhiều bước.
Minh họa về thuật toán lặp:
Minh họa về thuật toán lặp:
Giả sử tính toán
UCLN của 1071 và
1029 là 21;
Các bước lặp như biểu
bên
Lưu ý :
a, b trong mỗi lần gọi.
Nếu b > a, thì ta chỉ
cần hoán đổi 2 giá
trị cho nhau, sau đó
các bước hoàn toàn
tương tự.
Phạm vi của thuật toán Euclid
Phạm vi của thuật toán Euclid
Ví dụ, Tính UCLN của
a = x
4
+ 8x
3
+ 12x
2
+ 17x + 6 = (x
2
+ 7x + 3)(x
2
+ x + 2)
b =x
4
− 4x
3
+ 4x
2
− 3x + 14 = (x
2
− 5x + 7)(x
2
+ x + 2) và
Thuật toán Euclid có thể áp
Thuật toán Euclid có thể áp
dụng cho các nhóm số khác,
dụng cho các nhóm số khác,
không chỉ cho số tự nhiên.
không chỉ cho số tự nhiên.
Trường hợp cá biệt là các số
Trường hợp cá biệt là các số
nguyên Gaussian và các
nguyên Gaussian và các
nhóm đa thức.
nhóm đa thức.
Xét nhóm đa thức với hệ số
Xét nhóm đa thức với hệ số
hữu tỷ. Nhóm này, phép chia
hữu tỷ. Nhóm này, phép chia
với phần dư được sử dụng
với phần dư được sử dụng
phép chia đa thức.
phép chia đa thức.
Thay lời kết
Thay lời kết
Thuật toán Euclitd không phải mới ( có từ 300 năm TCN ), nhưng sẽ có
ích cho HS nếu phải giải những bài toán liên quan ƯSC & BSC.
Với HS muốn tìm hiểu sâu hơn (Đưa vào ngôn ngữ lập trình, sử dung đệ
quy…) xin xem thêm phần “Giải thuật Euclitd mở rộng ”
GT & biên soạn Phạm Huy Hoạt 1-3-2012
