Combinations
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 7499 | Accepted: 3509 |
Description
Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large. Challenges are the stuff of contests. Therefore, you are to make just such a computation given the following:
GIVEN: 5 <= N <= 100; 5 <= M <= 100; M <= N
Compute the EXACT value of: C = N! / (N-M)!M!
You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long. For the record, the exact value of 100! is:
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621, 468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253, 697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000
GIVEN: 5 <= N <= 100; 5 <= M <= 100; M <= N
Compute the EXACT value of: C = N! / (N-M)!M!
You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long. For the record, the exact value of 100! is:
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621, 468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253, 697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000
Input
The input to this program will be one or more lines each containing zero or more leading spaces, a value for N, one or more spaces, and a value for M. The last line of the input file will contain a dummy N, M pair with both values equal to zero. Your program
should terminate when this line is read.
should terminate when this line is read.
Output
The output from this program should be in the form:
N things taken M at a time is C exactly.
N things taken M at a time is C exactly.
Sample Input
100 6 20 5 18 6 0 0
Sample Output
100 things taken 6 at a time is 1192052400 exactly. 20 things taken 5 at a time is 15504 exactly. 18 things taken 6 at a time is 18564 exactly.
Source
poj上的思维问题。
就是求组合Cnm
队友们竟然提供了三种方法。
1采用 __int64 利用乘一个分子和下面所有的分母进行约分,约分过的就不用继续约分了。这样能有效的减少存储的位数。
#include<stdio.h> int a[120]; int main() { __int64 n,m,i,j,sum=1,num; while(scanf("%I64d %I64d",&n,&m)) { if(n==0&&m==0)break; for(i=1;i<=110;i++) a[i]=0; sum=1; for(i=n-m+1;i<=n;i++) { num=i; for(j=2;j<=m;j++) { if(a[j]==1)continue; if(num%j==0){num/=j;a[j]=1;} } sum*=num; } for(j=2;j<=m;j++) { if(a[j]==0)sum/=j; } printf("%I64d things taken %I64d at a time is %I64d exactly.\n",n,m,sum); } }
2 利用double来存储长位数,这样知道了分子和分母的总共乘积,就可以求出结果了。
#include<stdio.h> int main() { int n,m,i; double sum1=1,sum2=1; while(scanf("%d %d",&n,&m)!=EOF) { if(n==0&&m==0)break; sum1=1; sum2=1; for(i=n-m+1;i<=n;i++) sum1*=double(i); for(i=1;i<=m;i++) sum2*=double(i); printf("%d things taken %d at a time is %.0lf exactly.\n",n,m,sum1/sum2); } }
3 杨辉三角 Cnm=Cn-1m+Cn-1m-1
#include<stdio.h> __int64 a[110][110]; int main() { int i,j; for(i=0;i<=101;i++) a[i][0]=1; for(i=1;i<=101;i++) a[i][i]=1; for(i=2;i<=101;i++) for(j=1;j<i;j++) { a[i][j]=a[i-1][j]+a[i-1][j-1]; } while(scanf("%d %d",&i,&j)!=EOF) { if(i==0&&j==0)break; printf("%d things taken %d at a time is %I64d exactly.\n",i,j,a[i][j]); } }