南华大学
实验名称:算法的时间复杂度
学院:计算机学院
专业班级:本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;A<2;A++) //A
for(B=0;B<2;B++) //B
for(C=0;C<2;C++) //C
for(D=0;D<2;D++) //D
for(E=0;E<2;E++) //E
for(F=0;F<2;F++) //F
{
if((A+B>0) //AB至少一人作案
&&(A+E+F>1) //AEF至少两人作案
&&(A+D==1) //AD不可能是同案犯
&&(B+C!=1) //BC或同案或与本案无关
&&(C+D==1) //CD只有一人作案
&&(!(!D&&E)))//如果D没有参与作案,则E也不可能参与作案
{
cout<<"A:";
if(A==1)
cout<<"作案"< else cout<<"非作案"< cout<<"B:"; if(B==1) cout<<"作案"< cout<<"非作案"< if(C==1) cout<<"作案"< cout<<"非作案"< if(D==1) cout<<"作案"< cout<<"非作案"< if(E==1) cout<<"作案"< cout<<"非作案"< if(F==1) cout<<"作案"< else cout<<"非作案"< } } return 0; } /*2题程序*/ #include using namespace std; bool isValid(int i,int j,int k) { int a[3],b[3],c[3]; a[0]=i%10; a[1]=(i/10)%10; a[2]=i/100; b[0]=j%10; b[1]=(j/10)%10; b[2]=j/100; c[0]=k%10; c[1]=(k/10)%10; c[2]=k/100; if(a[0]!=a[1]&&a[0]!=a[2]&&a[0]!=b[0]&&a[0]!=b[1]&&a[0]!=b[2]&&a[0]!=c[0]&&a[0 ]!=c[1]&&a[0]!=c[2] &&a[1]!=a[2]&&a[1]!=b[0]&&a[1]!=b[1]&&a[1]!=b[2]&&a[1]!=c[0]&&a[1]!=c[1]&&a[1] !=c[2] &&a[2]!=b[0]&&a[2]!=b[1]&&a[2]!=b[2]&&a[2]!=c[0]&&a[2]!=c[1]&&a[2]!=c[2] &&b[0]!=b[1]&&b[0]!=b[2]&&b[0]!=c[0]&&b[0]!=c[1]&&b[0]!=c[2] &&b[1]!=b[2]&&b[1]!=c[0]&&b[1]!=c[1]&&b[1]!=c[2] &&b[2]!=c[0]&&b[2]!=c[1]&&b[2]!=c[2] &&c[0]!=c[1]&&c[0]!=c[2] &&c[1]!=c[2] &&a[0]!=0&&a[1]!=0&&a[2]!=0&&b[0]!=0&&b[1]!=0&&b[2]!=0&&c[0]!=0&&c[1]!=0&&c[2] !=0 ) return true; else return false; } int main(){ cout<<"满足条件的三个三位数分别为:"< for(int i=123;i<=329;i++) { int j=2*i,k=3*i; if(isValid(i,j,k)) cout< } 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)蛮力法经常用来解决一些较小规模的问题。如果需要解决的问题规模不大,用蛮力法设计的算法其速度是可以接受的,此时设计一个更高效算法的代价是不值得的。 (3)对于一些重要的问题(例如排序、查找、字符串匹配),蛮力法可以产生一些合理的算法,它们具备一些使用价值,而且不受问题规模的限制。 (4)蛮力法可以作为某类时间性能的底限,来衡量同样问题的更高效算法。 本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号:2016002105 学生姓名:俞梦真 指导教师:郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 1.4 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想: 根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计: 算法分析与设计实验报告第五次附加实验 附录: 完整代码(回溯法) //0-1背包问题回溯法求解 #include Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template 华北电力大学 实验报告| | 实验名称算法设计与分析综合实验 课程名称算法设计与分析 | | 专业班级软件12 学生姓名: 学号:成绩: 指导教师:胡朝举实验日期: 实验一分治策略—归并排序 一、实验要求 (1)编写一个模板函数:template 沈阳理工大学算法实践与创新论文 摘要 对于计算机科学来说,算法的概念是至关重要的,算法是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。为了更加的了解算法,本篇论文中,我们先研究一个算法---回溯法。 回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索,适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=(V, E),其中V为顶点集合,E为边集合,图着色问题即为将V分为K个颜色组,每个组形成一个独立集,即其中没有相邻的顶点。其优化版本是希望获得最小的 K值。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。 在本篇论文中,我们将运用回溯法来解决着图的着色问题,符号三角形问题,图排列问题,将此三个问题进行深入的探讨。 关键词: 回溯法图的着色问题符号三角形问题图排列问 题 目录 第1章引言 (1) 第2章回溯法的背景 (2) 第3章图的着色问题 (4) 3.1 问题描述 (4) 3.2 四色猜想 (4) 3.3 算法设计 (5) 3.4 源代码 (6) 3.5 运行结果图 (10) 第4章符号三角形问题 (11) 4.1 问题描述 (11) 4.2 算法设计 (11) 4.3 源代码 (12) 4.4 运行结果图 (16) 第5章圆的排列问题 (17) 5.1 问题描述 (17) 5.2 问题分析 (17) 5.3 源代码 (18) 5.4 运行结果图 (22) 结论 (23) 参考文献 (24) 算法分析与设计实验报告第七次附加实验 } } 测试结果 当输入图如下时: 当输入图如下时: 1 2 3 4 5 1 2 3 4 5 当输入图如下时: 1 2 3 4 5 附录: 完整代码(回溯法) //最大团问题回溯法求解 #include cout<<"最大团:("; for(int i=1;i 实验04 回溯法 班级:0920561 姓名:宋建俭学号:20 一、实验目的 1.掌握回溯法的基本思想。 2.掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子 集树与排列树的递归算法结构等内容。 3.掌握回溯法求解具体问题的方法。 二、实验要求 1.认真阅读算法设计教材,了解回溯法思想及方法; 2.设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序 三、实验内容 1.有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船,其中集装箱 i的重量为wi,且∑wi≤C1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有,找出一种装载方案。 2.在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则, 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。 3.给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每 个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。 这个问题是图的m可着色判定问题。 四、算法原理 1、装载问题 用回溯法解装载问题时,用子集树表示其解空间是最合适的。可行性约束可剪去不满足约束条件(w1x1+w2x2+…+wnxn)<=c1的子树。在子集树的第j+1层结点Z处,用cw记当前的装载重量,即cw=(w1x1+w2x2+…+wjxj),当cw>c1时,以结点Z为根的子树中所有结点都不满足约束条件,因而该子树中的解均为不可行解,故可将该子树剪去。 解装载问题的回溯法中,方法maxLoading返回不超过c的最大子集和,但未给出达到这个最大子集和的相应子集。 算法maxLoading调用递归方法backtrack(1)实现回溯搜索。Backtrack(i)搜索算法设计与分析实验报告
回溯法实验(0-1背包问题)
算法实验报告
回溯法论文-回溯法的分析与应用
回溯法实验(最大团问题)
回溯法实验报告
分别用蛮力法、分治法、减治法实现a的N次方