Thuật toán đệ quy dưới đây tính:
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;
Trả lời:
Đáp án đúng: D
Đoạn code trên thực chất tính tổ hợp chập b của a, ký hiệu là C(a, b).
Giải thích:
* **Trường hợp cơ sở:**
* `If (b = a) or (b = 0) then Test:=1`: Điều này tương ứng với C(a, a) = 1 và C(a, 0) = 1. Tức là, nếu chọn a phần tử từ a phần tử hoặc chọn 0 phần tử từ a phần tử, thì chỉ có 1 cách.
* **Bước đệ quy:**
* `Else Test := Test (a-1,b-1) + Test (a-1,b)`: Điều này tương ứng với công thức C(a, b) = C(a-1, b-1) + C(a-1, b).
Công thức này có nghĩa là, để chọn b phần tử từ a phần tử, ta có hai trường hợp:
1. Chọn phần tử thứ a, khi đó ta cần chọn b-1 phần tử từ a-1 phần tử còn lại (C(a-1, b-1)).
2. Không chọn phần tử thứ a, khi đó ta cần chọn b phần tử từ a-1 phần tử còn lại (C(a-1, b)).
Như vậy, hàm `Test(a, b)` tính toán chính xác tổ hợp chập b của a.
