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 2 Thiết kế thuật toán bằng đệ quy

Khởi động

Câu hỏi. An được giao tìm một thiết kế mới cho bài toán tính tổng Sín) = 1 +2 +... +n. An nhận thấy S(n) có thế được viết như sau: S(n-1)= 1+2+..+n = 1+2+...+ n - 1 + n = S(n - 1) + n. Do đó, việc tính S(n) có thể được tính từ S(n - 1), tương tự S(n - 1) lại có thể được tính từ S(n - 2), cứ như vậy, cuối cùng sẽ dẫn đến cần tính S(0), nhưng S(0) = 0.

Em có thể giúp An hoàn thiện ý tưởng trên thành một chương trình hay không?

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

Bước 1. Bài toán yêu cầu tính tổng của n số nguyên từ 1 đến n. Cần thiết lập hàm S(n) trả về giá trị tổng cần tim.
Bước 2. Điều kiện n ≥ 0.
Với n = 0 ta có S(n) = 0. Đây là phần cơ sở cho điều kiện
dừng của lời gọi đệ quy của hàm S(n).
Bước 3. Dễ thấy S(n) = n + S(n - 1) là công thức truy hồi của hàm S(n) và là cơ sở của lời gọi đệ quy của hàm. Chương trình như sau:

1. def S(n):
2. if n==0
3. return 0
4. else:
5. return n + S(n-1)

1. Ý tưởng thiết kế theo đệ quy

Hoạt động 1: Tìm hiểu ý tưởng thiết kế thuật toán theo kỹ thuật đệ quy

Câu hỏi: Trao đổi, thảo luận và tìm hiểu ý tưởng thực hiện các tính toán sau bằng kĩ thuật đệ quy

1. Tính tổng S(n)=1+2+..+n
2. Tính lũy thừa a=a x a x ... x a(n lần_
3. Tính n gia hừa n!= 1x2x...n

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

1. Tính tổng S(n)=1+2+3+...+n

Bước 1. Bài toán yêu cầu tính tổng của n số nguyên từ 1 đến n. Cần thiết lập hàm S(n) trả về giá trị tổng cần tim.
Bước 2. Điều kiện n ≥ 0.
Với n = 0 ta có S(n) = 0. Đây là phần cơ sở cho điều kiện
dừng của lời gọi đệ quy của hàm S(n).
Bước 3. Dễ thấy S(n) = n + S(n - 1) là công thức truy hồi của hàm S(n) và là cơ sở của lời gọi đệ quy của hàm.Chương trình như sau:

2. Tính lũy thừa aⁿ =a×a×...×a(n lan)

Bước 1. Bài toán yêu cầu tính luỹ thừa aⁿ . Cần thiết lập hàm exp(a,n) trả về giá trị aⁿ 
Bước 2. Điều kiện là n ≥ 0 và theo quy ước thì exp(a,0) = 1 với mọi a. Đây chính là phần cơ sở cho điều kiện dừng của lời gọi đệ quy của hàm exp(a,n).
Bước 3. Ta có aⁿ =ax a^n-1 suy ra exp(a,n) = a × exp(a,n-1), đây là công thức truy hồi tính exp(a,n). Từ đó có thể thiết lập lời gọi đệ quy của hàm này.

3. Tính n giai thừa n!=1×2×3×...×n

Bước 1. Bài toán yêu cầu tính n giai thừa n!. Ta cần thiết lập hàm giaithua(n) trả về giá trị n!.
Bước 2. Điều kiện là n ≥ 0 và quy ước 0! = 1, tức là giaithua (0) = 1. Đây là cơ sở cho điều kiện dừng của lời gọi đệ quy của hàm giaithua(n).
Bước 3. Ta có công thức giaithua(n) = n × giaithua(n-1), đây là công thức truy hồi tính giaithua(n). Từ đó dễ dàng thiết lập lời gọi đệ quy cho hàm này.

Câu hỏi 1. Hãy chỉ ra phần cơ sở và phần đệ quy của các chương trình trên.

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

1. Tính tổng S(n)=1+2+3+...+n

Phần cơ sở: S(0) = 0

Phần đệ quy: S(n) = n + S(n - 1)

2. Tính lũy thừa aⁿ=a×a×...×a(nlan)

Phần cơ sở: a⁰=1

Phần đệ quy: aⁿ=a⋅aⁿ⁻¹

3. Tính n giai thừa n!=1×2×3×...×n

Phần cơ sở: 0! = 1

Phần đệ quy: n!=n × (n-1)

Câu hỏi 2. Vì sao trong ý tưởng thiết kế đệ quy trên, yêu cầu từ bài toán với kích thước lớn cần phải đưa về cùng bài toán đó với kích thước nhỏ hơn?

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

Trong ý tưởng thiết kế đệ quy, yêu cầu đưa bài toán với kích thước lớn về cùng bài toán đó với kích thước nhỏ hơn bởi vì các bài toán lớn có thể được phân chia thành các bài toán con nhỏ hơn và tương tự như vậy cho đến khi đạt được bài toán nhỏ nhất mà ta có thể giải quyết trực tiếp. Khi đó, ta sử dụng kết quả của các bài toán con này để giải quyết bài toán ban đầu lớn hơn. Nhờ vậy, lời giải ngắn gọn và dễ hiểu hơn.

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

Hoạt động 2: Thiết kế thuật toán đệ quy cho hai bài toán tìm kiếm nhị phân

Câu hỏi 1. Nêu ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy.

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

Ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy là phân chia dãy phần tử đã sắp xếp thành hai nửa bằng nhau, tìm kiếm phần tử cần tìm trong nửa phù hợp và tiếp tục phân chia và tìm kiếm đệ quy cho đến khi tìm thấy phần tử hoặc không tìm thấy.

Câu hỏi 2. Vị trí nào trong thuật toán có thể gợi ý cho kĩ thuật đệ quy?

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

Vị trí trong thuật toán có thể gợi ý cho kĩ thuật đệ quy là phần phân chia dãy phần tử thành hai nửa bằng nhau, tìm kiếm trong nửa phù hợp và tiếp tục phân chia và tìm kiếm đệ quy cho đến khi tìm thấy phần tử hoặc không tìm thấy. Đây là một bài toán con nhỏ hơn của bài toán ban đầu và có thể được giải quyết bằng cùng một thuật toán đệ quy.

Câu hỏi 3. Phần cơ sở của thiết kế đệ quy nằm ở bước nào?

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

Phần cơ sở của thiết kế đệ quy nằm ở bước cuối cùng của thuật toán, khi không còn cách nào để phân chia dãy phần tử nữa và ta chỉ còn lại một phần tử hoặc không có phần tử nào để tìm kiếm. Khi đó, ta kết luận bài toán đệ quy đã được giải quyết và trả về kết quả.

Câu hỏi 1. Trong chương trình trên lệnh nào đóng vai trò là phần cơ sở của đệ quy?

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

Trong chương trình đệ quy, lệnh có vai trò là phần cơ sở của đệ quy là lệnh kết thúc đệ quy, hay còn gọi là điều kiện dừng. Lệnh này được sử dụng để đảm bảo rằng quá trình đệ quy sẽ dừng lại khi đạt được điều kiện mong muốn.

        Trong thuật toán tìm kiếm nhị phân đệ quy, lệnh kết thúc đệ quy có thể là điều kiện tìm thấy phần tử cần tìm trong dãy hoặc không còn phần tử nào để tìm kiếm. Khi đạt được điều kiện này, thuật toán sẽ không tiếp tục đệ quy và trả về kết quả.

Câu hỏi 2. Giả sử A = [1. 3. 7, 9] và K = 10. Nếu áp dụng chương trình trên thì cần mấy lần gọi hàm đệ quy?

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

Nếu áp dụng chương trình trên thì cần 4 lần gọi hàm đệ quy

lần đầu tiên gọi hàm binarySearch(A, 0, 3, 10), lần này lệnh return sẽ gọi tiếp hàm binarySearch(A, 0, 1, 10) vì A[mid] < K

lần thứ hai gọi hàm binarySearch(A, 0, 1, 10), lần này lệnh return sẽ gọi tiếp hàm binarySearch(A, 1, 1, 10) vì A[mid] < K

lần thứ ba gọi hàm binarySearch(A, 1, 1, 10), lần này lệnh return sẽ gọi tiếp hàm binarySearch(A, 2, 1, 10) vì A[mid] < K

lần thứ tư gọi hàm binarySearch(A, 2, 1, 10), lần này lệnh return sẽ kết thúc hàm và trả về -1 vì left > right.

Luyện tập

Câu hỏi 1. Viết chương trình theo kĩ thuật đệ quy để tính hàm SL(n) là tổng các số tự nhiên lẻ nhỏ hơn hoặc bằng n.

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

Để tính hàm SL(n) là tổng các số tự nhiên lẻ nhỏ hơn hoặc bằng n theo kĩ thuật đệ quy, ta có thể sử dụng thuật toán sau:

1. Kiểm tra điều kiện dừng: nếu n = 1, trả về giá trị 1.

2. Nếu n là số lẻ, ta tính SL(n-2) và cộng thêm n vào kết quả.

3. Nếu n là số chẵn, ta tính SL(n-1) và không cộng thêm n vào kết quả.

Câu hỏi 2. Cho trước dãy A, Viết chương trình đệ quy để in dãy A theo thứ tự ngược lại.

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

Để in dãy A theo thứ tự ngược lại sử dụng kĩ thuật đệ quy, ta có thể thực hiện theo thuật toán sau:

1. Kiểm tra điều kiện dừng: nếu A rỗng, không còn phần tử nào để in, thoát khỏi hàm.

2. In phần tử cuối cùng của dãy A (A[-1]).

3. Gọi đệ quy hàm in dãy A trừ phần tử cuối cùng (A[:-1]).

Vận dụng

Câu 1.  Viết chương trình tính tổng S = 1! + 2! +... + n! theo hai cách:

a) Không sử dụng đệ quy.

b) Có sử dụng kĩ thuật đệ quy.

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

a) Không sử dụng đệ quy:

Để tính tổng của một dãy số A, ta có thể sử dụng vòng lặp for để cộng dồn từng phần tử trong dãy A lại với nhau

b) Có sử dụng kĩ thuật đệ quy:

Để tính tổng của một dãy số A sử dụng kĩ thuật đệ quy, ta có thể thực hiện theo thuật toán sau:

1. Kiểm tra điều kiện dừng: nếu A rỗng, tổng của dãy là 0.

2. Trường hợp ngược lại, tính tổng của dãy bằng tổng của phần tử cuối cùng của dãy A (A[-1]) cộng với tổng của dãy A trừ phần tử cuối cùng (A[:-1]).

Câu 2: Chúng ra đã biết thuật toán sắp xếp trên dãy A cho trước theo hàm sau:

1. def InsertionSort(A):
2. n = len(A)
3. for i in range(1,n):
4. value = A[i]
5. j = i-1
6. while i >=0 and A[j] > value:
7. A[j+i] = A[j]
8. j=j-1
9. a[j+1]=value

Hãy thiết kế lại chương trình trên sử dụng kỹ thuật đệ quy

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

Để sắp xếp một mảng bằng thuật toán sắp xếp chèn đệ quy, ta có thể thực hiện theo thuật toán sau:

1. Kiểm tra điều kiện dừng: nếu độ dài của mảng là 1 hoặc ít hơn, mảng đã được sắp xếp.

2. Trường hợp ngược lại, sắp xếp mảng con trừ phần tử cuối cùng (arr[:-1]) bằng thuật toán sắp xếp chèn đệ quy.

3. Chèn phần tử cuối cùng vào mảng con đã sắp xếp được trả về ở bước 2.

Câu 3: Bạn An đã nghĩ ra thuật toán tím kiếm nhị phân bằng kỹ thuật đệ quy theo cách khac snhuw sau:

1. def binarySearch(A, left, rught, k):
2. if left == right:
3. if A[left]==K:
4. return left
5. else:
6. return n-1
7. else:
8. mid = (left+right)/2
9. if A[mid] ==K:
10. return mid
11. elfi A[mid]<K:
12. return binarySearch(A, mid+1,right, K)
13. else:
14. return binarySearch(A, left, mid, K)

a, Chương trình của bạn An có đúng không

b, Trong chương trình trên, phần cơ sở là những lệnh nào?

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

a) Chương trình của An đúng.

b) Phần cơ sở của đoạn lệnh trên là việc kiểm tra điều kiện kết thúc đệ quy, nếu left==right và A[left] == K thì trả về giá trị left, ngược lai nếu A[left] !=K thì trả về -1. Nếu không, tiếp tục tìm kiếm bằng cách tính giá trị mid ở giữa low và high, kiểm tra nó có bằng x hay không, nếu có thì trả về mid, nếu không thì tiếp tục tìm kiếm trong phần bên trái nếu x nhỏ hơn giá trị ở vị trí mid, hoặc phía bên phải nếu x lớn hơn giá trị ở vị trí mid. Quá trình đệ quy này sẽ tiếp tục cho đến khi tìm thấy giá trị x hoặc không tìm thấy và trả về -1.