Thuật toán phục hồi số hữu tỉ

Nghiên cứu trình bày bài toán này liên quan đến một số ứng dụng của thuật toán Euclid và lý thuyết về phân số chuỗi trong số học. Bài viết này sẽ lần lượt tìm hiểu các lý thuyết liên quan, lời giải của bài toán trên, và thử làm các bài tập tương tự. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Thuật toán phục hồi số hữu tỉTạp chí online của cộng đồng những người yêu Toán THUẬT TOÁN PHỤC HỒI SỐ HỮU TỈ Nguyễn Hùng Sơn (University of Warsaw) 1. Mở đầu Cách đây không lâu tôi có đố các bạn trẻ một bài toán đố nhỏ, nhưng mang tính thực tế, như sau: Một vị giáo sư toán-tin rất cẩn thận nhưng đãng trí. Cách đây vài hôm ngân hàng gửi ông một bức thư thông báo mật khẩu của thẻ tín dụng. Mật khẩu là một số có 6 chữ số: abcdef. Ông không muốn giữ lại bức thư vì sợ nó có thể lọt vào tay kẻ gian. Vì vậy ông đã dùng 1 chiếc máy tính xách tay đơn giản (gồm 4 phép tính +.−, ×, ÷ và 10 chữ số) để tính tỉ số abc ÷ def. Ông đã nhận được kết quả gần đúng là 0, 195323246 và ghi nhớ lại lên một tờ giấy. Làm thế nào để vị giáo sư có thể tìm lại được mật khẩu trong thời gian ngắn nhất nếu ông chỉ có trong tay chiếc máy tính xách tay đơn giản và mật khẩu là gì? Thực ra bài toán này liên quan đến một số ứng dụng của thuật toán Euclid và lý thuyết về phân số chuỗi trong số học. Sau đây chúng ta sẽ lần lượt tìm hiểu các lý thuyết liên quan, lời giải của bài toán trên, và thử làm các bài tập tương tự. 2. Thuật toán Euclid Đây là một trong các phương pháp tìm ước số chung lớn nhất ƯSCLN(a, b) của hai số tự nhiên. Khoảng 300 năm trước Công Nguyên, Euclid – nhà toán học cổ người Hy lạp – đã mô tả thuật toán này trong cuốn ”cơ sở” (Elements). 21 Ý tưởng chính của thuật toán này là: Nếu k, r là hai số nguyên sao cho a = kb + r thì:Tạp chí online của cộng đồng những người yêu Toán ƯSCLN(a, b) = ƯSCLN(r, b). Trong thuật toán Euclid, ta sẽ chọn k là phần nguyên của phép chia a cho b (k = ba/bc), còn r là phần dư khi chia a cho b (r = a − ba/bc · b). Thuật toán này được mô tả dạng biểu đồ ở Hình 3.1. Ví dụ nếu muốn tìm ƯSCLN của 2 số 324 và 918 thì các bước của thuật toán sẽ như sau: STT a b ba/bc r = a mod b d 1. 324 918 0 576 2. 918 324 2 270 3. 324 270 1 54 4. 270 54 5 0 5. 54 0 54 Nhªp 2 sè tü nhi¶n a, b Kiºm tra b=0 b 6= 0? b 6= 0 r := a mod b a := b ...