Bài 6: Ý Tưởng Và Kĩ Thuật Chia Để Trị | Chuyên đề học tập Tin học 11 (Định hướng khoa học máy tính) | Chuyên Đề 2: Thực Hành Thiết Kế Thuật Toán Theo Kĩ Thuật Chia Để Trị - Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống

(Trang 28)

1. Ý tưởng chia để trị

• Với 5 viên bi, lần cân đầu tiên chúng ta lấy 4 viên bi, đặt 2 viên bi ở hai bên cân.

Trường hợp 1. Nếu cân thăng bằng thì viên bi không được cân bị lỗi, còn lại là bi giả. Như vậy, sau lần cân thứ nhất ta tìm được bi giả.

Trường hợp 2. Nếu cân bị lệch, ta sẽ xác định được bên nặng hơn chứa bi giả. Lấy hai viên bi ở bên nặng hơn và cân mỗi bên một viên, ta sẽ xác định được viên bi giả. Như vậy sau lần cân thứ hai ta tìm được bi giả.

• Với n viên bi.

- Nếu n lẻ, n = 2k + 1, sau lần cân thứ nhất với mỗi bên k viên, hoặc tìm thấy ngay viên bi giả, hoặc biết bên nào có chứa bi giả và tiếp tục cân với k viên bi đó.

- Nếu n chẵn, n = 2k, sau lần cân thứ nhất, ta tìm được k viên bi chứa viên bi giả.

Tổng quát sau mỗi lần cân, bài toán với n viên bi sẽ dẫn đến bài toán với [n/2] viên bi ([x] là phần nguyên của x). Khi bài toán dẫn đến con hai hoặc ba viên bi thì chỉ cần một lần cân nữa sẽ tìm được viên bi giả. 

Ý tưởng chia để trị là bài toán ở trên được gọi là chia để trị. Tùy bài toán gốc luôn chia thành các bài toán có kích thước nhỏ hơn, ở đây là [n/2]. Khi số bi còn lại là 2 thì bài toán rất đơn giản có thể giải quyết ngay, đó là trị. Sau khi trị xong, kết hợp lại cả quá trình để tổng hợp kết quả chung sẽ giải quyết được bài toán gốc.

(Trang 29)

Chia để trị (Divide and Conquer) là một kĩ thuật rất quan trọng trong thiết kế thuật toán và chương trình. Gồm ba bước như sau:

Bước 1: Chia (Divide) Chia bài toán ban đầu (phức tạp) thành hai hoặc nhiều bài toán con (đơn giản hơn). Các bài toán con này có cùng dạng với bài toán ban đầu hoặc có liên quan với nhau. Mỗi bài toán con có thể được giải quyết một cách độc lập. Áp dụng tiếp tục kĩ thuật chia để trị để chia một bài toán con thành các bài toán con đơn giản hơn nữa (một cách đệ quy) và cứ như thế cho đến khi tất cả các bài toán con đủ đơn giản, có thể được giải quyết một cách dễ dàng.

Bước 2: Trị (Conquer) Giải quyết các bài toán con, kết quả là các lời giải của các bài toán con.

Bước 3: Kết hợp (Combine) Kết hợp các lời giải của các bài toán con để có được lời giải của bài toán ban đầu.

Nếu bài toán ban đầu được chia thành các bài toán con có cùng dạng với nó thì quá trình phân chia và giải quyết các bài toán này là quá trình đệ quy.

Thuật toán chia để trị. Gọi P là bài toán cần giải quyết. Hàm chiaĐểTrị(P) giải quyết bài toán P dùng kĩ thuật chia để trị.

def chiaDeTri(P):

         if P là bài toán đủ đơn giản:

            loi_giai = <giải quyết bài toán P>

         else:

               <Chia bài toán P thành các bài toán con>     # Chia

               <Gọi tapbCon là tập các bài toán con>

               <Gọi tapLGcon là tập các lời giải của các bài toán con>

               for btcCon in tapbCon:

                    lgiCon = chiaDeTri(btcCon)

                    <Ghi nhận lgiCon vào tapLgiCon>         # Trị

                loi_giai = <kết hợp các lời giải của tập tapLgiCon> # Kết hợp

          return loi_giai

Gọi hàm  ChiaDeTri(P) với P là bài toán ban đầu cần giải quyết.

Sơ đồ ý tưởng chia để trị như sau:

Hình 6.2. Sơ đồ ý tưởng chia để trị

Bài toán P

Bài toán P₁  

Bài toán P₂  

...  

Bài toán P_k 

Bước chia — Nhỏ bài toán thành các bài toán con

Lời giải P₁  

Lời giải P₂  

...

Lời giải P_k

Bước trị — Giải các bài toán con

Lời giải bài toán P

Bước kết hợp — Kết hợp các lời giải của các bài toán con

(Trang 30)

1. Với n = 9 bài toán tìm bi giả cần tối đa bao nhiêu lần cân?

2. Mô tả bước "kết hợp" của bài toán 9 viên bi trên.

2. Thuật toán tìm kiếm nhị phân

Bài toán gốc của tìm kiếm nhị phân như sau:

Cho trước dãy A các số gồm n phần tử đã được sắp xếp theo thứ tự tăng dần: A[0] ≤ A[1] ≤... ≤ A[n - 1].

Cho trước giá trị cần tìm K. Cần tìm chỉ số i của dãy A sao cho A[i] = K. Nếu tìm thấy trả về i, nếu không thấy trả về –1.

Thuật toán tìm kiếm nhị phân được mô tả bởi hàm binarySearch(A, left, right, K) như sau:

1 def binarySearch(A, left, right, K):

2     if left >= right:

3         mid = (left + right)//2

4         if A[mid] == K:

5            return mid

6         elif A[mid] < K:

7                return binarySearch(A, mid + 1, right, K)

8         else:

9               return binarySearch(A, left, mid - 1, K)

10    else:

11        return -1

– Dòng lệnh 2 là điều kiện để thực hiện lời gọi đệ quy của chương trình. Hàm tìm kiếm chỉ thực hiện khi left ≤ right.

– Dòng 3 có nhiệm vụ chia bài toán tìm kiếm thành hai bài toán con: tìm kiếm bên trái và bên phải. Đây chính là bước Chia (Divide) của kĩ thuật chia để trị.

(Trang 31)

– Các dòng 7 và 9 thực hiện lệnh gọi đệ quy tương ứng với các nửa bên phải và nửa trái của dãy. Các lệnh này phụ thuộc vào lệnh tại dòng 3. Đây chính là bước Trị (Conquer) của kĩ thuật chia để trị.

– Khi thực hiện xong các dòng 7, 9 thì bài toán đã được giải xong. Ở đây bước Kết hợp (Combine) sẽ được tự động thực hiện ngay sau khi gọi đệ quy.

1. Trong thuật toán tìm kiếm nhị phân trên, phần cơ sở là các lệnh nào?

2. Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right.

Gọi T(n) là thời gian thực hiện thuật toán tìm kiếm nhị phân trong chương trình trên, n là độ dài dãy A.

– Nếu n = 1, tức là left = right. Nếu A[left] = K thì sẽ thực hiện ngay các lệnh tại dòng 5 và dừng chương trình. Nếu A[left] ≠ K thì sẽ gọi tiếp đệ quy tới các dòng 7 hoặc 9 nhưng sẽ trả về ngay – 1. Vậy trong mọi trường hợp tổng số phép toán thực hiện khi n = 1 chỉ là hằng số, ta có T(1) = O(1).

– Nếu n > 1, nếu A[mid] ≠ K thì chương trình sẽ gọi đệ quy tại các lệnh 7 hoặc 9, các lệnh gọi đệ quy này sẽ chạy trên dãy có kích thước n/2. Như vậy, trong mọi trường hợp chúng ta có công thức sau cho trường hợp tổng quát:

T(n) = T(n/2) + O(1).

Vậy không mất tổng quát có thể giả thiết tồn tại hằng số C sao cho:

T(1) = C                                     (1)

T(n) = T(n/2) + C                       (2)

Từ các công thức (1), (2) có thể chứng minh được T(n) = O(logn).

Để tham khảo chúng ta sẽ chứng minh công thức T(n) = O(logn) trong trường hợp n = 2^k, k = log₂n.

Theo công thức (2) ta có:

T(n) = T(2^k) = T(2^k-1) + C

= T(2^k-2) + C + C = T(2^k-2) + 2C = ...

= T(2⁰) + kC //theo công thức  (1)

= (k + 1)C

= C.k + C = C.log₂n + C = O(log₂n).

(Trang 32)

1. Tìm chính xác số phép toán đơn cần thực hiện trong thuật toán tìm kiếm nhị phân nếu dãy gốc chỉ có 1 phần tử.

2. Tìm số phép toán đơn cần thực hiện trong thuật toán trên nếu dãy có 2 phần tử.

LUYỆN TẬP

1. Viết chương trình hoàn chỉnh nhập dãy số từ bàn phím, các số cách nhau bởi dấu cách. Sau đó, nhập số K bất kì từ bàn phím và thực hiện việc tìm kiếm số K trong dãy trên. Nếu tìm thấy thì trả lại chỉ số của phần tử có giá trị K, ngược lại trả về –1.

2. Cho trước danh sách gồm có tên, điểm thi và được sắp xếp theo thứ tự tăng dần của điểm thi, ví dụ danh sách: [["Binh", 7.5], ["Hoa", 8], ["An", 9], ["Quang", 10]]. Viết chương trình nhập một điểm số và tìm tên học sinh có điểm thi bằng điểm số đã nhập, nếu không tìm thấy thì thông báo "không có".

VẬN DỤNG

1. Phương án không đệ quy của thuật toán tìm kiếm nhị phân có phải là chia để trị không?

2. Em hãy viết chương trình cài đặt các thuật toán tìm kiếm tuần tự và nhị phân rồi tiến hành đo thời gian thực trên máy tính với hai thuật toán này. Thực hiện kiểm thử với các bộ dữ liệu n = 10, 20, 50, 100 và ghi vào bảng để so sánh thời gian chạy giữa hai thuật toán tìm kiếm này.

3. Cho trước giá trị (số nguyên) n cần tìm bậc hai của số tự nhiên n cho trước, người ta đã thiết lập hàm sau với ý tưởng gần tương tự thuật toán tìm kiếm tuần tự như sau:

1 def floorSqrt(n):

2     k = 1

3     while k*k <= n:

4         k = k + 1

5     return k - 1

Hãy thiết kế thuật toán tìm kiếm số nguyên lớn nhất không vượt quá căn bậc hai của n bằng kĩ thuật chia để trị.