Giải chi tiết chuyên đề tin học định hướng Khoa học máy tính 11 Kết nối mới bài 7 Thiết kế bài toán theo kĩ thuật chia để trị

Khởi động

Trong bài học này em sẽ thiết kế lời giải cho hai bài toán sau:

1. Bài toán tính luỹ thừa exp(a, n) = aⁿ với a là số bất kì (khác 0), n là số nguyên không âm, ở đây a được hiểu là tích của n lần giá trị a: aⁿ = a × a × ... × a (n lần).

2. Ban giám hiệu nhà trường cần tìm một bạn lớp em có chiều cao đúng bằng 1,7 m hoặc gần với chiều cao đó nhất để tham gia tập đội hình thể thao.

Với hai bài toán trên em sẽ thực hiện như thế nào?

Hướng dẫn trả lời:

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:

1. Bài toán tính lũy thừa

Câu hỏi 1. Hãy thiết lập thuật toán và chương trình tính luỹ thừa aⁿ a với a là số bất kì khác 0, n là số nguyên không âm.

Hướng dẫn trả lời:

Đề tính luỹ thừa a”, bạn có thể sử dụng kỹ thuật đệ quy. Dưới đây là một cách thiết lập thuật toán và cài đặt chương trình tính luỹ thừa a” bằng kỹ thuật đệ quy:

1. Nếu n bằng 0, trả về 1 vì a° = I.

2. Nếu n bằng I, trả về a vì a'= a.

3. Nếu n lẻ, tính giá trị của a” “bằng cách gọi đệ quy với tham số a và n//2, sau đó trả về kết quả nhân với chính nó: a”= a^n//2 *a^n//2*a,

4. Nếu n chãn, tính giá trị của a^n//2 bằng cách gọi đệ quy với tham số a và n//2, sau đó trả về kết quả nhân với chính nó: a”= a^n//2* a^n//2

Câu hỏi 1. Mô tả các bước tính bằng tay phép tính luỹ thừa 2¹¹ theo hai chương trình trên. Cách nào nhanh hơn?

Hướng dẫn trả lời:

Vì an = an∗a^{n-1}

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

- Để tính 211 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.

Câu hỏi 2. Phép tính a¹¹ sẽ cần dùng bao nhiêu phép nhân?

Hướng dẫn trả lời:

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

2. Bài toán tìm kiếm nhị phân mở rộng

Câu hỏi. Xây dựng thuật toán cho bài toán sau: Cho trước dãy các số đã được sắp xếp tăng dần. Với giá trị K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất.

Hướng dẫn trả lời:

- Để 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 1. Sử dụng tìm kiểm tuần tự

1. def valueClosest(A,K):
2.  n = len(A)
3. if K <= A[0}:
4. return A[0]
5. elif K ›= A[n - 1]:
6. return A[n - 1]
7. else:
8. value = A[0]
9. for 1 in range(n):
10. if abs(A[i] - K) <‹ abs(value - K):
11. value = A[i]
12. return value

- 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

Chương trình 2. Sử dụng tim kiếm nhị phân

1. def valueClosest(A, left,right,K):
2. if left == right:
3. return A[left]
4. elif left == right - 1:
5. if abs(A[left] - K) < abs(A[right] - K):
6. return A[left]
7. else:
8. return A[right]
9. else:
10. mid = (left + right)//2
11. if A[mid] == K:
12. return A[mid]

Câu hỏi 1. Hãy giải thích kĩ hơn chương trình 2 trên tại các dòng 2 và 4.

Hướng dẫn trả lời:

Giải thích kĩ hơn chương trình 2 trên tại các dòng 2 và 4:

- Dòng 2: nếu left == right tức là mảng có 1 phần tử

- Dòng 4: Nếu left == right - 1 tức là mảng có 2 phần tử

Câu hỏi 2. Nêu những điểm khác biệt của chương trình trên với chương trình tìm kiếm nhị phân đã biết

Hướng dẫn trả lời:

Điểm khác biệt:

1. Mục đích sử dụng:

- Chương trình tìm kiếm nhị phân: Sử dụng để tìm kiếm một phần tử duy nhất trong một dãy số đã được sắp xếp.

- Chương trình tìm ra các phần tử của dãy gần K nhất: Sử dụng để tìm các phần tử trong dãy số gần giá trị K nhất.

2. Phương pháp tìm kiếm:

- Chương trình tìm kiếm nhị phân: Sử dụng phương pháp chia để trị và tìm kiếm trên nửa dãy con.

- Chương trình tìm ra các phần tử của dãy gần K nhất: Sử dụng phương pháp tìm kiếm tuyến tính để tìm các phần tử gần giá trị K nhất.

4. Thời gian thực thi:

- Chương trình tìm kiếm nhị phân có thời gian thực thi nhanh hơn chương trình tìm ra các phần tử của dãy gần K nhất

Luyện tập

Câu hỏi 1. Viết chương trình không đệ quy cho bài toán tìm kiếm nhị phần mở rộng trên.

Hướng dẫn trả lời:

Chương trình như sau:

Câu hỏi 2. Viết chương trình đo thời gian thực chạy để so sánh hai phương án của bài toán.

Hướng dẫn trả lời:

Để đo thời gian thực chạy của hai phương án tìm kiếm nhị phân tìm số gần nhất của dãy theo phương pháp đệ quy và không đệ quy, ta có thể sử dụng module time trong Python.

Phương án tìm kiếm nhị phân mở rộng đệ quy:

- Phương án tìm kiếm nhị phân mở rộng không đệ quy:

Vận dụng

Câu hỏi 1.  Tìm cách thiết lập thuật toán tính aⁿ theo phương pháp chia để trị nhưng không sử dụng đệ quy.

Hướng dẫn trả lời:

Để tính an bằng phương pháp chia để trị mà không sử dụng đệ quy, ta có thể sử dụng một vòng lặp để lần lượt tính các giá trị a^n/2, a^n/4,a^{n}

Trong thuật toán này, biến result được khởi tạo bằng 1 và được nhân với giá trị a khi n là số lẻ.

Câu hỏi 2. Bài toán tìm vùng chỉ số của dãy đã sắp xếp.

Thiết lập thuật toán chia để trị để giải bài toán sau: Cho trước dãy A gồm n phần tử đã được sắp xếp theo thứ tự tăng dần, ví dụ:

A= [1, 2, 3, 3, 4, 4, 4, 5, 6, 6]

Cho trước giá trị K, cần tìm ra vùng chỉ số gồm các phần tử bằng K. Chương trình cần trả về hai chỉ số start, end là vị trí bắt đầu và kết thúc gồm toàn các giá trị K. Nếu không tìm thấy K thì phải trả về -1, -1.

Trong ví dụ trên, nếu K = 4 thì cần trả về hai chỉ số 4, 6.

Hướng dẫn trả lời:

Thực hiện các bước sau:

1. Tìm phần tử giữa của dãy.

2. Nếu giá trị ở vị trí giữa lớn hơn K, ta tiếp tục tìm kiếm trong nửa đầu của dãy (bên trái phần tử giữa).

3. Nếu giá trị ở vị trí giữa nhỏ hơn K, ta tiếp tục tìm kiếm trong nửa sau của dãy (bên phải phần tử giữa).

4. Nếu giá trị ở vị trí giữa bằng K, ta tiến hành tìm vị trí bắt đầu và kết thúc của đoạn chứa các phần tử bằng K bằng cách tiến hành tìm kiếm vị trí bắt đầu và kết thúc của các phần tử liên tiếp bằng K từ phải sang trái và từ trái sang phải. Khi tìm được hai vị trí này, ta sẽ trả về start và end.

5. Nếu không tìm thấy K trong dãy, ta trả về -1, -1.