实验二蛮力法.doc

实验二 蛮力法一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对蛮力法的理解。二、 实验内容:掌握蛮力法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。三、 实验题1. 某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析：（1）A、B至少有一人作案；（2）A、E、F三人中至少有两人参与作案；（3）A、D不可能是同案犯；（4）B、C或同时作案，或与本案无关；（5）C、D中有且仅有一人作案；（6）如果D没有参与作案，则E也不可能参与作案。试设计算法将作案人找出来。2. 将1,2.9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 实验程序第一题：#includeusing namespace std;int main()/每个人只可能有两种情况，1罪犯或0非罪犯int A,B,C,D,E,F;for(A=0;A2;A+)for(B=0;B2;B+)for(C=0;C2;C+)for(D=0;D2;D+)for(E=0;E2;E+)for(F=0;F=2)&(A+D)!=2)&(B+C=2)|(B+C=0)&(C+D=1)&(D=0)&(E=0)|(D=1)cout罪犯是：;if(A=1) coutA ;if(B=1) coutB ;if(C=1) coutC ;if(D=1) coutD ;if(E=1) coutE ;if(F=1) coutF ;coutendl;return 0;第二题：#includeusing namespace std;int i1,i2,i3,j1,j2,j3,k1,k2,k3;int main()int s1,s2,s3;for(i1=1;i110;i1+)for(i2=1;i210;i2+)for(i3=1;i310;i3+)for(j1=1;j110;j1+)for(j2=1;j210;j2+)for(j3=1;j310;j3+)for(k1=1;k110;k1+)for(k2=1;k210;k2+)for(k3=1;k310;k3+) s1=i1*100+i2*10+i3;s2=j1*100+j2*10+j3;s3=k1*100+k2*10+k3;if(s2/s1=2)&(s2%s1=0)&(s3/s1=3)&(s3%s1=0)&(i1!=i2)&(i1!=i3)&(i1!=j1)&(i1!=j2)&(i1!=j3)&(i1!=k1)&(i1!=k2)&(i1!=k3)&(i2!=i3)&(i2!=j1)&(i2!=j2)&(i2!=j3)&(i2!=k1)&(i2!=k2)&(i2!=k3)&(i3!=j1)&(i3!=j2)&(i3!=j3)&(i3!=k1)&(i3!=k2)&(i3!=k3)&(j1!=j2)&(j1!=j3)&(j1!=k1)&(j1!=k2)&(j1!=k3)&(j2!=j3)&(j2!=k1)&(j2!=k2)&(j2!=k3)&(j3!=k1)&(j3!=k2)&(j3!=k3)&(k1!=k2)&(k1!=k3)&(k2!=k3) cout结果是：endl;couts1:s2:s3=1:2:3endl;return 0;六、 实验结果 第一题： 第二题： 七、 实验分析 运行环境：Visual C+ 6.0 CPU：2.53GHz 内存：1.92GB系统：Microsoft Windows XP Professional 版本2002蛮力法，又称枚举法、穷举法，暴力法，是一种直接解决问题的方法，常常直接基于问题的描述和所设计的概念定义，因此也是最容易应用的方法。但是，用蛮力法设计的算法其时间性能往往是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的。蛮力法不是一个最好的算法（巧妙和高效的算法很少出自蛮力），但当我们想不出更好的办法是，它也是一种有效的解决问题的方法。它可能是一种几乎什么问题都能解决的一般性办法，常用于一些非常基本、但又十分重要的算法，比如计算n个狮子的和，求一个列表的最大元素等。蛮力法的优点：1、逻辑清晰，编写程序简洁；2、对于一些重要的问题（比如：排序、查找、矩阵乘法和字符串匹配），可以产生一些合理的算法；3、解决问题的实例很少时，可以花费较少的代价；4、可以解决一些小规模的问题（使用优化的算法没有必要，而且某些优化算法本身较复杂）；5、可以作为其他高效算法的衡量标准；用蛮力法解决问题，通常可以从两