Ta được hai số n và k. Chúng ta cần tìm số mảng có thể được tạo thành bằng cách sử dụng n số có tổng là k.
Số mảng có kích thước N với tổng K là $ \ dbinom {k - 1} {n - 1} $.
Đây là một công thức đơn giản để tìm các mảng số có thể được tạo thành bằng cách sử dụng n phần tử có tổng k. Hãy xem một ví dụ.
Đầu vào
n = 1 k = 2
Đầu ra
1
Mảng duy nhất có thể được hình thành là [2]
Đầu vào
n = 2 k = 4
Đầu ra
3
Các mảng có thể được tạo thành là [1, 3], [2, 2], [3, 1].
Thuật toán
- Khởi tạo các số n và k.
- Viết một hàm để tính giai thừa của một số.
- Bây giờ, hãy viết hàm chính của chúng tôi để tính toán nhị thức như đã thấy ở trên.
- Trả lời câu trả lời.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong C ++
#include <bits/stdc++.h> using namespace std; int factorial(int n) { int result = 1; for (int i = 2; i <= n; i++) { result *= i; } return result; } int getNumberOfArraysCount(int n, int k) { return factorial(n) / (factorial(k) * factorial(n - k)); } int main() { int N = 5, K = 8; cout << getNumberOfArraysCount(K - 1, N - 1) << endl; return 0; }
Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
35