จำนวนอาร์เรย์ขนาด N ที่สมาชิกเป็นจำนวนเต็มบวกและผลรวมเป็น K ใน C++

โจทย์

เราได้รับตัวเลขสองตัว n และ k เราต้องหาจำนวนอาร์เรย์ที่สามารถสร้างได้โดยใช้นตัวเลขซึ่งผลรวมเป็น k

จำนวนอาร์เรย์ขนาด N ที่ผลรวมเป็น K คือ $\dbinom{k - 1}{n - 1}$

นี่เป็นสูตรตรงไปตรงมาสำหรับหาจำนวนอาร์เรย์ที่สามารถสร้างได้โดยใช้นองค์ประกอบซึ่งผลรวมเป็น 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