Giải SGK Chuyên đề Tin học 11 Bài 7. Thiết kế thuật toán theo kĩ thuật chia để trị

1. Để tính luỹ thừa của một số a với một số nguyên không âm n, em có thể sử dụng thuật toán đệ quy như sau:

2. Để tìm một bạn lớp có chiều cao gần với 1,7 m nhất, em có thể sử dụng một thuật toán tìm kiếm đơn giản như thuật toán tìm kiếm tuần tự hoặc tìm kiếm nhị phân. Tuy nhiên, để áp dụng thuật toán tìm kiếm nhị phân, em cần phải sắp xếp danh sách chiều cao của các bạn lớp trước.

Ví dụ, nếu danh sách chiều cao của các bạn lớp được lưu trữ trong một mảng a, em có thể sử dụng thuật toán tìm kiếm tuần tự như sau:

Vì ${a}^{n}=a\times {a}^{n-1}$

1. Tính bình thường:

- Để tính ${2}^{11}$ bằng phương pháp bình thường, ta sẽ lặp lại việc nhân 2 với chính nó 21 lần (tức là 2*** 2***...*2, lặp lại 21 lần).

Tuy nhiên, việc tính toán này sẽ rất tốn thời gian và không hiệu quả khi giá trị của số mũ lớn hơn.

2. Chia để trị:

Bước 1: Chia bài toán thành các bài toán con

Chia 11 cho 2, ta được kết quả là 5 và số dư là 1: 11 = 2 * 5 + 1

Bước 2: Giải quyết các bài toán con

Ta cần tính 2^5 để giải quyết bài toán con này. Tiếp tục áp dụng phương pháp chia để trị trên bài toán con này:

Chia 5 cho 2, ta được kết quả là 2 và số dư là 1: 5 = 2 * 2 + 1

Tiếp tục giải bài toán con tiếp theo:

Chia 2 cho 2, ta được kết quả là 1 và số dư là 0: 2 = 2 * 1 + 0

Bây giờ ta đã giải quyết được tất cả các bài toán con.

Bước 3: Tính toán kết quả

Từ bài toán con cuối cùng, ta có được: 2^1 = 2

Từ bài toán con thứ hai, ta có được: 2^2 = (2^1)^2 = 2^2 = 4

Từ bài toán con đầu tiên, ta có được: 2^5 = (2^2)^2 * 2 = 4^2 * 2 = 16 * 2 = 32

Vậy: 2^11 = 2^5 * 2^5 * 2 = 32 * 32 * 2 = 1024

Do đó, 2^11 = 1024.

Ta có công thức tổng quát sau: T(n) = T(n/2) + O(1) và T(0) = 1, O(1) =1

Với n = 21, T(21) = T(21/2) + 1 = T(10) + 1

= (T(5) + 1) + 1 =((T(2) + 1) + 1)+ 1 = T(1) + 1 + 3

= T(0) + 1 + 4 = 1 + 5 = 6

- Để tìm ra các phần tử của dãy gần K nhất chúng ta cần thêm các tính toán phụ tại dòng 10

- Chương trình trên hoàn toàn tương tự thuật toán tìm kiếm tuần tự, chỉ có một vòng lặp tại dòng 9, do đó có thời gian chạy O(n).

- Chúng ta thiết kế thuật toán thứ hai dựa trên tìm kiếm nhị phân. Hàm đệ quy chính sẽ được thiết kế theo dạng valueClosest(A, left, right, K) sẽ tìm phần tử gần K nhất trong khoảng chỉ số từ left đến right. Trước tiên có một số nhận xét cho các trường hợp đặc biệt.
+ Nếu n = 1, dãy A chỉ có một phần tử, khi đó hàm sẽ trả lại phần tử duy nhất của A.
+ Nếu n = 2, dãy A có hai phần tử thì cần so sánh phần tử nào gần K hơn chính
là phần tử cần tìm.

Chương trình cuối cùng có dạng như sau