Module: kết hợp


Problem

1 /3


Số lượng kết hợp

Theory Click to read/hide

Hỗn hợp của n phần tử bởi k là hợp chất có thể tạo thành từ n phần tử, thu k phần tử trong mỗi liên kết; trong khi các kết nối khác nhau chỉ bởi chính các phần tử (sự khác biệt về thứ tự sắp xếp của chúng không được tính đến).
 
Ví dụ: các kết hợp sau có thể được tạo từ 3 phần tử (a,b,c)(a,b,c) 2 mỗi phần tử: ab,ac,bc.
 
Số lượng tất cả các kết hợp có thể được tạo thành từ n phần tử bởi k được biểu thị bằng ký hiệu  và được tính theo công thức:
 
Có hai cách để tìm số lượng kết hợp 
 
1. Tìm n!, k!, (n – k)! và theo công thức trên, chúng tôi tính toán số lượng, nhưng từ – do có thể tràn, phương pháp này có thể được sử dụng với n <= 12.
 
2. Với lập trình động.
 
DP sẽ giống như tam giác Pascal, với các số ở trên cùng và các cạnh, và mỗi số bằng tổng của hai số ở trên nó.





Hàm đếm số lượng kết hợp sử dụng lập trình động trong O(n^2 ):

int C(int n, int nhịp > k)
{
vectơ<vector<int> > dp(n + 1, vector<int>(n + 1, 1)); // Tạo mảng dp có kích thước (n + 1, n + 1)
cho (int i = 0; i <= n; i++) // Điền vào dòng thứ i của mảng
{
cho (int j = 1; j < i; j++)
{
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; //tính lại vị trí (i;j) qua (i - 1; j - 1) và (i - 1; j) 
}
}
return dp[n][k]; //giá trị trả về 
}

Problem

Cho các số nk (\(0 <= k <= n\),  ; \(0< n<=12\)) tính số tổ hợp  \(C_n^k\) < /span>.
 

 

Ví dụ
<đầu>
# Đầu vào Đầu ra
1 2 8 28