Bài 2: Thuật toán đệ quy - Chuyên đề Tin học 11 Cánh diều

Câu 1

Trả lời câu hỏi khởi động trang 10 Chuyên đề Tin học 11 Cánh diều

Định nghĩa  .Em hãy đưa ra mô tả đệ quy cho hàm F(n) để tính a­ⁿ.

Lời giải chi tiết:

Mô tả đệ quy cho hàm F(n) để tính a­ⁿ như sau:

{Hàm_đệ_quy} ({Danh_sách_tham_số})

{

{Gọi_lại_hàm_đệ_quy}({Danh_sách_tham_số});

}

Câu 2

Trả lời câu hỏi hoạt động 1 trang 10 Chuyên đề Tin học 11 Cánh diều

Hai chương trình cho trong Hình 1 yêu cầu người sử dụng nhập hai giá trị nguyên avà n từ bàn phím (n >0), rồi gọi hàm power1 (a,n) và power2 (a,n) tương ứng để in ra màn hình giá trị a”. Em hãy đọc cả hai chương trình này và:

a) Cho biết kết quả thu được của hai chương trình khi giá trị của cặp (4, n) nhập vào lần lượt bằng (2, 4) và (3, 6).

b) Nhận xét về sự khác nhau giữa hai hàm powez1 (a,n) và power2 (a,n).

Lời giải chi tiết:

a) Cho biết kết quả thu được của hai chương trình khi giá trị của cặp (4, n) nhập vào lần lượt bằng (2, 4) và (3, 6).

print (z, "mũ", n, "=", power1(2,4))

print (z, "mũ", n, "=", power1(3,6))

b) Nhận xét

Các ngôn ngữ lập trình bậc cao thường cho phép xây dựng các hàm đệ quy, nghĩa là trong thân của bàm có chứa những câu lệnh gọi đến chính nó.

Câu 3

Trả lời câu hỏi hoạt động 2 trang 11 Chuyên đề Tin học 11 Cánh diều

Em hãy:

a) Đọc chương trình ở Hình 3 và cho biết dấu ? trong hàm h(n) cần được thay bằng gì để tính được số lượng cái bắt tay diễn ra trong phòng họp có n người.

b) Chạy chương trình để tính số cái bắt tay khi n = 5 và n = 10.

Lời giải chi tiết:

a) Chương trình ở Hình 3: dấu ? trong hàm h(n) cần được thay như sau để tính được số lượng cái bắt tay diễn ra trong phòng họp có n người:

return 1

else

return h(n-1) + 1 // Gọi đệ quy

b) Chạy chương trình để tính số cái bắt tay nhập lần lượt n = 5 và n = 10 và đọc kết quả xuất hiện trên màn hình.

Luyện tập Câu 1

Trả lời câu hỏi Luyện tập 1 trang 12 Chuyên đề Tin học 11 Cánh diều

Em hãy đọc chương trình ở hình 5 và cho biết kết quả nhận được khi chạy chương trình.

Lời giải chi tiết:

Nhập chương trình trong bảng 1 vào máy tính và đọc kết quả màn hình xuất ra.

Luyện tập Câu 2

Trả lời câu hỏi Luyện tập 2 trang 13 Chuyên đề Tin học 11 Cánh diều

Dãy số Fibonacci được định nghĩa đệ quy như sau:

+ Phần cơ sở: F(w) = 0 nếu n = 0. F(n) = 1 nếu n > 1.

+ Phần đệ quy: F(n) = F (n - 1) + F(n - 2) nếu n >2

Hàm đệ quy F (n) cho trong hình 6s dùng định nghĩa đệ quy ở trên để tính và trả về giá trị của F(n).

a) Em hãy cho biết các dấu ? trong hàm đệ quy F(n) của được thay bằng gì?

b) Hình 7 liệt kê lần lượt I7 bước chương trình sẽ thực hiện luôn khi lời gọi đến F(4) được thực thi. Em hãy đưa ra giải thích bằng lời ý nghĩa của I7 bước đã cho.

Lời giải chi tiết:

a) return 1

else

return F (n - 1)

b) Ý nghĩa của I7 bước đã cho.

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.

Thuật toán đệ quy được cài đặt dưới dạng hàm đệ quy, để xử lí với các đối tượng được định nghĩa đệ quy.

Vận dụng

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

Mẹ An là cô giáo dạy Toán muốn nhờ An in lời một bài hát dạy đếm số cho các em học sinh có định dạng như sau:

Có 20 chiếc kẹo trong hộp các bạm ơi, ta lấy 1 chiếc ra ăn các bạn nhé.

Vậy trong hộp còn 19 chiếc thôi.

Có 19 chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc ra ăn các bạn nhé.

Vậy trong hộp còn 18 chiếc thôi.

...

Có 2 chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc ra ăn các bạn nhé.

Vậy trong hộp còn 1 chiếc thôi.

Còn duy nhất 1 chiếc kẹo trong hộp các bạn ơi, ta lấy nốt chiễc cuối cùng ra ăn các bạn nhé, không còn chiếc kẹo nào trong hộp, ta cùng nhau đi mua thêm kẹo thôi nào

Em hãy giúp An viết hàm đệ quy in_loi_bai_hat (n) với n là số kẹo để có thể in ra lời bài hát như trên nếu gọi hàm in loi bai hat(20)

Lời giải chi tiết:

Hàm đệ quy in_loi_bai_hat (n) với n là số kẹo để có thể in ra lời bài hát như trên nếu gọi hàm in loi bai hat(20):

{Hàm_đệ_quy} ({Danh_sách_tham_số})

{

{Gọi_lại_hàm_đệ_quy}({Danh_sách_tham_số});

}

Câu 7

Trả lời câu hỏi tự kiểm tra trang 14 Chuyên đề Tin học 11 Cánh diều

Trong những câu sau đây, câu nào đúng khi nói về hàm đệ quy?

a) Trong hàm đệ quy chỉ được phép chứa duy nhất một lệnh gọi đến chính nó.

b) Trong hàm đệ quy, trường hợp cơ sở không được phép tiếp tục gọi đệ quy.

c) Hàm đệ quy là hàm mà thân hàm có chứa những lệnh gọi đến chính nó.

đ) Hàm đệ quy được sử dụng để cài đặt thuật toán đệ quy.

e) Trong hàm đệ quy có thể có nhiều hơn một trường hợp cơ sở.

g) Hàm đệ quy không bao giờ dừng nếu không có trường hợp cơ sở.

Lời giải chi tiết:

Những câu sau đây đúng khi nói về hàm đệ quy:

c) Hàm đệ quy là hàm mà thân hàm có chứa những lệnh gọi đến chính nó.

đ) Hàm đệ quy được sử dụng để cài đặt thuật toán đệ quy.

g) Hàm đệ quy không bao giờ dừng nếu không có trường hợp cơ sở.