用浮点类型的,即使结果正确,也应该扔茅坑里。
先分析一下 20! / 10! / 10!
20! = 2432902008176640000,需要
62bits的整数类型进行存储
所以第一种方法有了,就是用
uint64_t 保存中间结果
在计算 20!/10! 时,不需要先算出20!再除以10!,可以直接求 20*19*18*……*11,这样就可以使得中间结果的峰值降低
20*19*18*……*11 = 670442572800,需要
40bits的整数类型进行存储
所以第二种方法有了,还是得用
uint64_t 保存中间结果,但
可计算范围比第一种方法更大了,可喜的进步
我们知道排列组合的结果必然是个整数,即必然有一种方法使得计算中间结果不大于最终的结果
这就得靠知识储备,杨辉三角 其实就是个 组合数列
所以第三种方法有了,利用杨辉三角,这次只需要用
uint32_t 就行了
下面详细讲解一下杨辉三角
C(m,n) 和 C(m,m-n) 的结果是一样的
假设要求 C(5,3),等同于求 C(5,2)。下面是杨辉三角矩阵
1, 0,
0,
0, 0, 0, 0, ……
1, 1,
0,
0, 0, 0, 0, ……
1, 2,
1,
0, 0, 0, 0, ……
1, 3,
3,
1, 0, 0, 0, ……
1, 4,
6,
4, 1, 0, 0, ……
1, 5,
10, 10, 5, 1, 0, ……
看到第5行第2列了,它就是C(5,2)的结果
看,多么简单呀,简单到我与其用文字来描述算法,还不如直接贴代码
程序代码:
unsigned C( unsigned m, unsigned n )
{
if( m < n )
return 0;
n = n<m-n?n:m-n;
unsigned* buf = (unsigned*)calloc( n+1, sizeof(*buf) );
buf[0] = 1;
for( unsigned r=0; r!=m; ++r )
for( unsigned c=n; c!=0; --c )
buf[c] += buf[c-1];
unsigned r = buf[n];
free( buf );
return r;
}