Đang chuẩn bị liên kết để tải về tài liệu:
BÀI TOÁN ĐẾM – PHẦN 3

Nhiều thuật toán đệ quy chia bài toán với các thông tin vào đã cho thành một hay nhiều bài toán nhỏ hơn. Sự phân chia này được áp dụng liên tiếp cho tới khi có thể tìm được lời giải của bài toán nhỏ một cách dễ dàng. Chẳng hạn, ta tiến hành việc tìm kiếm nhị phân bằng cách rút gọn việc tìm kiếm một phần tử trong một danh sách tới việc tìm phần tử đó trong một danh sách có độ dài giảm đi một nửa. Ta rút gọn liên tiếp như vậy cho tới. | BÀI TOÁN ĐẾM - PHẦN 3 QUAN HỆ CHIA ĐỂ TRỊ. 2.6.1. Mở đầu Nhiều thuật toán đệ quy chia bài toán với các thông tin vào đã cho thành một hay nhiều bài toán nhỏ hơn. Sự phân chia này được áp dụng liên tiếp cho tới khi có thể tìm được lời giải của bài toán nhỏ một cách dễ dàng. Chẳng hạn ta tiến hành việc tìm kiếm nhị phân bằng cách rút gọn việc tìm kiếm một phần tử trong một danh sách tới việc tìm phần tử đó trong một danh sách có độ dài giảm đi một nửa. Ta rút gọn liên tiếp như vậy cho tới khi còn lại một phần tử. Một ví dụ khác là thủ tục nhân các số nguyên. Thủ tục này rút gọn bài toán nhân hai số nguyên tới ba phép nhân hai số nguyên với số bit giảm đi một nửa. Phép rút gọn này được dùng liên tiếp cho tới khi nhận được các số nguyên có một bit. Các thủ tục này gọi là các thuật toán chia để trị. 2.6.2. Hệ thức chia để trị Giả sử rằng một thuật toán phân chia một bài toán cỡ n thành a bài toán nhỏ trong đó mỗi bài toán nhỏ có n cỡ -7 b để đơn giản giả sử rằng n chia hết cho b .í . Tn w n i trong thực tê các bài toán nhỏ thường có cỡ b hoặc b Giả sử răng tông các phép toán thêm vào khi thực hiện phân chia bài toán cỡ n thành các bài toán có cỡ nhỏ hơn là g n . Khi đó nêu f n là số các phép toán cần thiêt để giải bài toán đã cho thì f thỏa mãn hệ thức truy hồi sau n f n af b g n Hệ thức này có tên là hệ thức truy hồi chia để trị. Thí dụ 15 1 Thuật toán tìm kiêm nhị phân đưa bài toán tìm kiêm cỡ n về bài toán tìm kiêm phần tử này trong dãy tìm kiêm cỡ n 2 khi n chẵn. Khi thực hiện việc rút gọn cần hai phép so sánh. Vì thê nêu f n là số phép so sánh cần phải làm khi tìm kiêm một phần tử trong danh sách tìm kiêm cỡ n ta có f n f n 2 2 nêu n là số chẵn. 2 Có các thuật toán hiệu quả hơn thuật toán thông thường để nhân hai số nguyên. Ở đây ta sẽ có một trong các thuật toán như vậy. Đó là thuật toán phân nhanh có dùng kỹ thuật chia để trị. Trước tiên ta phân chia mỗi một trong hai số nguyên 2n bit thành hai khối mỗi khối n bit. Sau đó phép nhân hai số nguyên 2n bit ban đầu .