蛮力法:
基于计算机运行速度快的这一特性,在解决问题时采用的一种“懒惰”策略。这种策略不经过思考,把问题的所有情况和所有过程交给计算机一一尝试,从中找出问题的解。我们常用的:选择,冒泡,插入,顺序查找,朴素的字符串匹配等。比较常用的还有枚举法,穷举搜素算法等等。
枚举法
枚举法也称穷举法,是蛮力策略的一种表现形式,也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来,逐一尝试从中找到满足问题条件的解。用该方法通常要确定数值取值范围和找出约束条件。
Case1:
百元百鸡“鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,翁,母,雏各几何?”
算法分析:
首先设定x,y,z,分别代表公鸡,母鸡,雏鸡的数量,由于题意给定了100块买百鸡,若全部买公鸡最多可以买100/5=20只,显然x的取值范围是1-20,同理可得 y的取值范围1-33,z则是1-100
约束条件:
x+y+z=100,5x+3y+z/3=100
算法设计1:
main(){ int x,y,z; for(x=1;x<20;i++){ for(y=1;y<34;y++){ for(z=1;z<100;z++){ if(x+y+z=100 && 5x+3y+z/3=100){ cout<<"公鸡"<<x; } cout<<"母鸡"<<y; } cout<<"小鸡"<<z; } } }
但是由于for循环的嵌套,导致循环次数的累乘,一共要循环2034100=68000次,显然效率太低了。因此我们
可以稍微进行一个小小的优化,当将约束条件改为:当公鸡,母鸡的数量都知道时,那么小鸡的数量自然而然是100-x-y。因此可以做出算法2设计
算法设计2:
main(){ int x,y; for(x=1;x<20;x++){ for(y=1;y<34;y++){ z=100-x-y; if(x+y+z=100 && 5x+3y+z/3=100){ cout<<"公鸡"<<x; } cout<<"母鸡"<<y; } cout<<"小鸡"<<z; } }
算法设计2 只需要枚举尝试20*33=660次,实现时约束条件即限定Z能被3整除,进一步提高算法的效率。
Case2:
求3个数的最小公倍数
三个数据最小公倍数的定义为“三个数的公倍数中最小的一个”。用蛮力法直接用最小公倍数的定义算法设计,逐步从小扩大到1,2,3,4,5......测试,直到它的某一倍数正好也是其他两个数据的倍数,也就是说能被其他的两个数据整除,因此就找到问题的解。
算法设计:
首先先选出3个数的最大值,然后对这个最大值从1开始,对其扩大自然数的倍数,知道这个积能被全部3个数整除为止,这个积就是它们的最小公倍数了。
算法如下:
main(){ int x1,x2,x3,i; cout<<"输入3个数"; cin>>x1>>x2>>x3; i=1; while(1){ if(i mod x1=0 and i mod x2=0 and i mod x3=0){ break; i++; } cout<<x1<<x2<<x3<<"最小公倍数是"<<i; } }
不过该算法虽然简单易懂,但是当三个数据较大时,算法效率非常低,可以使用最小公倍数定义进行算法设计,或者用短除法的思想。