二項係数のprogramm出力入力は

Question

（C++）大きい場合、誤った結果が、私は二項係数を算出するプログラムの開発、作成している：すべてが完璧に正常に動作します（10まで）、小さな入力の場合

#include <iostream> 
#include <string> 
using namespace std; 

int factorial(int num){ 
    int res = 1; 
    for(int i = 1;i <= num; ++i){ 
     res *= i; 
    } 
    return res; 
} 

int binom(int n,int k){ 
    int factorial(int num); 
    int binom_coef; 
    binom_coef = factorial(n)/(factorial(k)*factorial(n-k)); 
    return binom_coef; 
} 

int main(){ 
    int n,k; 
    int binom(int n,int k); 
    try{ 
     cout << "Enter number n:"; 
     cin >> n; 
     cout << "Enter number k:"; 
     cin >> k; 
     if(n < k){ 
      throw -1; 
     } 
     cout << binom(n,k) << "\n"; 

    }catch(int x) 
     cout << "n must be biggger than k"; 

} 

を。しかし、十分に大きなnとk（10以上）を入力すると計算が完全に間違っているので、なぜそれがわからないのですか？

私を助けることができますか？

Answer 1

階乗は本当に速く成長する関数です。 n > 10の階乗はすでにintタイプをオーバーフローしている可能性があります。

実際に

、12! = 479001600

あなたは二項係数のための理論式を適用しているが、あなたは手術の定義を試みる場合は、以下の問題がある可能性があります

10 : 2 = 10!/(2! * 8!) = (10 * 9)/(2 * 1) 

だから何のことができます。 do：[n, n - k)にすべての数値を掛けて、[k, 1)のすべての数値で除算します。あなたが見ることができるように

int bin_coeff(int n, int k) { 
    int res = 1, i = n; 
    while (i > n - k) res *= i--; 
    while (i > 0) res /= i--; 
    return res; 
} 

、あなたは単に大きな数字ではありません 90/2を、実行して 10 : 2を計算します、そしてあなたも、あなたのアルゴリズムのためのより良い効率を得ることができます。