Giải Chuyên đề Tin học 11 Bài 2 (Kết nối tri thức): Thiết kế thuật toán đệ quy

Giải Chuyên đề Tin học 11 Bài 2: Thiết kế thuật toán đệ quy

Khởi động trang 11 Chuyên đề Tin học 11: An được giao tìm một thiết kế mới cho bài toán tính tổng S(n) có thể được viết lại như sau:

S(n) = 1+2+3+…+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 n hoàn thiện ý tưởng trên thành một chương trình hay không?

Hình 1. Máy tính ENIAC

Lời giả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. Ý tưởng thiết kế theo đệ quy

Hoạt động 1 trang 11 Chuyên đề Tin học 11: 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+3+…+n

2. Tính lũy thừa

3. Tính n giai thừa n!= 1x2x3x…xn

Lời giả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

Bước 1. Bài toán yêu cầu tính luỹ thừa $a^n$ . Cần thiết lập hàm exp(a,n) trả về giá trị $a^n$.

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^n=a*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 x 2 x 3 x … x 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 trang 12 Chuyên đề Tin học 11: Hãy chỉ ra phần cơ sở và phần đệ quy của các chương trình trên

Lời giải:

1. Tính tổng $S\left(n\right)=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^n=a\times a\times a\times ...\times a(n lan)$

Phần cơ sở: $a^0=1$

Phần đệ quy:$a^n=a\times a^{n-1}$

3. Tính n giai thừa $n!=1\times 2\times 3\times ...\times n$

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

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

Câu hỏi 2 trang 12 Chuyên đề Tin học 11: 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?

Lời giả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ìm kiếm nhị phân

Hoạt động 2 trang 12 Chuyên đề Tin học 11: Chúng ta đã biết thuật toán tìm kiếm nhị phân trên các dãy phần tử đã sắp xếp. Hãy tìm tới thiết kế mới của thuật toán này theo kĩ thuật đệ quy. Trao đổi, thảo luận và trả lời các câu hỏi sau:

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

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

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

Lời giải:

1. Ý 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.

2. 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.

3. 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 trang 14 Chuyên đề Tin học 11: Trong chương trình trên lệnh nào đóng vai trò là phần cơ sở của đệ quy?

Lời giả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 trang 14 Chuyên đề Tin học 11: 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?

Lời giả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

Luyện tập 1 trang 14 Chuyên đề Tin học 11: 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

Lời giả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ả.

Luyện tập 2 trang 14 Chuyên đề Tin học 11: Cho trước dãy A. Viết chương trình đệ quy để in dãy A theo thứ tự ngược lại

Lời giả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

Vận dụng 1 trang 15 Chuyên đề Tin học 11: Viết chương trì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

Lời giả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]).

Vận dụng 2 trang 15 Chuyên đề Tin học 11: Chúng ta đã biết thuật toán sắp xếp chèn trên dãy A cho trước theo hàm sau

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

Lời giả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.

Vận dụng 3 trang 15 Chuyên đề Tin học 11: Bạn An đã nghĩ ra thuật toán tìm kiếm nhị phân bằng đệ quy theo cách khác như sau:

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?

Lời giả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.