穷举算法分析报告.docx

穷举算法分析报告1 什么是穷举算法穷举算法：穷举算法就是将一个事件所有可能的结果全部列举出来，直到得到自己所需要的正确结果。又叫枚举法。对于我们计算机运行，穷举算法是一个很好的算法设计方法，其运用循环的方式解决问题，但是运用穷举算法解决问题缺点就是当问题较为复杂的时候，使用的时间过长。2 穷举算法存在的主要问题及其优化方案1.主要问题：穷举算法具有准确性、全面性和算法简单的优点；但是也存在一定缺点，比如说计算时间长就是致命缺点。2.优化方案：穷举算法 要 将事件的结果一一列举出来，那就势必要用到循环结构。那么我们就可以 经过初步判断之后减少循环的次数这样就大大的缩小了运算的时间,减少运行的次数。三穷举算法设计一般流程提出问题穷举可能的结果筛选结果得出正确答案4 穷举算法运用举例 例一：运用穷举算法解决百元买百鸡的问题 流程图：百元买百鸡 列举出一百元能买到鸡的所有结果筛选共买到一百只鸡的结果 得出正确答案源代码：#include#includeint main()clock_t t1=clock();float x,y,z;for(x=0;x=100;x+)for(y=0;y100;y+)for(z=0;z=100;z+)if(x+y+z=100 & 5*x+3*y+z/3=100)printf(%.0f %.0f %.0fn,x,y,z);clock_t t2=clock();printf(%dn,t2-t1);return 0;运行结果：优化后的穷举算法：源代码：#include#includeint main()clock_t t1=clock();float x,y,z;for(x=0;x=20;x+)for(y=0;y33;y+)for(z=3;z=99;z+)if(x+y+z=100 & 5*x+3*y+z/3=100)printf(%.0f %.0f %.0fn,x,y,z);clock_t t2=clock();printf(%dn,t2-t1);return 0;运行结果：结果分析：1.优化后的次数比优化前的次数少。优化前共运行1000000次，优化后运行65000次。2.从时间上比较，第一次用时15毫秒，第二次用时0.例2：木棒任意分三份构成三角形的问题。流程图：十米长木棒分三份所有能分成三份的结果筛选可构成三角形的结果得到正确答案数学知识：三角形构成依据：两边之和大于第三边，两边之差小于第三边。源程序：#include#include#includeclock_t t1=clock();int main()int x,y,z;for(x=1;x=10;x+)for(y=1;y=10;y+)for(z=1;z=y & y=z & x+y+z=10 & x+yz & abs(x-y)z)printf(%d %d %dn,x,y,z);clock_t t2=clock();printf(t=%dn,t2-t1);运行结果：优化后的穷举算法：源程序：#include#include#includeclock_t t1=clock();int main()int x,y,z;for(x=1;x=5;x+)for(y=1;y=4;y+)for(z=1;z=y & y=z & x+y+z=10 & x+yz & abs(x-y)z)printf(%d %d %dn,x,y,z);clock_t t2=clock();printf(%d