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

HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: Chuyển giao nhiệm vụ

- GV yêu cầu HS thảo luận cặp đôi, đọc sách CĐHT, quan sát Hình 1 và trả lời câu hỏi Hoạt động 1 trang 10 sách CĐHT:

Hai chương trình trong Hình 1 yêu cầu người sử dụng nhập hai giá trị nguyên a và n từ bàn phím (n ≥ 0), rồi gọi là hàm power1 (a, n) và power2 (a, n) tương ứng để in ra màn hình giá trị aⁿ. Em hãy đọc cả hai chương trình này và:

a) Cho biết kết quả thu được của hai chương trình khi giá trị của cặp (a, n) nhập vào lần lượt bằng (2, 4) và (3, 6).

b) Nhận xét về sự khác nhau giữa hai hàm power1 (a, n) và power2 (a, n).

- Trên cơ sở đó, GV yêu cầu HS trả lời câu hỏi: Cho biết hàm đệ quy được xác định như thế nào?

- GV đặt câu hỏi mở rộng cho HS trả lời: 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?

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

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

- Hướng dẫn trả lời câu hỏi Hoạt động 1 trang 10 sách CĐHT:

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 aⁿ:

⮚ Hàm power1 (a, n): Tính aⁿ theo công thức aⁿ = 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 aⁿ, 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): tính aⁿ theo công thức đệ quy (1) được xây dựng từ phần khởi động. Do đó, hàm power2 (a, n) cũng bao gồm hai phầ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.

- Đặc điểm hàm đệ quy:

o   Trong hàm có một hoặc nhiều lệnh gọi đến chính nó.

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

- Hướng dẫn trả lời 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

Hoặc

def power2 (a, n):

  if n >= 1:

     return a * power2(a, n – 1)

  else:

     return 1

HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: Chuyển giao nhiệm vụ

- GV đặt vấn đề HS: 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.

Áp dụng Hình 2. Mô hình của thuật toán đệ quy vào power2 (a, n) ở Hoạt động 1 trả lời các câu hỏi sau:

- 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?

Lưu ý: 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.

- 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?

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS trả lời câu hỏi Hoạt động 2 trang 11 sách CĐHT.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, quan sát hình và trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- HS giơ tay phát biểu trả lời câu hỏi.

- Các HS nhận xét, bổ sung.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả trả lời của HS

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS hoàn thành ghi chép đầy đủ vào vở.

II. Thuật toán đệ quy

- Thuật toán đệ quy được cài đặt dưới dạng hàm đệ quy, để xử lí với các đối tượng được định nghĩa đệ quy.

- Hướng dẫn trả lời câu hỏ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ảicủa bài toán mà không cần phải tính toán gì khác.

+ dequy(<input với kích thước nhỏ hơn>) : Tương ứng trong hàm power2 (a, n) là power2(a, n – 1), input kích thước từ n giảm xuống còn n – 1.

+ <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>: Trong hàm power2 (a, n) để có được lời giải của bài toán kích thước n, ta chỉ cần giải duy nhất một bài toán có kích thước input nhỏ hơn n – 1 (tương ứng với power2(a, n – 1)); lời giải của bài toán kích thước n thu được thông qua một phép nhâ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 sẽ ra lời giải của bài toán kích thước n (thực hiện thông qua câu lệnh return a * power2(a, n – 1)).

- Hướng dẫn trả lời câu hỏi Hoạt động 2 trang 11 sách CĐHT:

a)

+ return 0

+ return h(n – 1) + n – 1

b) 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”.