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

目录后退前进结束江苏省高淳职教中心校张建青C语言程序设计---穷举法主讲：张建青对象：08计1目录后退前进结束江苏省高淳职教中心校张建青课程开始的思考题思考：某个暑假小明携带密码行李箱外出旅游，旅行途中发现自己忘记了开锁的密码，怎么办？目录后退前进结束江苏省高淳职教中心校张建青穷举法的思路穷举算法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。目录后退前进结束江苏省高淳职教中心校张建青用穷举算法解决问题，通常可以从两个方面进行分析：一、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。二、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。把这些条件描述出来。只要把这两个方面分析好了，问题自然会迎刃而解。目录后退前进结束江苏省高淳职教中心校张建青例1：我国古代数学家张丘建在《算经》中出了这样一道题目：鸡翁一，值五钱，鸡母一，值三钱，鸡雏三，值一钱，百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？分析：这就是穷举法当中的典型例题百钱百鸡问题。题目要我们找出符合条件的鸡翁、鸡母、鸡雏的个数。答案显然是一组数据。首先分析一下问题所涉及的情况。–百钱如果全买公鸡，可以买0~20只；–百钱如果全买母鸡，可以买0~33只；–百钱如果全买小鸡，可以买0~300只，但百鸡限定最多99只，小鸡数必须是3的倍数；综上，我们发现公鸡21种买法，母鸡34种，小鸡33种，所以总共面临着21×34×34=24276种买法。目录后退前进结束江苏省高淳职教中心校张建青分析进入第二步现在我们已经了解了所有可能的情况，按照穷举法解题的思路，我们需要设计一下正确买法所需满足的条件，假设公鸡数为i，母鸡数为j，小鸡数为k，则得到如下方程：i*5+j*3+k/3==100I+j+k==100百钱百鸡目录后退前进结束江苏省高淳职教中心校张建青编写程序#includestdio.hmain(){inti,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&&i*5+j*3+k/3==100)printf(“\t%d\t%d\t%d\n”,i,j,k);}我们运行演示一下目录后退前进结束江苏省高淳职教中心校张建青小结思考刚才的百钱百鸡程序在循环次数上有24276次之多，那么有什么办法可以减少循环次数，而又不会遗漏答案呢？目录后退前进结束江苏省高淳职教中心校张建青提示程序利用的是三重循环，想要减少循环次数，那么很显然，可以从以下两个方面思考：1.减少i，j，k三个循环中的某一个或者几个的循环次数2.减少循环结构的重数，三重变两重或者一重目录后退前进结束江苏省高淳职教中心校张建青分析分析后我们发现第一种思路没前途，因为取值情况的分析很合理，即便可以减少也只是一点点，对总数2万多来说，减少的幅度很不明显。所以我们考虑第二种思路，减少循环的重数，我们观察方程后发现，其实，三重循环可以变成两重循环。目录后退前进结束江苏省高淳职教中心校张建青k=100-i-ji*5+j*3+k/3==100我们将条件方程改变一下：如此，便不再需要k循环了目录后退前进结束江苏省高淳职教中心校张建青改进后的程序#includestdio.hmain(){inti,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%d\t%d\t%d\n,i,j,k);}}我们运行演示一下目录后退前进结束江苏省高淳职教中心校张建青发现问题•运行的结果出人意料，答案变多了，很明显多出的答案是不合理的(小鸡的数量)•原因何在？•分析：在我们减少k循环之后，k的值由表达式100-i-j提供，很显然，它不能保证出来的k是3的倍数。•改善：加入判断k值为3的倍数的条件。目录后退前进结束江苏省高淳职教中心校张建青完善后的改进程序#includestdio.hmain(){inti,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&&i*5+j*3+k/3==100)printf(\t%d\t%d\t%d\n,i,j,k);}}目录后退前进结束江苏省高淳职教中心校张建青密码箱问题的演示程序#includestdio.hmain(){inti,key;printf(请设定旅行箱的密码(000-999)：);scanf(%d,&key);printf(\n你的旅行箱密码是：);for(i=0;i=999;i++)if(i==key)if(i10)printf(00%d\n,i);elseif(i100)printf(0%d\n,i);elseprintf(%d\n,i);}目录后退前进结束江苏省高淳职教中心校张建青模仿练习例2：36块砖，36人搬。男搬4，女搬3，两个小儿抬一砖。要求一次全搬完。问需男、女、小儿各若干（必须都有）？请同学们先分析第一步：问题所涉及的情况目录后退前进结束江苏省高淳职教中心校张建青分析：题目要我们找出符合条件的男生、女生和小孩的人数。答案显然是一组数据。首先分析一下问题所涉及的情况。对于男生来说，至少要有一人；每个男生可以搬4块砖，那么36块砖最多9个男生足够，共有9种不同取值。同样，女生有12种不同取值。两个小孩抬一块砖，至少要有两个小孩，最多36个，并且小孩的人数必须是个偶数，所以小孩的人数可以取18种不同的值。最坏情况下，男生、女生和小孩的人数可以是9×12×18＝1944种不同组合。目录后退前进结束江苏省高淳职教中心校张建青分析第二步：答案满足所需的条件方程k=36-i-ji*4+j*3+k/2==36注意：k必须是2的倍数目录后退前进结束江苏省高淳职教中心校张建青程序#includestdio.hmain(){inti,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&&i*4+j*3+k/2==36)printf(\t%d\t%d\t%d\n,i,j,k);}}目录后退前进结束江苏省高淳职教中心校张建青本节内容总结穷举法问题在解题中要特别注意以下几个方面：1.对情况的分析要准确，即在答案范围的分析时不能漏掉答案2.对方程的整理后注意某些值的限定，如小鸡必须为3的倍数，在编写程序中要反映出来目录后退前进结束江苏省高淳职教中心校张建青课后作业1.换零钞问题：一张100元，换成20，10，5，1面值的零钞，每种至少一张，共有哪些换法，总计多少种换法？2.从1到100的自然数中，每次取出两个数，要使它们的和大于100，共有哪些取法，总计多少种取法？