实验二--蛮力法.doc

南华大学实验名称：算法的时间复杂度学 院：计 算 机 学 院专业班级：本2010电气信息类03班 学 号：20104030342 姓 名： 谢志兴指导教师： 余颖日期： 2012 年 3 月 27 日实验二 蛮力法一、 实验目的与要求熟悉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的比例,试求出所有满足条件的三个三位数。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 实验程序/*1题程序*/#include using namespace std; int main() int A,B,C,D,E,F; /每个罪犯只有01两种情况，1是罪犯0清白 for(A=0;A2;A+) /A for(B=0;B2;B+)/Bfor(C=0;C2;C+)/Cfor(D=0;D2;D+)/Dfor(E=0;E2;E+)/Efor(F=0;F0) /AB至少一人作案 &(A+E+F1) /AEF至少两人作案 &(A+D=1) /AD不可能是同案犯 &(B+C!=1) /BC或同案 或与本案无关 &(C+D=1) /CD只有一人作案 &(!(!D&E)/如果D没有参与作案，则E也不可能参与作案 coutA:;if(A=1)cout作案endl;elsecout非作案endl;coutB:;if(B=1)cout作案endl;elsecout非作案endl;coutC:;if(C=1)cout作案endl;elsecout非作案endl;coutD:;if(D=1)cout作案endl;elsecout非作案endl;coutE:;if(E=1)cout作案endl;elsecout非作案endl;coutF:;if(F=1)cout作案endl;elsecout非作案endl; return 0; /*2题程序*/#includeusing namespace std;bool isValid(int i,int j,int k) int a3,b3,c3; a0=i%10; a1=(i/10)%10; a2=i/100; b0=j%10; b1=(j/10)%10; b2=j/100; c0=k%10; c1=(k/10)%10; c2=k/100; if(a0!=a1&a0!=a2&a0!=b0&a0!=b1&a0!=b2&a0!=c0&a0!=c1&a0!=c2 &a1!=a2&a1!=b0&a1!=b1&a1!=b2&a1!=c0&a1!=c1&a1!=c2 &a2!=b0&a2!=b1&a2!=b2&a2!=c0&a2!=c1&a2!=c2 &b0!=b1&b0!=b2&b0!=c0&b0!=c1&b0!=c2 &b1!=b2&b1!=c0&b1!=c1&b1!=c2 &b2!=c0&b2!=c1&b2!=c2 &c0!=c1&c0!=c2 &c1!=c2 &a0!=0&a1!=0&a2!=0&b0!=0&b1!=0&b2!=0&c0!=0&c1!=0&c2!=0 ) return true; else return false;int main()cout满足条件的三个三位数分别为：endl; for(int i=123;i=329;i+) int j=2*i,k=3*i; if(isValid(i,j,k)couti j kendl; return 0;六、 实验结果运行环境：操作系统：Windows 7 旗舰版 32位 SP1 ( DirectX 11 )处理器：AMD A6-3400M APU with Radeon HD Graphics 四核主板：宏碁 Aspire 4560 (AMD K12)内存：3 GB ( 海力士 DDR3 1333MHz / 南亚易胜 DDR3 1333MHz )运行结果：1题结果：2题结果：七、 实验分析 蛮力法，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。但是用蛮力法设计的算法其时间性能往往是最低的，典型的指数时间算法一般都是通过蛮力法搜索而得到的。 蛮力法的设计思想： 蛮力法所依赖的最基本技术是扫描技术，依次处理所有元素师蛮力法的关键，一次处理每个元素的方法是遍历。 虽然设计高效的算法很少来自于蛮力法，但基于以下原因，蛮力法也是一种重要的算法设计技术：（1）理论上，蛮力法可以解决可计算领域的各种问题。对于一些非常基本的问题，例如求一个序列的最大元素，计算n个数的和等，蛮力法是一种非常常用的算法设计技术。（2）蛮力法经常用来解决一些较小规模的问题。如果需要解决的问题规模不大，用蛮力法设计的算法其速度是可以接受的，此时设