Chương trình C++ tính tổ hợp nCr bằng đệ quy

Tính tổ hợp chập r của n (nCr) sử dụng công thức truy hồi: C(n,r) = (n/r) * C(n-1, r-1) với điều kiện cơ sở C(n,0) = 1.

Thuật toán

Hàm CalCombination(n, r):
  Nếu r > 0: trả về (n/r) * CalCombination(n-1, r-1).
  Ngược lại: trả về 1.

Ví dụ mã nguồn

#include <iostream>
using namespace std;

long long CalCombination(long long n, long long r) {
    if (r > 0)
        return (n / r) * CalCombination(n-1, r-1);
    return 1;
}

int main() {
    long long n, r;
    cout << "Nhap n: "; cin >> n;
    cout << "Nhap r: "; cin >> r;
    cout << "nCr = " << CalCombination(n, r) << endl;
    return 0;
}

Đầu ra mẫu

Nhap n: 7
Nhap r: 6
nCr = 7