如何计算大数的组合 [英] how to calculate combination of large numbers
问题描述
我计算出的数字排列为:-
I calculated permutation of numbers as:-
nPr = n!/(nr)!
其中n和r是给定的。
1 <= n,r< = 100
where n and r are given .
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)!]的范围相同。?
But how will I calculate the nCr = n!/[r! * (n-r)!] for the same range.?
我使用递归方法如下:-
I did this using recursion as follow :-
#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。
but range for n <=100 , and this is not working for n>60 .
推荐答案
考虑使用BigInteger类型的类来表示您的大数字。 BigInteger在Java和C#(。NET Framework的4+版本)中可用。从您的问题来看,您似乎正在使用C ++(应始终将其添加为标记)。因此,尝试在此处和此处,以获取可用的C ++ BigInteger类。
Consider using a BigInteger type of class to represnet your big numbers. BigInteger is available in Java and C# (version 4+ of the .NET Framework). From your question, it looks like you are using C++ (which you should always add as a tag). So try looking here and here for a usable C++ BigInteger class.
最好的之一我见过建议的用于计算二项式系数的方法是 Mark Dominus 。与其他方法相比,N和K值较大时,溢出的可能性要小得多。
One of the best methods for calculating the binomial coefficient I have seen suggested is by Mark Dominus. It is much less likely to overflow with larger values for N and K than some other methods.
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,您就应该做好了。
Just replace all the long definitions with BigInt and you should be good to go.
这篇关于如何计算大数的组合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!