TAILIEUCHUNG - 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! | 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 . 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 d a Xu t d STOP b r Hình Thuật toán Euclid để tìm ước số chung lớn nhất của hai số tự nhiên a b. 22 3. Liên phân số Tạp chí online

• Toán học
• Thuật toán phục hồi số hữu tỉ
• Hồi số hữu tỉ
• Thuật toán Euclid
• Phân số chuỗi
• Phục hồi số hữu tỉ