Cho thuật toán:
Function Test(a,b): Integer;
Begin
If (b = a) or (b = 0) then Test:=1
Else Test := Test (a-1,b-1) + Test (a-1,b);
End;
Với a = 21, b = 3. Kết quả nào đúng trong số những kết quả dưới đây:
Trả lời:
Đáp án đúng: B
Để giải bài này, ta cần tính giá trị của `Test(21, 3)` bằng cách sử dụng đệ quy theo thuật toán đã cho.
`Test(21, 3) = Test(20, 2) + Test(20, 3)`
Để tính `Test(20, 2)` và `Test(20, 3)`, ta tiếp tục áp dụng đệ quy:
`Test(20, 2) = Test(19, 1) + Test(19, 2)`
`Test(20, 3) = Test(19, 2) + Test(19, 3)`
Tiếp tục phân tích cho đến khi đạt đến điều kiện dừng (b = a hoặc b = 0):
Nhận thấy rằng hàm này thực chất đang tính tổ hợp chập k của n, tức là C(n, k), hay "n choose k". Trong trường hợp này, ta có C(21, 3).
Công thức tính tổ hợp chập k của n là: C(n, k) = n! / (k! * (n-k)!) hoặc C(n, k) = C(n-1, k-1) + C(n-1, k)
Vậy, `Test(21, 3)` tương ứng với C(21, 3) = 21! / (3! * 18!) = (21 * 20 * 19) / (3 * 2 * 1) = 1330
Vậy đáp án đúng là 1330.
Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!
30 câu hỏi 60 phút