BÀI TOÁN ĐẾM – PHẦN 3 ppsx

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ó cỡ n

b

(để đơn giản giả sử rằng n chia hết cho b;