เราได้รับตัวเลขสองตัว n และ k เราต้องหาจำนวนอาร์เรย์ที่สามารถสร้างได้โดยใช้ตัวเลข n ซึ่งมีผลรวมเป็น k
จำนวนอาร์เรย์ขนาด N ที่มีผลรวม K คือ $\dbinom{k - 1}{n - 1}$.
สูตรนี้เป็นสูตรที่ตรงไปตรงมาในการหาอาร์เรย์ตัวเลขที่สามารถเกิดขึ้นได้โดยใช้องค์ประกอบ n ซึ่งมีผลรวม k มาดูตัวอย่างกัน
ป้อนข้อมูล
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
