Thuật toán tính tổ hợp - Cách tính tổ hợp trong C++

Hôm nay mình sẽ giới thiệu đến các bạn cách tính tổ hợp trong c++ bằng phương pháp đệ quy và phương pháp lặp. Nhưng trước tiên ta cùng tìm hiểu tổ hợp là gì nhé ?

Trong Toán học, tổ hợp là cách chọn những phần tử từ một nhóm lớn hơn mà không phân biệt thứ tự. Ví dụ chọn 2 trong 3 phần tử {1, 2, 3 } sẽ có ba cách chọn đó là: {1, 2}, {1, 3}, {2, 3}. Các bạn có thể tham khảo tại đây để hiểu rõ hơn.

Cách tính tổ hợp trong c++ bằng đệ quy

Ta có công thức truy hồi như sau: $C^k_n + C^{k+1}_n = C^{k+1}_{n+1}$

Với các tính chất sau:

$C^0_n=C^n_n = 1$
$C^1_n = C^{n-1}_n = n$

Từ công thức truy hồi trên ta sẽ dễ dàng viết được một hàm đệ quy để tính tổ hợp như sau:

#include<iostream>
using namespace std;
int C(int k, int n) {
	if (k == 0 || k == n) return 1;
	if (k == 1) return n;
	return C(k - 1, n - 1) + C(k, n - 1);
}
int main(){
	int n, k;
	cout << "Nhap k: ";
	cin >> k;
	cout << "Nhap n: ";
	cin >> n;
	cout << "To hop bang: " << C(k, n);
	system("pause");
	return 0;
}

#include<iostream>

using namespace std;

int C(int k, int n) {

if (k == 0 || k == n) return 1;

if (k == 1) return n;

return C(k - 1, n - 1) + C(k, n - 1);

}

int main(){

int n, k;

cout << "Nhap k: ";

cin >> k;

cout << "Nhap n: ";

cin >> n;

cout << "To hop bang: " << C(k, n);

system("pause");

return 0;

}

Sau khi chạy chương trình thì chúng ta sẽ có kết quả sau

Nhap k: 3
Nhap n: 5
To hop bang: 10

Nhap k: 3

Nhap n: 5

To hop bang: 10

Các bạn có thể thấy ở trên mình dùng ba điểm neo để làm điều kiện dừng đó là:

Tại k bằng 0 hoặc k bằng n thì ta phải return 1
Tại k bằng 1 thì ta return n

Hoàn toàn đúng với các tính chất mình đã trình bày ở trên nhé ^_^

Nhưng nhược điểm của phương pháp đệ quy này lại là tốc độ. không tin thì bạn cứ thử nhập k và n lớn xí nhé !

Cách tính tổ hợp trong c++ bằng phương pháp lặp

Số các tổ hợp chập k của phần tử:

Với công thức trên thì ta chỉ cần viết một hàm tính giai thừa là xong rồi phải không nào. Chúng ta cùng bắt đầu nhé

#include<iostream>
using namespace std;
long long gt(int n) {
	long long s = 1;
	for (int i = 1; i <= n; i++)
		s *= i;
	return s;
}
long long C(int k, int n) {
	return  gt(n) / (gt(k)*gt(n - k));
}
int main(){
	int n, k;
	cout << "Nhap k: ";
	cin >> k;
	cout << "Nhap n: ";
	cin >> n;
	cout << "To hop bang: " << C(k, n);
	system("pause");
	return 0;
}

#include<iostream>

using namespace std;

long long gt(int n) {

long long s = 1;

for (int i = 1; i <= n; i++)

s *= i;

return s;

}

long long C(int k, int n) {

return gt(n) / (gt(k)*gt(n - k));

}