Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 2: Thuật toán đệ quy

XIN CHÀO CÁC EM!

MỜI CÁC EM ĐẾN VỚI

BÀI HỌC MỚI!

KHỞI ĐỘNG

n số a

Gợi ý đáp án

• Phần đệ quy: Ta có an = a × an – 1, do đó có thể viết F(n) = a × F(n – 1).
• Phần cơ sở là hàm tại n có giá trị nhỏ nhất bằng 0, có a0 = 1 do đó F(0) = 1.

BÀI 2

THUẬT TOÁN ĐỆ QUY

NỘI DUNG BÀI HỌC

Khái niệm hàm đệ quy

1

Thuật toán đệ quy

2

KHÁI NIỆM HÀM ĐỆ QUY

1

Hoạt động 1

Hình 1. Hai chương trình tính an

HƯỚNG DẪN THỰC HIỆN

a

• Khi (a, n) = (2, 4), giá trị trả về của cả hai chương trình đều là 16.
• Khi (a, n) = (3, 6), giá trị trả về của cả hai chương trình đều là 729.

b

Hoạt động này đề xuất hai cách tính an:

• Hàm power1 (a, n):
• Tính an theo công thức an = a × a × … × a (gồm n thừa số a).
• Do đó hàm sử dụng một vòng lặp for lặp n lần, mỗi lần lặp nhân vào biến kq một giá trị a.
• Biến kq lưu trữ kết quả của an, do đó khởi tạo ban đầu bằng 1.

Hàm power1 (a, n) không phải hàm đệ quy

• Hàm power2 (a, n):
• Phần đầu bao gồm các câu lệnh xử lí phần cơ sở.
• Phần thứ hai tương ứng với phần đệ quy.

Hàm power2 (a, n) là hàm đệ quy

Cho biết hàm đệ quy được xác định như thế nào?

• Trong hàm có một hoặc nhiều lệnh gọi đến chính nó.
• Mỗi lần gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn so với lần gọi trước. Khi đạt được trường hợp thì chương trình không cần gọi đệ quy.

Nếu hàm power2 (a, n) xử lí phần đệ quy trước, phần cơ sở sau thì cần sửa thế nào?

Câu hỏi mở rộng

def power2 (a, n):

if n >= 1:

return a * power2(a, n – 1)

else if n == 0:

return 1

def power2 (a, n):

if n >= 1:

return a * power2(a, n – 1)

else:

return 1

THUẬT TOÁN ĐỆ QUY

2

Thuật toán đệ quy được cài đặt dưới dạng hàm đệ quy giải các bài toán được định nghĩa đệ quy.

Hình 2. Mô hình của thuật toán đệ quy

TRƯỜNG HỢP CƠ SỞ

• Các câu lệnh kiểm tra if (<kích thước của input là nhỏ nhất>) tương ứng vào câu lệnh nào?
• <Giải bài toán kích thước input nhỏ nhất để thu được lời_giải> tương ứng với câu lệnh nào?

Trong nhiều bài toán phức tạp khác thì không đơn giản chỉ có duy nhất câu lệnh return 1 như trong trường hợp hàm power2 (a, n) mà sẽ phải giải một bài toán cụ thể gồm nhiều câu lệnh.

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

Các câu lệnh kiểm tra if (<kích thước của input là nhỏ nhất>): tương ứng trong hàm power2 (a, n) là câu lệnh if n == 0.

<Giải bài toán kích thước input nhỏ nhất để thu được lời_giải>: Trong hàm power2 (a, n) chỉ có câu lệnh return 1 để trả về giá trị lời_giải của bài toán mà không cần phải tính toán gì khác.

GỌI ĐỆ QUY

• dequy(<input với kích thước nhỏ hơn>) tương ứng với câu lệnh nào?
• <Kết hợp lời giải của các bài toán có kích thước input nhỏ hơn để thu được lời_giải> được thực hiện trong hàm power2 (a, n) như thế nào?

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

dequy(<input với kích thước nhỏ hơn>)

power2(a, n – 1)

input kích thước từ n giảm xuống còn n – 1.

Giải duy nhất một bài toán có kích thước input nhỏ hơn n – 1

Để có được lời giải của bài toán kích thước n

Đem giá trị của a nhân với kết quả của bài toán kích thước n – 1

return a * power2(a, n – 1)

• Câu lệnh thực hiện:

Hoạt động 2

Em hãy:

• Đọc chương trình ở Hình 3 và cho biết dấu trong hàm h(n) cần được thay bằng gì để tính được số lượng cái bắt tay diễn ra trong phòng họp n người.
• Chạy chương trình để tính số cái bắt tay khi n = 5 và n = 10.

?

Hình 3. Chương trình đệ quy giải bài toán về tính số cái bắt tay

• Khi n = 5, chương trình in ra “Tổng số cái bắt tay giữa 5 người bằng 10”.
• Khi n = 10, chương trình in ra “Tổng số cái bắt tay giữa 10 người bằng 45”.

LUYỆN TẬP

Câu 1: Chọn đáp án SAI:

A. Trong hàm đệ quy chỉ được phép chứa duy nhất một lệnh gọi đến chính nó.

B. Trong hàm đệ quy, trường hợp cơ sở không được phép liên tục gọi đệ quy.

C. Hàm đệ quy là hàm mà thân hàm có chứa những lệnh gọi đến chính nó.

D. Hàm đệ quy không bao giờ dừng nếu không có trường hợp cơ sở.

A. Trong hàm đệ quy chỉ được phép chứa duy nhất một lệnh gọi đến chính nó.

Câu 2: Trong hàm power2 (a, n) câu lệnh tương ứng trong mô hình thuật toán đệ quy if (<kích thước của input là nhỏ nhất>) là

A. return 1

B. power2(a, n – 1)

C. if n == 0

D. return a * power2(a, n – 1)

C. if n == 0

Câu 3: Trong hàm power2 (a, n) câu lệnh tương ứng trong mô hình thuật toán đệ quy dequy(<input với kích thước nhỏ hơn>) là

A. return 1

B. power2(a, n – 1)

C. if n == 0

D. return a * power2(a, n – 1)

B. power2(a, n – 1)

Câu 4: Trong hàm power2 (a, n) câu lệnh tương ứng trong mô hình thuật toán đệ quy <Kết hợp lời giải của các bài toán có kích thước input nhỏ hơn để thu được lời_giải> là

A. return 1

B. power2(a, n – 1)

C. if n == 0

D. return a * power2(a, n – 1)

D. return a * power2(a, n – 1)

Câu 5: Chạy chương trình sau:

Khi n = 4 thì kết quả là?

A. 3

B. 6

C. 8

D. 10

B. 6

Bài 1.(SGK-tr12) Em hãy đọc chương trình ở Hình 5 và cho biết kết quả nhận được khi chạy chương trình:

• Khi chạy chương trình, trên màn hình sẽ hiển thị dòng: Kết quả bằng 12.
• Khi n > 0, hàm test (n) trả về tổng của các số chẵn từ 0 đến số chẵn lớn nhất còn nhỏ hơn hoặc bằng n.

Bài 2.(SGK-tr13) Dãy số Fibonacci được định nghĩa đệ quy như sau:

- Phần cơ sở: F(n) = 0 nếu n = 0, F(n) = 1 nếu n = 1.

- Phần đệ quy: F(n) = F(n – 1) + F(n – 2) nếu n ≥ 2.

Hàm đệ quy F(n) cho trong hình 6 sử dụng định nghĩa đệ quy ở trên để tính và trả về giá trị của F(n).

a) Em hãy cho biết dấu ? trong hàm đệ quy F(n) cần được thay bằng gì.

b) Hình 7 liệt kê lần lượt 17 bước chương trình sẽ thực hiện khi lời gọi đến F(4) được thực thi. Em hãy đưa ra giải thích bằng lời ý nghĩa của 17 bước đã cho.

a

b

• Khi câu lệnh F(4) được thực thi, chương trình thực hiện câu lệnh return F(3) + F(2).
• Vì vậy, chương trình trước tiên sẽ tính F(3) thông qua các bước từ 1 đến 10, sau đó tính F(2) thông qua các bước từ 11 đến 16, các kết quả tương ứng từ F(3) và F(2) sẽ được cộng lại và trả về hàm F(4) tại bước 17.

Các bước thực hiện

Bước 1 đến 10: Tính F(3)

Bước 11 đến 16: Thực hiện tính F(2)

Bước 17. Hàm F(4) kết thúc và trả về giá trị 3.

VẬN DỤNG

--------------- Còn tiếp ---------------