Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 3: Thực hành thiết kế thuật toán đệ quy

CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Nhớ lại kiến thức ở bài học cũ và trả lời câu hỏi: Nêu đặc điểm của hàm đệ quy.

ĐẶC ĐIỂM CỦA HÀM ĐỆ QUY

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 cơ sở thì chương trình không cần gọi đệ quy

BÀI 3: THỰC HÀNH THIẾT KẾ THUẬT TOÁN ĐỆ QUY

BÀI TOÁN 1

Tìm số ước chung lớn nhất

Nhiệm vụ 1: Chạy chương trình

Cài đặt và chạy trên máy chương trình đã cho với một số dữ liệu đầu vào (x, y) khác nhau:

Nhiệm vụ 2: Viết hàm đệ quy

• Viết hàm đệ quy UCLN (x, y) theo công thức đã cho:

Hàm đệ quy

Nhiệm vụ 3: Trả lời câu hỏi

Em hãy chạy chương trình câu a) và b) với hai bộ dữ liệu

x = 5, y = 0

x = 0, y = 5

Em hãy nhận xét kết quả thu được.

• Cả hai hàm đã cho đều được dùng để tính UCLN của hai số tự nhiên x, y.
• Hàm UCLN ở câu a chỉ chạy được với điều kiện y khác 0.
• Nếu cố nhập giá trị 0 cho y chương trình sẽ báo lỗi, ("ZeroDivisionError: integer division or modulo by zero") ở dòng lệnh r = x%y.

KẾT LUẬN

BÀI TOÁN 2

Nhận biết lỗi lặp vô hạn khi cài đặt đệ quy

Em hãy thực hiện các yêu cầu sau:

• Đọc hàm đệ quy product(n) ở Hình 2 và cho biết kết quả thu được khi thực thi lời gọi hàm product(8).
• Chạy chương trình ở Hình 2 và cho biết Python thông báo lỗi như thế nào.
• Sửa chương trình ở Hình 2 như sau: Thay thế câu lệnh cuối cùng print(‘KQ = ‘, product(8)) thành print(‘KQ = ‘, product(9)) và cho biết kết quả khi chạy chương trình.
• Theo em, tại sao Python lại thông báo lỗi khi chương trình thực thi product(8), nhưng lại không báo lỗi khi chương trình thực thi product(9)?

Gợi ý: Kiểm tra xem trong quá trình thực hiện product(8) có lần gọi đệ quy nào đến được trường hợp cơ sở if(n==1) hay không.

a

product(8):

return 8 * product(6)

product(6):

return 6 * product(4)

product(4):

return 4 * product(2)

product(2):

return 2 * product(0)

product(0):

return 0 * product(-2)

Lặp vô hạn: gọi product(-4), product(-6), product(-8)…

b

Thông báo lỗi là:

"line 2, in product

If (n==1):

RecursionError: maximum recursion depth exceeded in comparison".

c

Kết quả:

KQ = 945

d

Do Python hạn chế số lần tối đa một hàm đệ quy có thể tự gọi đến chính nó.

Trong quá trình thực thi một hàm đệ quy mà bước cơ sở không bao giờ được thực hiện thì hàm đệ quy sẽ bị lặp vô hạn, không bao giờ dừng.

KẾT LUẬN

BÀI TOÁN 3

Xác định ý nghĩa của hàm đệ quy cho trước

Nhiệm vụ:

• Cho biết ý nghĩa của hàm abs và phép toán // là gì?
• Em hãy chạy chương trình ở Hình 3 và cho biết hàm đệ quy mystery(n) với đầu vào n là số nguyên được dung để giải quyết bài toán nào.

a

Hàm abs (x): trả về giá trị tuyệt đối của số x.

Phép toán //: x // y trả về một số nguyên là số nguyên lớn nhất nhỏ hơn hoặc bằng kết quả của phép chia x cho y.

Ví dụ: 5 // 3 = 1,4 // 3 = 1.

b

Hàm mystery (n) dùng để đếm số lượng chữ số có trong số nguyên n.

LUYỆN TẬP

Câu 1: Số lần tối đa một hàm đệ quy có thể tự gọi đến chính nó là

A. 100

B. 1000

C. 2000

D. 10000

B. 1000

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

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