Hai công thức sau đều được sử dụng để tính số cách chọn k phần tử từ n phần tử
Hai công thức sau đều được sử dụng để tính số cách chọn k phần tử từ n phần tử sau:
Giải Chuyên đề Tin học 11 Bài 1: Khái niệm đệ quy và ví dụ - Cánh diều
Hoạt động 1 trang 6 Chuyên đề Tin học 11: Hai công thức sau đều được sử dụng để tính số cách chọn k phần tử từ n phần tử sau:
Theo em, trong hai công thức (2) và (3), công thức nào là công thức mang tính đệ quy? Em hãy giải thích cho lựa chọn của mình.
Lời giải:
Công thức 2 mang tính đệ quy
Sử dụng công thức ( 2 ) để tiếp tục quá trình tính toán, ta có F(n -1)- F(n - 2)+ F(n - 3), f( n - 2) = F(n - 3) + F(n - 4)... Do đó, nếu cứ gọi đến hàm F như vậy thÌ việc tính toán sẽ không có điểm dừng nên ta phải bỎ sang trường hợp đặc biệt được tính toán sẵn là hàm F tại n = 0 có giá trị 0 và tại n - 1 có giá trị 1. Công thức ( 2) là công thức mang tính đệ quy.
Lời giải Chuyên đề Tin 11 Bài 1: Khái niệm đệ quy và ví dụ hay, ngắn gọn khác: