Đang chuẩn bị liên kết để tải về tài liệu:
THUẬT TOÁN – PHẦN 3

Thuật toán Euclide: Phương pháp tính ước chung lớn nhất của hai số bằng cách dùng phân tích các số nguyên đó ra thừa số nguyên tố là không hiệu quả. Lý do là ở chỗ thời gian phải tiêu tốn cho sự phân tích đó. Dưới đây là phương pháp hiệu quả hơn để tìm ước số chung lớn nhất, gọi là thuật toán Euclide. Thuật toán này đã biết từ thời cổ đại. Nó mang tên nhà toán học cổ Hy lạp Euclide, người đã mô tả thuật toán này trong cuốn sách “Những yếu tố” nổi tiếng. | THUẬT TOÁN - PHẦN 3 SỐ NGUYÊN VÀ THUẬT TOÁN 1.4.1. Thuật toán Euclide Phương pháp tính ước chung lớn nhất của hai số bằng cách dùng phân tích các số nguyên đó ra thừa số nguyên tố là không hiệu quả. Lý do là ở chỗ thời gian phải tiêu tốn cho sự phân tích đó. Dưới đây là phương pháp hiệu quả hơn để tìm ước số chung lớn nhất gọi là thuật toán Euclide. Thuật toán này đã biết từ thời cổ đại. Nó mang tên nhà toán học cổ Hy lạp Euclide người đã mô tả thuật toán này trong cuốn sách Những yếu tố nổi tiếng của ông. Thuật toán Euclide dựa vào 2 mệnh đề sau đây. Mệnh đề 1 Thuật toán chia Cho a và b là hai số nguyên và b 0. Khi đó tồn tại duy nhất hai số nguyên q và r sao cho a bq r 0 r b . Trong đẳng thức trên b được gọi là số chia a được gọi là số bị chia q được gọi là thương số và r được gọi là số dư. Khi b là nguyên dương ta ký hiệu số dư r trong phép chia a cho b là a mod b. Mệnh đề 2 Cho a bq r trong đó a b q r là các số nguyên. Khi đó UCLN a b UCLN b r . Ở đây UCLN a b để chỉ ước chung lớn nhất của a và b. Giả sử a và b là hai số nguyên dương với a b. Đặt r0 a và r1 b. Bằng cách áp dụng liên tiếp thuật toán chia ta tìm được r0 Ĩ1Q1 r2 0 r2 n n r2q2 r3 0 r3 r2 rn-2 rn-1Ợn-1 rn 0 rn ĩn-1 rn-1 rnqn . Cuối cùng số dư 0 sẽ xuất hiện trong dãy các phép chia liên tiếp vì dãy các số dư a r0 r1 r2 . 0 không thể chứa quá a số hạng được. Hơn nữa từ Mệnh đề 2 ở trên ta suy ra UCLN a b UCLN r0 r1 UCLNỘj r2 . UCLN rn-2 rn-1 UCLN rn-1 rn rn. Do đó ước chung lớn nhất là số dư khác không cuối cùng trong dãy các phép chia. Thí dụ 6 Dùng thuật toán Euclide tìm UCLN 414 662 . 662 441.1 248 414 248.1 166 248 166.1 82 166 82.2 2 82 2.41. Do đó UCLN 414 662 2. Thuật toán Euclide được viết dưới dạng giả mã như sau procedure ƯCLN a b positive integers X a y b while y 0 begin r X mod y X y y r end UCLN a b là x Trong thuật toán trên các giá trị ban đầu của x và y tương ứng là a và b. Ở mỗi giai đoạn của thủ tục x được thay bằng y và y được thay bằng x mod y. Quá trình này được lặp lại chừng nào