C语言程序设计---穷举法

1、C语言程序设计-穷举法,主讲：张建青 对象：08计1,课程开始的思考题,思考：某个暑假小明携带密码行李箱外出旅游，旅行途中发现自己忘记了开锁的密码，怎么办？,穷举法的思路,穷举算法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。,用穷举算法解决问题，通常可以从两个方面进行分析： 一、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。 二、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。把这些条件描述出来。 只

2、要把这两个方面分析好了，问题自然会迎刃而解。,例 1 ： 我国古代数学家张丘建在算经中出了这样一道题目：鸡翁一，值五钱，鸡母一，值三钱，鸡雏三，值一钱，百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？,分析：这就是穷举法当中的典型例题百钱百鸡问题。题目要我们找出符合条件的鸡翁、鸡母、鸡雏的个数。答案显然是一组数据。首先分析一下问题所涉及的情况。 百钱如果全买公鸡，可以买020只； 百钱如果全买母鸡，可以买033只； 百钱如果全买小鸡，可以买0300只，但百鸡限定最多99只，小鸡数必须是3的倍数； 综上，我们发现公鸡21种买法，母鸡34种，小鸡33种，所以总共面临着21 34 34 = 24276种买法。

3、,分析进入第二步,现在我们已经了解了所有可能的情况，按照穷举法解题的思路，我们需要设计一下正确买法所需满足的条件，假设公鸡数为i，母鸡数为j，小鸡数为k，则得到如下方程：,i *5+j *3+k/3=100,I +j +k=100,百钱,百鸡,编写程序,#include main() int i , j , k; /*准备输出格式*/ printf(“t公鸡t母鸡t小鸡n”); for(i=0;i=20;i+) for(j=0;j=33;j+) for(k=0;k=99;k+=3) if(i+j+k=100 ,我们运行演示一下,小结思考,刚才的百钱百鸡程序在循环次数上有24276次之多，那么有

4、什么办法可以减少循环次数，而又不会遗漏答案呢？,提示,程序利用的是三重循环，想要减少循环次数，那么很显然，可以从以下两个方面思考： 减少i，j，k三个循环中的某一个或者几个的循环次数 减少循环结构的重数，三重变两重或者一重,分析,分析后我们发现第一种思路没前途，因为取值情况的分析很合理，即便可以减少也只是一点点，对总数2万多来说，减少的幅度很不明显。 所以我们考虑第二种思路，减少循环的重数，我们观察方程后发现，其实，三重循环可以变成两重循环。,k=100 - i - j,i *5+j *3+k/3=100,我们将条件方程改变一下：,如此，便不再需要k循环了,改进后的程序,#include ma

5、in() int i , j , k; /*准备输出格式*/ printf(t公鸡t母鸡t小鸡n); for(i=0;i=20;i+) for(j=0;j=33;j+) k=100-i-j; if(i*5+j*3+k/3=100) printf(t%dt%dt%dn ,i ,j ,k); ,我们运行演示一下,发现问题,运行的结果出人意料，答案变多了，很明显多出的答案是不合理的(小鸡的数量) 原因何在？ 分析：在我们减少k循环之后，k的值由表达式100-i-j提供，很显然，它不能保证出来的k是3的倍数。 改善：加入判断k值为3的倍数的条件。,完善后的改进程序,#include main() in

6、t i , j , k; /*准备输出格式*/ printf(t公鸡t母鸡t小鸡n); for(i=0;i=20;i+) for(j=0;j=33;j+) k=100-i-j; if(k%3=0 ,密码箱问题的演示程序,#include main() int i,key; printf(请设定旅行箱的密码(000-999)：); scanf(%d, ,模仿练习,例 2 ： 36 块砖， 36 人搬。男搬 4 ，女搬 3 ，两个小儿抬一砖。要求一次全搬完。问需男、女、小儿各若干（必须都有）？ 请同学们先分析第一步：问题所涉及的情况,分析 ： 题目要我们找出符合条件的男生、女生和小孩的人数。答案显

7、然是一组数据。首先分析一下问题所涉及的情况。对于男生来说，至少要有一人；每个男生可以搬 4 块砖，那么 36 块砖最多 9 个男生足够，共有 9 种不同取值。同样，女生有 12 种不同取值。两个小孩抬一块砖，至少要有两个小孩，最多 36 个，并且小孩的人数必须是个偶数，所以小孩的人数可以取 18 种不同的值。最坏情况下，男生、女生和小孩的人数可以是 9 12 18 1944 种不同组合。,分析第二步：答案满足所需的条件方程,k=36 - i - j,i *4+j *3+k/2=36,注意：k必须是2的倍数,程序,#include main() int i ,j ,k; printf(t男人t女人t孩子n); for(i=1;i=9;i+) for(j=1;j=12;j+) k=36-i-j; if(k%2=0 ,本节内容总结,穷举法问题在解题中要特别注意以下几个方面： 对情况的分析要准确，即在答案范围的分析时不能漏掉答案 对方程的整理后注意某些值的限定，如小鸡必须为3的倍数，