Trang bìa
Trang bìa
Ảnh
BÀI 3 THỰC HÀNH THIẾT KẾ THUẬT TOÁN ĐỆ QUY
CHUYÊN ĐỀ1. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY
Khái niệm
Yêu cầu
Hình vẽ
Học xong bài này, em sẽ: * Viết và thực hiện được một vài chương trình cài đặt thuật toán đệ quy. * Nhận biết được lỗi lặp vô hạn khi cài đặt thuật toán đệ quy.
Bài toán 1. Tìm ước số chung lớn nhât
Tìm ước số chung
a) Để tìm ước số chung lớn nhất của hai thuật toán số tự nhiên x và y latex(x ne 0, y ne 0). Ta sử dụng công thức sau: Em hãy chạy chương trình ở Hình 1 với một số bộ dữ liệu đầu vào (x, y) khác nhau để chạy kiểm thử chương trình.
Ảnh
Ảnh
Hình 1. Chương trình tìm ước số chung lớn nhất của hai hàm số tự nhiên
Viết hàm đệ quy
b) Viết hàm đệ quy UCLN1(x,y). tìm các số chung lớn nhất của hai số tự nhiên x và y không đồng thời bằng 0, sử dụng công thức sau
Ảnh
Sau đó, viết chương trình gọi hàm UCLN1(x,y) để tìm ước số chung lớn nhất của hai số x và y được nhập vào từ bàn phím. Chạy chương trình với các bộ dữ liệu đầu vào em đã sử dụng ở câu a) và so sánh kết quả thu được. c) Em hãy chạy chương trình trong câu a) và b) với hai bộ dữ liệu x = 5, y = 0 và x = 0 y = 5. Sau đó nhận xét kết quả thu được.
Bài toán 2. Nhận biết lỗiât
Yêu cầu
Em hãy thực hiện các yêu cầu sau: a) Đọ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) b) Chạy chương trình ở Hình 2 và cho biết python thông báo lỗi như thế nào. c) Sửa chương trình ở Hình 2 như sau : Thay 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. d) 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).
Yêu cầu
Ảnh
Hình 2. Chương trình đệ quy có lỗi
Bài toán 3. Ý nghĩa của hàm đệ quy cho trước
Hàm đệ quy
Hình 3.Chương trình có sử dụng hàm đệ quy
Ảnh
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 dùng để giải quyết bài toán nào.
Bài tập
Ứng dụng
Hình vẽ
a) Tìm hiểu bài toán: Một cánh đồng được chia thành các thửa ruộng hình chữ nhật như Hình 4, Bờ ruộng được thể hiện bởi các đường thẳng màu xanh. Các nốt tròn đỏ trên hình thể hiện các nút giao lộ giữa thửa ruộng, được đánh giá theo tọa độ từ (0,0) đến (D,C). Với mỗi bước nhảy bật xa của mình, An chỉ có thể đi từ nút giao lộ này sang nút giao lộ khác trên bờ ruộng theo một hướng hoặc lên trên hoặc sang phải.
Ảnh
Ứng dụng
Ảnh
Ảnh
Hình 4. Cánh đông với D = 4, C = 3
Hình 5. Minh họa cách đi trên cánh đồng D = 4, C = 3
Ứng dụng
b) Em hãy đọc hiểu và chạy chương trình ở Hình 6 và cho biết chương trình này có giải quyết được bài toán trên hay không.
Ứng dụng
Ảnh
Hình 6. Chương trình giải bài toán đếm số đường đi trên cánh đồng và màn hình kết quả chạy dữ liệu thử nghiệm
Cảm ơn
Thank You
Ảnh