Bài 3: Thực hành thiết kế thuật toán đệ quy - Chuyên đề Tin học 11 Cánh diều

Bài tập 1

Trả lời bài tập 1 trang 16 Chuyên đề Tin học 11 Cánh diều

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

Lời giải chi tiết:

a. Để tìm ước số chung lớn nhất của hai số tự nhiên x và y (x khác 0, y khác 0), ta sử dụng công thức sau:

Với r là số dư cho phép chia x cho y.

Em hãy chạy chương trình ở Hình 1 với một bộ dữ liệu đầu vào (x,y) khác nhau để kiểm thử chương trình.

b. Viết hàm đệ quy UCLN1(x,y) tìm ướ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:

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 tập 2

Trả lời bài tập 2 trang 17 Chuyên đề Tin học 11 Cánh diều

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

Lời giải chi tiết:

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 thông báo lỗi khi thực hiện chương trình 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?

Bài tập 3

Trả lời bài tập 3 trang 17 Chuyên đề Tin học 11 Cánh diều

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

Lời giải chi tiết:

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 sau:

Vận dụng v

Trả lời câu hỏi Vận dụng trang 18 Chuyên đề Tin học 11 Cánh diều

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 2. 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 các thửa ruộng, được đánh theo toạ độ 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 hướng lên hoặc sang phải

Cụ thể là khi đang đứng ở nút giao lộ có toa độ (i, j) bất kì với 0 <i < D , 0 < j< C, với một bước nhảy, An chịc ó thê nhảy tới nút i,j + 1) hoặc nút (j + 1, i). Em hãy xác định giúp An có tất cả bao nhiêu cách đề có thể đi từ nút xuất phát (i,j) khác (D. C) đến nút (D,C) bằng các bước nhảy của mình.

Ví dụ cho cánh đồng với D = 4, C = 3 như hình 5. Giả sử An đang đứng ở nút (2,2), thì để đến được nút (4,3) An có thể đi theo 1 trong 3 cách sau:

1. (2.2) -> (2.3) -> (3.3) -> (4.3)

2. (2.2) -> (3.2) -> (3.3) -> (4.3)

3. (2.2) -> (3.2) -> (3.3) -> (4.3)

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.

Lời giải chi tiết:

Ví dụ cho cánh đồng với D = 4, C = 3 như hình 5. Gỉa sử An đang đứng ở nút (2,2), thì để đến được nút (4,3) An có thể đi theo 1 trong 3 cách sau:

1. (2.2) -> (2.3) -> (3.3) -> (4.3)

2. (2.2) -> (3.2) -> (3.3) -> (4.3)

3. (2.2) -> (3.2) -> (3.3) -> (4.3)

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.