2

私は数の順列を次のように計算しました：-

nPr = n!/(n-r)!

ここで、nとrが与えられます。 1<= n,r <= 100

i find p=(n-r)+1
and 
for(i=n;i>=p;i--)
  multiply digit by digit and store in array.

しかし、どのようにnCr = n！/ [r！*（nr）！]同じ範囲の場合。

私は次のように再帰を使用してこれを行いました：-

#include <stdio.h>
typedef unsigned long long i64;
i64 dp[100][100];
i64 nCr(int n, int r)
{
if(n==r) return dp[n][r] = 1;
if(r==0) return dp[n][r] = 1;
if(r==1) return dp[n][r] = (i64)n;
if(dp[n][r]) return dp[n][r];
return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

int main()
{
int n, r;
while(scanf("%d %d",&n,&r)==2)
{
    r = (r<n-r)? r : n-r;
    printf("%llu\n",nCr(n,r));
}
return 0;
}

ただし、n <= 100の範囲であり、これはn>60では機能しません。

4

1 に答える 1

2

BigIntegerタイプのクラスを使用して、大きな数値を表すことを検討してください。BigIntegerは、JavaおよびC＃（.NET Frameworkのバージョン4以降）で使用できます。あなたの質問から、あなたはC ++を使用しているようです（これは常にタグとして追加する必要があります）。したがって、こことここで、使用可能なC++BigIntegerクラスを探してみてください。

私が提案した二項係数を計算するための最良の方法の1つは、MarkDominusによるものです。他のいくつかの方法よりも、NとKの値が大きくなることでオーバーフローする可能性ははるかに低くなります。

static long GetBinCoeff(long N, long K)
{
   // This function gets the total number of unique combinations based upon N and K.
   // N is the total number of items.
   // K is the size of the group.
   // Total number of unique combinations = N! / ( K! (N - K)! ).
   // This function is less efficient, but is more likely to not overflow when N and K are large.
   // Taken from:  http://blog.plover.com/math/choose.html
   //
   if (K > N) return 0;
   long r = 1;
   long d;
   for (d = 1; d <= K; d++)
   {
      r *= N--;
      r /= d;
   }
   return r;
}

すべての長い定義をBigIntに置き換えるだけで、準備が整います。

于 2013-01-28T14:22:27.400 に答える