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 1: Khái niệm đệ quy và ví dụ (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ề định nghĩa đệ quy và các thành phần cơ bản trong định nghĩa đệ quy.
3. Nội dung: HS hoạt động cá nhân trả lời câu hỏi trắc nghiệm khách quan.
4. Sản phẩm: Đáp án câu hỏi trắc nghiệm khách quan.
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 định nghĩa đệ quy và các thành phần cơ bản trong định nghĩa đệ quy.

Câu 1: Định nghĩa đệ quy của một đối tượng gồm:

1. phần cơ sở và phần quy tắc. B. phần quy tắc và phần định nghĩa.
2. phần cơ sở và phần đệ quy. D. phần quy tắc và phần đệ quy.

Câu 2: Cho công thức toán học sau:

Phần cơ sở của xⁿ là

1. x¹ = 0. B. x⁰ = 1. C. xⁿ = x × x^{n – 1}.             D. xⁿ = x.

Câu 3: Cho công thức toán học sau:

Phần đệ quy của xⁿ là

1. x¹ = 0. B. x⁰ = 1. C. xⁿ = x × x^{n – 1}.             D. xⁿ = x.

Câu 4: Sự vật nào sau đây có tính đệ quy?

1. Sách giáo khoa. B. Búp bê Matryoshka.
2. Bình nước. D. Búp bê Barbie.

Câu 5: Phát biểu nào sau đây sai về đệ quy?

1. Một đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông qua khái niệm về chính nó.
2. Đối tượng đệ quy thì sự vật, hiện tượng liên quan đến đối tượng sẽ được lặp lại nhiều lần.
3. Trong đệ quy, lời giải của một bài toán phụ thuộc vào lời giải của các trường hợp nhỏ hơn cùng một bài toán.
4. Đệ quy là cách gọi khác của lặp.

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

• HS đọc câu hỏi và trả lời câu hỏi trắc nghiệm khách quan.

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

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 định nghĩa đệ 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 định nghĩa đệ quy.
4. c) Sản phẩm: Gợi ý trả lời bài tập liên quan đến định nghĩa đệ 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:

+ Câu 3 sách CĐHT trang 9 sách CĐHT.

+ Câu hỏi hộp Vận dụng trang 9 sách CĐHT.

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

- HS suy nghĩ và giải bài tập liên quan đến định nghĩa đệ 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:

- Câu 3 sách CĐHT trang 9 sách CĐHT:

• Xét tập S được định nghĩa đệ quy như sau:

+ Phần cơ sở: x₀ = 1.

+ Phần đệ quy: x_n = 2k + 1 (k là số nguyên dương bất kì).

• So sánh cách mô tả tập S:

+ Ưu điểm lớn nhất của phép đệ quy là tiếp cận xử lý vấn đề bằng những đoạn code sạch, gọn gàng, dễ đọc, dễ hiểu. Nhược điểm rõ ràng là nguy cơ cao tràn bộ nhớ Stack như đã giải thích ở trên.

+ Cùng giải quyết một bài toán nhưng một phương án khác để thay thế đệ quy là sử dụng vòng lặp.

+ Dù vòng lặp có một ưu điểm là chỉ có một vòng duy nhất được gọi ra và ta sẽ không phải lo nghĩ gì về vấn đề tràn bộ nhớ Stack. Nhưng vòng lặp cũng có một nhược điểm so với đệ quy là code xử lý sẽ viết dài và phức tạp hơn.

- Câu hỏi hộp Vận dụng trang 9 sách CĐHT:

Để xây dựng phân đệ quy cho h(n), em hãy xác định lời giải của bài toán khi có 0 người trong phòng từ lời giải của bài toán khi có n - 1 người trong phòng.

1. a) Khi n = 0 thì số lượng cái bắt tay bằng 0.

Khi n = 1 thì số lượng cái bắt tay bằng 0.

Khi n = 2 thì số lượng cái bắt tay bằng 1.

Khi n = 3 thì số lượng cái bắt tay bằng 3.

Khi n = 4 thì số lượng cái bắt tay bằng 6.

1. b) Để đếm được số lượng cái bắt tay, ta sẽ bắt đầu từ khi phòng không có người nào và khi chỉ có một người, số lượng bắt tay cả hai trường hợp này đều là 0. Sau đó, tại mỗi bước lặp lại i (với i = 2, 3…n) ta sẽ thêm người thứ i vào phòng. Lúc này, người thứ i sẽ đi bắt tay lần lượt i – 1 người đang có trong phòng, tức là có thêm I – 1 lượt bắt tay mới. Như vậy, số lượng cái bắt tay sẽ được tính bằng số lượng bắt tay đã diễn ra giữa i – 1 người đang ở trong phòng, cộng thêm i – 1 lượt bắt tay mới của người thứ i này. Do đó, ta có h(i) = h(i – 1) + i – 1, với i = 2. 3…n.

Do đó, ta xây dựng được hàm mang tính đệ quy h(n) được định nghĩa như sau:

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

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

- Chuẩn bị bài 2. Thuật toán đệ quy.