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 3: Thực hành thiết kế thuật toán đệ quy (P2)

Hoạt động 3: Bài toán 3. Xác định ý nghĩa của hàm đệ quy cho trước

1. Mục tiêu: Xác định được ý nghĩa của hàm đệ quy.
2. Nội dung: HS hoạt động độc lập, đọc sách CĐHT, quan sát Hình 3, chạy chương trình và trả lời câu hỏi trang 17, 18.
3. Sản phẩm: Hướng dẫn trả lời câu hỏi Bài toán 3 trang 17, 18 sách CĐHT.
4. Tổ chức thực hiện

1. HOẠT ĐỘNG LUYỆN TẬP
2. Mục tiêu: HS củng cố lại kiến thức về thiết kế 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 thiết kế 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 thiết kế 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: Số lần tối đa một hàm đệ quy có thể tự gọi đến chính nó là

1. 100 B. 1000 C. 2000               D. 10000

Câu 2: Nếu muốn thay đổi số lần tối đa một hàm đệ quy có thể tự gọi chính nó ta dùng hàm

1. sys.setrecursionlimit() B. logger.setLevel()
2. callingthisfunction() D. sock.connect()

Câu 3: Bộ dữ liệu (x, y) = (56, 140) chạy chương trình ở Bài toán 1 được kết quả UCLN là

1. 48 B. 36 C. 60                 D. 42

Câu 4: Cho biết chương trình đệ quy sau xảy ra lỗi gì?

def giaithua(n):

    """Đây là hàm tính giai thừa của một số nguyên"""

   if n == 1:

      return 1

   else:

   return (n * giaithua(n-1))

print (giaithua(1001))

1. ZeroDivsion: division by zero
2. RecursionError: maximum recursion depth exceeded in comparison
3. SyntaxError: can't assign to literal
4. FileNotFoundError: [Error 2] No such file or directory: 'imaginary.txt'

Câu 5: Cho biết ý nghĩa của hàm abs trong chương trình

1. Trả về chuỗi số nguyên từ số bắt đầu đến số kết thúc
2. Làm tròn số thập phân
3. Trả về số thập phân từ số, chuỗi
4. Trả về giá trị tuyệt đối của một số

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

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 thiết kế 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 thiết kế thuật toán đệ quy.
4. c) Sản phẩm: Gợi ý trả lời bài tập liên quan đến thiết kế 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 18 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 thiết kế 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:

1. a) Trường hợp 1: An đứng ở các nút có i = D → một cách duy nhất để đến nút (D, C) đó là hướng lên trên.

Trường hợp 2: An đứng ở các nút j = C → một cách duy nhất để đến nút (D, C) đó là nhảy từng bước theo hướng bên phải.

Trường hợp 3: An đứng ở các nút giao lộ có tọa độ (i, j) → Có 2 cách:

- Tổng số cách đi từ ô (i + 1, j) đến ô (D, C).

- Tổng số cách đi từ ô (i, j + 1) đến ô (D, C).

1. b) Trường hợp cơ sở xảy ra khi:

• Hoặc i = D tức là An đang đứng ở cột cuối cùng bên phải → chỉ còn một cách duy nhất để đạt đến nút (D, C) đó là nhảy từng bước theo hướng lên trên.
• Hoặc j = C tức là An đang đứng ở dòng trên cùng, do đó, chỉ còn một cách duy nhất để đạt đến nút (D, C) đó là nhảy từng bước theo hướng sang phải.

Do đó, trong trường hợp cơ sở, hàm trả về giá trị 1.

- Khi đang ở nút (i, j): An có hai cách đi hoặc sang phải đến ô (i + 1, j) hoặc lên trên đến ô (i, j + 1). Do đó số cách để An  đi từ ô (i, j) đến ô (D, C) chính là tổng số cách đi từ ô (i + 1, j) đến ô (D, C) và số cách đi từ ô (i, j + 1) đến ô (D, C). Vì vậy, ở phần gọi đệ quy, ta có câu lệnh return dem(i + 1, j, D, C) + dem(i, j + 1, D, C).

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

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

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