C++

Question

'daki Newton binomial katsayısıyla ilgili sorun Newton Binom Katsayıları programımla ilgili bir sorun yaşıyorum. Öncelikle negatif sayıları yazdırdı ancak faktöriyel işlev türünü unsigned long long olarak değiştirmek, sorunu negatif sayılarla yazdırmak gibi görünüyordu. Program maksimum n = 20 için çalışıyor, yukarıda sıfırları, birleri ve ikişer yazdırmaya başlar. Bunu nasıl düzelteceğimize dair hiçbir fikrim yok ve umarım birileri bana yardım edebilir.

#include <iostream> 
using namespace std; 

unsigned long long factorial(int n) { 
    if (n == 0) { 
     return 1; 
    } 
    return n*factorial(n - 1); 
} 

void Binom(int n ,int k) { 
    unsigned long long factorialResult; 
    if (k > n) { 
     return; 
    } 
    factorialResult = factorial(n) /(factorial(k) * factorial(n - k)); 
    cout << factorialResult << " "; 
    if (n >= k) { 
     Binom(n, k + 1); 
    } 
} 

Answer 1

Faktörler genellikle çok büyüktür, bu nedenle burada yalnızca tamsayı taşması vardır. Bu sorunu gidermek için, örneğin, faktöriyel'dir kullanmayan C(n, k) hesaplama başka algoritmayı uygulamak: Burada aşağıdaki tekrarlayan kural kullanılır

unsigned long long C(unsigned n, unsigned k) { 
    if (n == k || k == 0) { 
     return 1; // There's exactly one way to select n or 0 objects out of n 
    } 
    return C(n - 1, k - 1) * n/k; 
} 

: C(n, k) = C(n - 1, k - 1) * n/k. C(n, k) = n!/(k! (n-k)!) = (n/k) * (n-1)!/((k-1)!(n-1-k+1)!)'dan beri kanıtlamak çok kolay.