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 (P2)

1. HOẠT ĐỘNG LUYỆN TẬP
2. Mục tiêu: HS củng cố lại kiến thức về thuật toán đệ quy.
3. Nội dung: HS hoạt động cá nhân trả lời câu hỏi liên quan đến thuật toán đệ quy.
4. Sản phẩm: Hướng dẫn trả lời câu hỏi liên quan đến thuật toán đệ quy.
5. Tổ chức thực hiện

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

- GV cho HS trả lời nhanh các câu hỏi trắc nghiệm về các nội dung liên quan đến thuật toán đệ quy.

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

1. Trong hàm đệ quy chỉ được phép chứa duy nhất một lệnh gọi đến chính nó.
2. Trong hàm đệ quy, trường hợp cơ sở không được phép liên tục gọi đệ quy.
3. Hàm đệ quy là hàm mà thân hàm có chứa những lệnh gọi đến chính nó.
4. Hàm đệ quy không bao giờ dừng nếu không có trường hợp cơ sở.

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à

1. return 1 B. power2(a, n – 1)
2. if n == 0 D. return a * power2(a, n – 1)

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à

1. return 1 B. power2(a, n – 1)
2. if n == 0 D. return a * 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à

1. return 1 B. power2(a, n – 1)
2. if n == 0 D. return a * power2(a, n – 1)

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

def h(n):

  if (n == 0 or n == 1) :           #Trường hợp cơ sở

        return 0

  else:

        return h(n-1) + n-1        #Gọi đệ quy

#Nhập giá trị n:

n = int (input("Nhập số lượng người trong phòng n = "))

#Xuất ra kết quả của hàm:

Print ("Tổng số các cái bắt tay giữa",n,"người = ",h(n))

Khi n = 4 thì được kết quả là

1. 3 B. 6 C. 8                   D. 10

Bài 1. 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:

Bài 2. 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).

1. a) Em hãy cho biết dấu ? trong hàm đệ quy F(n) cần được thay bằng gì.
2. 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.

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

• HS đọc câu hỏi và trả lời.

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

• Đại diện HS giơ tay phát biểu.
• Các HS khác nhận xét, góp ý, bổ sung.

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

-  GV chữa bài, chốt đáp án.

- GV nhận xét thái độ học tập, phương án trả lời của HS, ghi nhận và tuyên dương.

Đáp án

Bài 1. 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.

1. a) return n

return F(n – 1) + F(n – 2)

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

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

• Bước 1: F(3) được thực thi, chương trình thực hiện câu lệnh return F(2) + F(1).
• Bước 2: F(2) được thực thi, tương ứng với n = 2 chương trình thực hiện câu lệnh return F(1) + F(0).
• Bước 3: Câu lệnh F(1) được thực thi, tương ứng với n = 1, tương ứng với n = 1 là trường hợp cơ sở, do đó chương trình thực hiện câu lệnh return 1.
• Bước 4: Thể hiện câu lệnh F(1) kết thúc và trả giá trị về là 1, chương trình quay về hàm F(2).
• Bước 5: Thực thi F(0), tương ứng với n = 0 nên hàm thực hiện câu lệnh return 0.
• Bước 6: Thể hiện câu lệnh F(0) kết thúc và giá trị trả về là 0, chương trình quay về hàm F(2).
• Bước 7: Chương trình đang trong hàm F(2), câu lệnh return F(1) + F(0) đã có các kết quả trả về từ F(1) và F(0), do đó phép cộng được thực hiện, tương ứng là 1 + 0. Hàm F(2) kết thúc và giá trị trả về là 1, chương trình quay lại hàm F(3).
• Bước 8: Câu lệnh F(1) được thực thi, tương ứng với n = 1 chính là trường hợp cơ sở, do đó hàm trả về giá trị 1.
• Bước 9: Thể hiện câu lệnh F(1) kết thúc và giá trị trả về là 0, chương trình quay lại hàm F(3).
• Bước 10: Trong hàm F(3), câu lệnh return F(2) + F(1) đã có các kết quả trả về từ F(2) và F(1), do đó phép cộng sẽ được thực hiện, tương ứng là 1 + 1. Hàm F(3) kết thúc và trả về giá trị 2, chương trình quay lại F(4).

⮚ Bước 11 đến 16: Thực hiện tính F(2), quá trình hoàn toàn tương tự như các bước 2 đến 7.

⮚ Bước 17: Trong hàm F(4), câu lệnh return F(3) + F(2) đã có các kết quả trả về từ F(3) và F(2), do đó, phép cộng sẽ được thực hiện tương ứng là 2 + 1. Hàm F(4) kết thúc và trả về giá trị 3.

1. HOẠT ĐỘNG VẬN DỤNG
2. a) Mục tiêu: Vận dụng kiến thức giải một số bài tập liên quan đến thuật toán đệ quy.
3. b) Nội dung: HS làm việc cá nhân thực hiện giải một số bài tập liên quan đến thuật toán đệ quy.
4. c) Sản phẩm: Gợi ý trả lời bài tập liên quan đến thuật toán đệ quy.
5. d) Tổ chức thực hiện:

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

- GV yêu cầu HS làm việc cá nhân giải bài tập Vận dụng trang 14 sách CĐHT:

Mẹ An là cô giáo dạy Toán, muốn nhờ An in lời một bài hát dạy đếm số cho các em học sinh có định dạng như sau:

          Có 20 chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc ra ăn các bạn nhé,

          Vậy trong hộp còn 19 chiếc thôi.

          Có 19 chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc ra ăn các bạn nhé,

          Vậy trong hộp còn 18 chiếc thôi.

          …

          Có 2 chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc ra ăn các bạn nhé,

          Vậy trong hộp còn 1 chiếc thôi.

          Còn duy nhất 1 chiếc kẹo trong hộp các bạn ơi, ta lấy nốt chiếc cuối cùng ra ăn các bạn nhé,

          Không còn chiếc kẹo nào trong hộp, ta cùng nhau đi mua thêm kẹo thôi nào.

Em hãy giúp An viết hàm đệ quy in_loi_bai_hat (n) với n là số kẹo để có thể in ra lời bài hát như trên nếu gọi hàm in_loi_bai_hat (20).

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

- HS suy nghĩ và giải bài tập liên quan đến thuật toán đệ quy.

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

- HS xung phong trình bày bài làm của mình.

- HS khác nhận xét và bổ sung.

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

- GV chữa bài, chốt đáp án.

- GV nhận xét thái độ làm việc, sản phẩm, phương án trả lời của các học sinh, ghi nhận và tuyên dương.

Gợi ý trả lời:

def in_loi_bai_hat (n):

    if n == 0: #Trường hợp cơ sở

         print("Không còn chiếc kẹo nào trong hộp, ta cùng nhau đi mua thêm kẹo thôi nào.")

    elif n == 1: #Trường hợp cơ sở

         print("Còn duy nhất 1 chiếc kẹo cuối cùng trong hộp thôi các bạn ơi, ta lấy nốt chiếc kẹo cuối cùng ra ăn các bạn nhé,")

         in_loi_bai_hat(n–1)

    else:

         print("Có", n,"chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc kẹo ra ăn các bạn nhé,")

         print ("Vậy trong hộp còn",n-1,"chiếc thôi.")

         in_loi_bai hat(n-1)

in_loi_bai_hat(20)

* HƯỚNG DẪN VỀ NHÀ

- Ghi nhớ kiến thức trong bài.

- Chuẩn bị bài 3. Thực hành thiết kế thuật toán đệ quy.