百鸡问题

百鸡问题

输入：所购买的3种鸡的总数目n

输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]

1. void chicken_question(int n,int &k,int g[],int m[],int s[])

2. {

3.     int  a,b,c;

4.     k = 0;  

5.     for (a=0;a<=n;a++){

6.         for (b=0;b<=n;b++){

7.             for (c=0;c<=n;c++) {

8.                 if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) {

9.                     g[k] = a;

10.                     m[k] = b;

11.                     s[k] = c;

12.                     k++;   

13.                 }   

14.             }

15.         }

16.     }

17. }

 

这个算法有三重循环，主要执行时间取决于第7行开始的内循环的循环体的执行次数。外循环的循环体执行n+1次，中间循环的循环体执行(n+1)(n+1)次，内循环的循环体执行(n+1)(n+1)(n+1)次。当n=100时，内循环的循环体执行次数大于100万次。

考虑到n元钱只能买到n/5只公鸡，或n/3只母鸡。因此，有些组合可以不必考虑。而小鸡的只数又与公鸡及母鸡的只数相关，上述的内循环可以省去。

 

改进的百鸡问题

输入：所购买的3种鸡的总数目n

输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]

1. void chicken_problem(int n,int &k,int g[],int m[],int s[])

2. {

3.     int  i,j,a,b,c;

4.     k = 0;

5.     i = n/5;

6.     j = n/3;

7.     for (a=0;a<=i;a++){

8.        for (b=0;b<=j;b++) {

9.             c = n–a–b;

10.             if ((5*a+3*b+c/3==n)&&(c%3==0)) {

11.                 g[k] = a;

12.                 m[k] = b;

13.                 s[k] = c;

14.                 k++;

15.             }

16.         }

17.     }

18. }

 

算法有两重循环，主要执行时间取决于第8行开始的内循环，其循环体的执行次数是(n/5+1)(n/3+1)。当n=100时，内循环的循环体的执行次数为21*34=714次，这和100万次比较起来，仅是原来的万分之七，有重大的改进。

对某类特定问题，在规模较小的情况下，穷举法往往是一个简单有效的方法。