資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中大小為 N 且元素為正整數且和為 K 的陣列個數
給定兩個數字 n 和 k。我們需要找到可以使用 n 個數字形成的陣列的個數，這些陣列的和為 k。
大小為 N 且和為 K 的陣列的個數為 $\dbinom{k - 1}{n - 1}$。
這是一個查詢可以使用 n 個元素形成的陣列個數的簡單公式。讓我們看一個例子。
輸入
n = 1 k = 2
輸出
1
唯一可以形成的陣列是 [2]
輸入
n = 2 k = 4
輸出
3
可以形成的陣列是 [1, 3]、[2, 2]、[3, 1]。
演算法
- 初始化數字 n 和 k。
- 編寫一個函式來計算數字的階乘。
- 現在，編寫我們的主函式來計算如上所示的二項式係數。
- 返回答案。
實現
以下是上述演算法在 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;
}輸出
如果執行以上程式碼，則會得到以下結果。
35
更新於: 2021-10-26
322 次瀏覽
廣告