【实训3-24】实例详解(六)百钱买百鸡问题
(总分32)


 【实训目的】实例详解(六)百钱买百鸡问题   

【第 1 步】实训内容介绍

实训内容介绍
用循环语句列出所有可能的组合,输出符合要求的组合
优化,提高效率
再优化,提高效率
再次优化,提高效率
实训结束

【Jitor 校验第 1 步】我已阅读实训内容介绍 // 送分题。直接点击。

 

 

【第 2 步】用循环语句列出所有可能的组合,输出符合要求的组合

 注意:本次实训将严格检查代码,应该与教材上的代码严格一致,一步一步完成每个步骤。
  1、本实训使用项目 cpp3 中的 cpp3code.cpp 源代码文件,如果不存在,则先创建项目,然后创建源代码文件。
 2、将下述代码复制到 cpp3code 中:

#include <iostream.h>
void main(void) {
         int count =0;
         int i, j, k;
// 在这里补写代码

         cout << "一共循环了 {" << count << "} 次\n";
}

 这个代码列出了所有买 100 只鸡的各种组合,直接运行它(可能需要 1-2 分钟),看看循环了多少次,就是説有多少种组合。
 然后修改这个代码,找出这些组合中满足给定条件的组合,一共是 4 个组合满足条件。
 代码见简明教程【例3-24】第 1 步代码,运行结果如下:

2601:公鸡={0}, 母鸡={25}, 小鸡={25}
42701:公鸡={4}, 母鸡={18}, 小鸡={18}
82801:公鸡={8}, 母鸡={11}, 小鸡={11}
122901:公鸡={12}, 母鸡={4}, 小鸡={4}
一共循环了 {1030301} 次
Press any key to continue

 从结果中看到,一共循环了 103 万次。

代码如下:
// 从下一行开始复制。
#include <iostream.h>
void main(void){
         int count=0;
         int i,j,k;
         for(i=0;i<=100;i++){
                  for(j=0;j<=100;j++){
                           for(k=0;k<=100;k++){
                                    count++;
                                    if(5*i+3*j+k/3==100 && k%3==0 && i+j+k==100){
                                             cout<<count<<":公鸡={"<<i<<"},母鸡={"<<j<<"},小鸡={"<<k<<"}\n";
                                    }
                           }
                  }
         }
         cout << "一共循环了 {" << count << "} 次\n";
}
// 一直复制到上一行结束。

【Jitor 校验第 2 步】    // 复制上面的代码到VC++ 6.0,保存并运行。点击。

 

 

【第 3 步】优化,提高效率

 前面的代码有许多组合是没有意义的,例如买了 15 只公鸡后,就不可能买 90 只母鸡了。 因此可以优化代码,减少循环的次数。
 代码见简明教程【例3-24】第 2 步代码,运行结果如下:

2301:公鸡={0}, 母鸡={25}, 小鸡={25}
21674:公鸡={4}, 母鸡={18}, 小鸡={18}
39486:公鸡={8}, 母鸡={11}, 小鸡={11}
55801:公鸡={12}, 母鸡={4}, 小鸡={4}
一共循环了 {176851} 次
Press any key to continue

 从结果中看到,循环次数降到 17 万次。

代码如下:
// 从下一行开始复制。
#include <iostream.h>
void main(void){
         int count=0;
         int i,j,k;
         for(i=0;i<=100;i++){
                  for(j=0;j<=100-i;j++){
                           for(k=0;k<=100-i-j;k++){
                                    count++;
                                    if(5*i+3*j+k/3==100 && k%3==0 && i+j+k==100){
                                             cout<<count<<":公鸡={"<<i<<"},母鸡={"<<j<<"},小鸡={"<<k<<"}\n";
                                    }
                           }
                  }
         }
         cout << "一共循环了 {" << count << "} 次\n";
}
// 一直复制到上一行结束。

【Jitor 校验第 3 步】          // 复制上面的代码到VC++ 6.0,保存并运行。点击。

 

 

【第 4 步】再优化,提高效率

 一旦公鸡和母鸡的数量定了下来,小鸡的数量就是 100 减去公鸡和母鸡的数量,这样又可以优化代码。
 代码见简明教程【例3-24】第 3 步代码,运行结果如下:

26:公鸡={0}, 母鸡={25}, 小鸡={25}
417:公鸡={4}, 母鸡={18}, 小鸡={18}
792:公鸡={8}, 母鸡={11}, 小鸡={11}
1151:公鸡={12}, 母鸡={4}, 小鸡={4}
一共循环了 {5151} 次
Press any key to continue

 从结果中看到,循环次数降到 5 千多次。

代码如下:
// 从下一行开始复制。
#include <iostream.h>
void main(void){
         int count=0;
         int i,j,k;
         for(i=0;i<=100;i++){
                  for(j=0;j<=100-i;j++){
                           k = 100-i-j;
                           count++;
                           if(5*i+3*j+k/3==100&&k%3==0){
                                    cout<<count<<":公鸡={"<<i<<"},母鸡={"<<j<<"},小鸡={"<<k<<"}\n";
                           }
                  }
         }
         cout << "一共循环了 {" << count << "} 次\n";
}
// 一直复制到上一行结束。

【Jitor 校验第 4 步】          // 复制上面的代码到VC++ 6.0,保存并运行。点击。

 

 

【第 5 步】再次优化,提高效率

 因为公鸡的价格是 5 块钱一只,因此,最多只能买 100/5 = 20只公鸡,这样又可以优化代码。
 代码见简明教程【例3-24】第 4 步代码,运行结果如下:

26:公鸡={0}, 母鸡={25}, 小鸡={25}
417:公鸡={4}, 母鸡={18}, 小鸡={18}
792:公鸡={8}, 母鸡={11}, 小鸡={11}
1151:公鸡={12}, 母鸡={4}, 小鸡={4}
一共循环了 {1911} 次
Press any key to continue

 从结果中看到,循环次数降到少于 2 千次。

代码如下:
// 从下一行开始复制。
#include <iostream.h>
void main(void){
         int count=0;
         int i,j,k;
         for(i=0;i<=100/5;i++){
                  for(j=0;j<=100-i;j++){
                           k = 100-i-j;
                           count++;
                           if(5*i+3*j+k/3==100&&k%3==0){
                                    cout<<count<<":公鸡={"<<i<<"},母鸡={"<<j<<"},小鸡={"<<k<<"}\n";
                           }
                  }
         }
         cout << "一共循环了 {" << count << "} 次\n";
}
// 一直复制到上一行结束。

【Jitor 校验第 5 步】          // 复制上面的代码到VC++ 6.0,保存并运行。点击。

 

 

【第 6 步】实训总结

 本次实训学习了循环的优化,循环次数从 103 万,降到 17 万,再降到 5 千,最后再降到少于 2 千次。
 针对这个问题,循环次数还可以下降到 644 次,请尝试一下。 因此,写一个好的代码,可以大大提高程序的性能。 

【Jitor 校验第 6 步】我已阅读实训总结 // 送分题。直接点击。

 

仍有疑问 ? 联系QQ 9429444(陈海云) : 返回首页