我乘车时想到的计算组合数算法

文化机器人

如题，抛个砖，大家拿玉砸吧，用的递归

int ComputeComb(int down, int up) {     if(up > down || down< 0)     {         fprintf(stderr,"\nError Input\n");         return EOF;     }     if(up == 0 || up == down)     {         return 1;     }     return (ComputeComb(down-1,up) + ComputeComb(down-1,up-1)); }

[ 本帖最后由 文化机器人 于 2009-2-22 17:36 编辑 ]

emacsnw

是 int 还是 int *？

langue

其实可以用 int &

文化机器人

sorry,誊写出怪了
在车上手写的，誊写时还在想配一个main
就想出了妖蛾子；改完了，一般计算组合是用什么算法？

cobras

c(m, n) = n!/(m!*(n - m)!)

1. 
   
2. int factorial(int n) /* be carefull of overflow */
   
3. {
   
4.     int val;
   
5. 
   
6.     val = 1;
   
7.     for (; n > 1; n--) {
   
8.         val *= n;
   
9.     }
   
10.     return val;
    
11. }
    
12. 
    
13. int combine(int m, int n)
    
14. {
    
15.     return factorial(n)/(factorial(m)*factorial(n-m));
    
16. }
    

复制代码

[ 本帖最后由 cobras 于 2009-2-22 17:54 编辑 ]

文化机器人

继续贴代码

#include<stdio.h> int ComputeComb(int down, int up) {     if(up > down || down< 0)     {         fprintf(stderr,"\nError Input\n");         return EOF;     }     if(up == 0 || up == down)     {         return 1;     }     return (ComputeComb(down-1,up) + ComputeComb(down-1,up-1)); } int main(int argc, char *argv[]) {     int answer,sta num[2];     if(argc != 3)     {         fprintf(stderr"\nArgument Error\n");         exit(1);     }          sta = sscanf(argv[1],"%d",num);     if(!sta)     {         fprintf(stderr,"\nNumber 1 Error!(should be a integer)\n");         exit(2);     }     sta = sscanf(argv[2],"%d",num+1);     if(!sta)     {         fprintf(stderr,"\nNumber 2 Error!(should be a integer)\n");         exit(3);     }     answer = ComputeComb(num[0],num[1]);     if(answer == EOF)     {         fprintf(stderr,"\nNumbers range Error!\n");         exit(4)     }     printf("\nthe Number of Combinations is %d.\n",answer); }

[ 本帖最后由 文化机器人 于 2009-2-22 17:57 编辑 ]

文化机器人

5楼的用这样不就优化了：

1. int Permutation(int high, int low)
   
2. {
   
3.         int val:
   
4. 
   
5.         val = 1;
   
6.         for(; low>0;low--)
   
7.         {
   
8.                 val *= high--
   
9.         }
   
10. 
    
11. int combine(int m, int n)
    
12. {
    
13.     return Permutation(n,m)/Permutation(m,m));
    
14. }
    
15. }

复制代码

[ 本帖最后由 文化机器人 于 2009-2-22 18:13 编辑 ]

cugb_cat

这个速度应该很慢吧，而且很容易溢出。

emacsnw

当n大一点的时候，比较有用的是求它的log.

drowsyboy

不妨考虑一种比较好，而且不容易溢出的方法：就是对数进行素数分解，也就是说 n = p1^n1*p2^n2*......

这样，C(m,n) = (n-m+1)*...*n/(1*2*...*m) 首先对分子所有的乘数进行素数分解，然后相加；在对分母的所有乘数进行素数分解，然后相加-----两者分解和之差，就得到结果了。