THUẬT TOÁN ƠCLIT TÌM ƯCLN, BCNN - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.ppt) (10 trang)

Trang chủ

Giáo án - Bài giảng

Toán học

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 EuclideEuclide Giới thiệuGiớ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.AristotleAristotle EuclidEuclid Tính ước số chung lớn nhấtTính ước số chung lớn nhấtVí 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ùngCuối cùng ƯSCLN(287,91)ƯSCLN(287,91) = 7 = 7 Tính Tính BSCNN nhanh nhấtBSCNN 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ổ đề EuclideGiả 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 minhChứ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 EuclidPhạm vi của thuật toán EuclidVí dụ, Tính UCLN củaa = x4 + 8x3 + 12x2 + 17x + 6 = (x2 + 7x + 3)(x2 + x + 2)b =x4 − 4x3 + 4x2 − 3x + 14 = (x2 − 5x + 7)(x2 + 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ếtThay 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

Tài liệu liên quan

Cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất
- 4
- 6
- 138
Thuật toán google tìm kiếm website
- 4
- 338
- 0
Thuật toán Dijkstra - Tìm đường đi ngắn nhất trong đồ thị
- 3
- 12
- 154
bai thuyet trinh ly thuyet so ve Thuat toan Oclit
- 7
- 1
- 11
chuyên đề thuật toán ơclit
- 2
- 845
- 5
TÌM UCLN & BCNN CỦA 2 SỐ pot
- 3
- 359
- 0
Thuật toán Prim – Tìm cây khung có trọng số nhỏ nhất ppsx
- 8
- 1
- 17
nghiên cứu cấu trúc và hệ thống điều khiển bộ biến đổi bán dẫn công suất cho hệ pin mặt trời có thuật toán dò tìm điểm công suất lớn
- 86
- 930
- 3
THUẬT TOÁN ƠCLIT TÌM ƯCLN, BCNN
- 10
- 11
- 72
ỨNG DỤNG LUẬT KẾT HỢP VÀ THUẬT TOÁN APRIORI TÌM CÁC NHÂN TỐ ẢNH HƯỞNG PRODUCTIVTYQUALITY CỦA SOFTWARE MAINTENANCE PROJECT
- 14
- 953
- 3