实验项目1：蛮力法与分治法应用
1、目的与要求：
实验目的：了解蛮力法和分治法的基本思想，学会运用蛮力法和分治法解决实际系统设计应用中碰到的问题。
实验要求：用蛮力法实现选择、冒泡排序，或旅行商问题、背包问题等问题（任选其中之一）。用分治法实现合并排序或快速排序。要求写出算法的伪代码描述，并编写程序实现之，相关算法放在函数内实现，主程序给出测试用例，要设计足够多的相关测试用例，验证程序的正确性。注意观察程序执行结果和运行的时间。
实验报告要求给出问题定义及算法的伪代码描述，程序设计的代码，算法的测试用例及结果，并分析算法的时间效率，回答指导书中的思考题。
2、实验内容：
（2）用分治法实现快速排序、合并排序算法。
本实验主要是用分治法实现合并排序，快速排序程序等。
合并排序算法描述：
MergeSort ( A[0...p-1] )
// input 待排序数组A[0..n-1]
// output 非降序排列的数组A[0..n-1]
if ( n>1 ) {//至少有2个元素
Copy A[0.. n/2-1 ] to B[0.. n/2-1 ];
Copy A[n/2..n-1 ] to C[0.. n/2-1 ];
MergeSort ( B[0.. n/2-1 ] );
MergeSort (C[0.. n/2-1 ]t);
Merge (B, C, A); //复制回数组a
快速排序算法描述：
QuickSort ( A[1.. r ] )
{
if (l QuickSort ( A[l..s-1] ); //对左半段排序 QuickSort ( A[s+1,r); //对右半段排序 } Partition ( A[l..r] ) { p=A[[l] ; i = l; j = r + 1; repeated repeated i=i+1; until A[i]> p // 将>= x的元素交换到左边区域 repeated i=i+1; until A[i]> p // <= x的元素交换到右边区域 Swap( A[i], A[j] ) Until i>j Swap( A[i] = a[j] ); Swap( A[l], A[j] ) return j; 要求先给出算法的伪代码，然后用C++或其他程序设计语言编写程序实现之，并设计相关的测试用例，验证程序的正确性。测试用例要求达到30个数据以上，或程序生成100个以上的数据，验证并说明程序的正确性。 上述实验项目是一般要求，的如学生水平较高，上述这些程序已经掌握，可以设计其他难度较高问题的算法和程序。如：hanoi 塔问题。 最后要求结合实验体会，分析算法的时间效率。 实验思考题：1、蛮力法的优缺点是什么？适用什么情况？ 2、分治法的基本思想是什么？适用什么情况？说明分治法的优点 和局限性。 实验代码： #include using namespace std; inline void Swap(int &x,int &y) //交换x,y { int temp=x; x=y; y=temp; } int Partition(int a[],int p,int r) //通过一趟排序将要排序的数据分割成独立的两部分 //Partition 以确定一个基准元素a[q] 对子数组a[p:r]进行划分 { int i=p,j=r+1; int x=a[p]; //一部分的所有数据都比另外一部分的所有数据都要小 while(true) { while(a[++i] while(a[--j]>x); //将>x得元素交换到右边区域 if(i>=j) break; Swap(a[i],a[j]); //交换a[i],a[j] } a[p]=a[j]; a[j]=x; return j; //返回划分点 } void QuickSort(int a[],int p,int r) //利用递归进行快速排序 { if(p { int q=Partition(a,p,r); //Partition返回划分点j，此处使q=j q 为分裂点 QuickSort(a,p,q-1); //对左半段排序 QuickSort(a,q+1,r); //对右半段排序 } } int main() { int len; cout<<"请输入数组长度: "; cin>>len; int *a=new int[len]; //动态生成一个长度为len的数组 cout<<"请输入一个数组: "; for(int i=0;i cin>>a[i]; QuickSort(a,0,len-1); //对数组进行快排cout<<"排序后的数组是:"; for(int j=0;j cout< delete[] a; return 0; } 测试结果图： 图1： 图2： 图3： 30组数据测试图： 合并排序 代码： //递归实现合并排序 #include "stdafx.h" #include using namespace std; int a[] = {10,5,9,4,3,7,8}; int b[7]; template void Merge(Type c[],Type d[],int l,int m,int r); template void MergeSort(Type a[],int left,int right); int main() { for(int i=0; i<7; i++) { cout< } cout< MergeSort(a,0,6); for(int i=0; i<7; i++) { cout< } cout< } template void Merge(Type c[],Type d[],int l,int m,int r) { int i = l,j = m + 1,k = l; while((i<=m)&&(j<=r)) { if(c[i]<=c[j]) { d[k++] = c[i++]; } else { d[k++] = c[j++]; } } if(i>m) { for(int q=j; q<=r; q++) { d[k++] = c[q]; } } else { for(int q=i; q<=m; q++) { d[k++] = c[q]; } } } template void MergeSort(Type a[],int left,int right) { if(left { int i = (left + right)/2; MergeSort(a,left,i); MergeSort(a,i+1,right); Merge(a,b,left,i,right);//合并到数组b //复制回数组a for(int g=left; g<=right; g++) { a[g] = b[g]; } } } 测试结果图： 图1： 图2： 图3： 30组数据测试图： 分治法的基本思想： 任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的问题，当n=1时，不需任何计算；当n=2时，只要作一次比较即可排序好；当n=3时只要做3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 适用什么情况？ 分治法所能解决的问题一般具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 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．代码设计： 数值实验报告I 实验名称Poisson方程九点差分格式实验时间2016年 4 月 15 日姓名米瑞琪班级信息1303学号04成绩 一、实验目的，内容 1、理解Poisson方程九点差分格式的构造原理； 2、理解因为网格点的不同排序方式造成的系数矩阵格式的差异； 3、学会利用matlab的spdiags(),kron()函数生成系数矩阵； 二、算法描述 针对一个Poisson方程问题： 在Poisson方程五点差分格式的基础上，采用Taylor展开分析五点差分算子的截断误差，可以得到： 为了提高算子截断误差的精度，在(1)式中配凑出了差分算子的形式，将原Poisson方程代入（1）式有： 考虑，有： 将（3）代回（2）可得 得到Poisson方程的九点差分格式： 在计算机上实现（4）式，需要在五点差分格式 的基础上在等式两端分别增加一部分，将等式左侧新增的部分写成紧凑格式，有： 对于该矩阵，可以看成是两个矩阵的组合： 以及 则生成这两个矩阵可以采用Kroncker生成，方法类似于五点差分格式。 对于右端添加的关于f(x,y)的二阶导数，可以采用中心差分格式进行近似代替，即： 写成相应的紧凑格式有： 该式中的矩阵又可以分解为两个矩阵的和： %计算误差 u_real=@(x,y)exp(pi*(x+y))*sin(pi*x).*sin(pi*y); for i=1:N1-1 u_m((i-1)*(N2-1)+1:i*(N2-1))=u_real(x(i),y); end u_v=u_m'; err_d=max(abs(u_d-u_v)); sol=reshape(u_d,N2-1,N1-1); mesh(X,Y,sol) 四. 数值结果 针对课本P93给出的问题，分别采用步长，将计算出的误差列表如下： 步长五点差分格式误差九点差分格式误差 可见采用九点差分格式可以进一步缩小误差，达到更高阶的精度。 五. 计算中出现的问题，解决方法及体会 在生成九点差分格式的时候，等号右端涉及到了对f的二阶偏导，我最初利用符号函数定义了f,随后求出其二阶偏导（仍然是符号函数）之后带入网格点，求f二阶偏导的精确解，但是代入过程相当繁琐，运行速度非常慢，最终我改变策略，选用f关于x,y的二阶中心差分格式替代精确值，最终得到了相对满意的结果。 教 师 评 语 指导教师：年月日 算法分析与设计实验报告第五次附加实验 附录： 完整代码（回溯法） //0-1背包问题回溯法求解 #include Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template 华北电力大学 实验报告| | 实验名称算法设计与分析综合实验 课程名称算法设计与分析 | | 专业班级软件12 学生姓名： 学号：成绩： 指导教师：胡朝举实验日期： 实验一分治策略—归并排序 一、实验要求 （1）编写一个模板函数：template 实验一分治法 一、实验目的 1．理解分治法的方法； 2. 掌握使用分治法解决一般问题的步骤； 3. 掌握分治算法求解数组的最大值和最小值的方法。 二、实验原理 在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。 假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接查找，算法伪代码如下： 1. x←a[0]; y←a[0] 2. for i←2 to n 3. if a[i] 南京理工大学 课程考核论文 课程名称：高等数值分析 论文题目：有限差分法求解偏微分方程 姓名：罗晨 学号： 成绩： 有限差分法求解偏微分方程 一、主要内容 1.有限差分法求解偏微分方程，偏微分方程如一般形式的一维抛物线型方程：具体求解的偏微分方程如下： 2.推导五种差分格式、截断误差并分析其稳定性； 3.编写MATLAB程序实现五种差分格式对偏微分方程的求解及误差分析； 4.结论及完成本次实验报告的感想。 二、推导几种差分格式的过程： 有限差分法（finite-differencemethods ）是一种数值方法通过有限个微分方程近似求导从而寻求微分方程的近似解。有限差分法的基本思想是把连续的定解区域用有限个离散点构成的网格来代替；把连续定解区域上的连续变量的函数用在网格上定义的离散变量函数来近似；把原方程和定解条件中的微商用差商来近似，积分用积分和来近似，于是原微分方程和定解条件就近似地代之以代数方程组，即有限差分方程组，解此方程组就可以得到原问题在离散点上的近似解。 推导差分方程的过程中需要用到的泰勒展开公式如下： ()2100000000()()()()()()()......()(()) 1!2!! n n n f x f x f x f x f x x x x x x x o x x n +'''=+-+-++-+-(2-1) 求解区域的网格划分步长参数如下： 11k k k k t t x x h τ ++-=?? -=?(2-2) 2.1古典显格式 2.1.1古典显格式的推导 由泰勒展开公式将(,)u x t 对时间展开得 2,(,)(,)( )()(())i i k i k k k u u x t u x t t t o t t t ?=+-+-?(2-3) 当1k t t +=时有 21,112,(,)(,)( )()(())(,)()() i k i k i k k k k k i k i k u u x t u x t t t o t t t u u x t o t ττ+++?=+-+-??=+?+?(2-4) 得到对时间的一阶偏导数 1,(,)(,)()=()i k i k i k u x t u x t u o t ττ+-?+?(2-5) 由泰勒展开公式将(,)u x t 对位置展开得 223,,21(,)(,)()()()()(())2!k i k i k i i k i i u u u x t u x t x x x x o x x x x ??=+-+-+-??(2-6) 当11i i x x x x +-==和时，代入式(2-6)得 算法分析与设计实验报告第七次附加实验 } } 测试结果 当输入图如下时： 当输入图如下时： 1 2 3 4 5 1 2 3 4 5 当输入图如下时： 1 2 3 4 5 附录： 完整代码（回溯法） //最大团问题回溯法求解 #include cout<<"最大团：（"; for(int i=1;i 工程电磁场 实验报告 ——有限差分法 用超松弛迭代法求解 接地金属槽内电位的分布 一、实验要求 按对称场差分格式求解电位的分布 已知： 给定边值：如图1-7示 图1-7接地金属槽内半场域的网格 给定初值)()(.1j 40 100 1j p 1 2j i -= --= ??? 误范围差: 510-=ε 计算：迭代次数N ，j i ,?，将计算结果保存到文件中 二、实验思想 有限差分法 有限差分法（Finite Differential Method ）是基于差分原理的一种数值计算法。其基本思想：将场域离散为许多小网格，应用差分原理，将求解连续函数?的泊松方程的问题转换为求解网格节点上? =?= V 100 ? 0 =?0 =? 的差分方程组的问题。 泊松方程的五点差分格式 )(4 1 4243210204321Fh Fh -+++=?=-+++?????????? 当场域中,0=ρ得到拉普拉斯方程的五点差分格式 )(4 1 044321004321??????????+++=?=-+++ 差分方程组的求解方法(1) 高斯——赛德尔迭代法 ][)(,)(,)(,)(,)(,2 k 1j i k j 1i 1k 1j i 1k j 1i 1k j i Fh 4 1 -+++=+++-+-+????? (1-14) 式中：??????=??????=,2,1,0,2,1,k j i ， ? 迭代顺序可按先行后列，或先列后行进行。 ? 迭代过程遇到边界节点时，代入边界值或边界差分 格式，直到所有节点电位满足ε??<-+)(,)(,k j i l k j i 为止。 （2）超松弛迭代法 ][) (,)(,)(,)(,)(,)(,)(,k j i 2k 1j i k j 1i 1k 1j i 1k j 1i k j i 1k j i 4Fh 4 ?????α??--++++=+++-+-+ (1-15) 式中：α——加速收敛因子)21(<<α 可见：迭代收敛的速度与α有明显关系 三、程序源代码 #include 实验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)搜索 《算法设计与分析》实验报告一 学号：姓名： 日期： 2012.11.5 得分： 一、实验内容： 分别用蛮力法、分治法、减治法实现a^n。 二、实验要求： 完成试验报告、给出对此结果。 为防止大数溢出，可以用1^n来测试在n比较大是的三种算法运行情况。 四、源程序及注释： #include } int main() { int a=1; int n=10000; LARGE_INTEGER start1,end1,start2,end2,start3,end3,f; QueryPerformanceFrequency(&f); QueryPerformanceCounter(&start1) ; int p1=Power1(a,n); QueryPerformanceCounter(&end1); QueryPerformanceCounter(&start2) ; int p2=Power2(a,n); QueryPerformanceCounter(&end2); QueryPerformanceCounter(&start3) ; int p3=Power3(a,n); QueryPerformanceCounter(&end3); cout<<"a="< 数学与计算机学院实验报告 一、实验项目信息 项目名称：回溯法 实验时间： 2016/06/08 实验学时： 03 学时 实验地点：工科楼503 二、实验目的及要求 理解回溯法的深度优先搜索策略、 掌握用回溯法解题的算法框架、 掌握回溯法的设计策略 三、实验环境 计算机Ubuntu Kylin14.04 CodeBlock软件四、实验内容及实验步骤 排兵布阵问题 某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为A ij。试设计一个布阵方案，使总的攻击力最大。 数据： 防卫点 角 色 1 2 3 4 5 1 2 3 4 5 回溯法： 程序： #include if(check(k))break; else position[k]=position[k]+1; if(position[k]<=n && k==n-1) { for(i=0;i 算法设计与分析课程实验项目目录 学生姓名：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号 201 实验项目类型设计实验地点机房 学生姓名学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间 2012年 3月 1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要内容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的： S END +MORE MONEY . 这 里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序代码如下： #include "" #include "" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 宁波工程学院电信学院计算机系 实验报告 课程名称：算法设计与分析实验项目：用分治法算法解 最接近点对问题 指导教师：崔迪 实验位置：软件工程实验室姓名： 班级： 学号： 日期： 2016/10/12 一、实验目的 通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设 计和算法复杂性分析等。 二、实验环境： Eclipse 三、实验内容：用分治法解最接近点对问题 （1）问题描述 给定平面S上n个点，找其中的一对点，使得在n(n-1)/2 个点对中，该 点对的距离最小。 （2）算法设计思想 1. n较小时直接求 (n=2). 2.将S上的n个点分成大致相等的2个子集S1和S2 3.分别求S1和S2中的最接近点对 4.求一点在S1、另一点在S2中的最近点对 5.从上述三对点中找距离最近的一对. （3）程序设计（程序清单及说明） package closestpair; import java.util.Arrays; import https://www.doczj.com/doc/4f14144551.html,parator; import java.util.Random; import java.util.Scanner; //定义坐标点 class Point { double x; double y; public Point(double x, double y) { this.x = x; this.y = y; } } // 根据x坐标排序 class MyComparatorX implements Comparator 实验报告 课程名称：计算方法 院系：数学科学系 专业班级：数应1001 学号：1031110139 学生姓名：姚海保 指导教师：沈林 开课时间：2012至2013学年第一学期 一、学生撰写要求 按照实验课程培养方案的要求，每门实验课程中的每一个实验项目完成后，每位参加实验的学生均须在实验教师规定的时间内独立完成一份实验报告，不得抄袭，不得缺交。 学生撰写实验报告时应严格按照本实验报告规定的内容和要求填写。字迹工整，文字简练，数据齐全，图表规范，计算正确，分析充分、具体、定量。 二、教师评阅与装订要求 1.实验报告批改要深入细致，批改过程中要发现和纠正学生实验报告中的问题，给出评语和实验报告成绩，签名并注明批改日期。实验报告批改完成后，应采用适当的形式将学生实验报告中存在的问题及时反馈给学生。 2.实验报告成绩用百分制评定，并给出成绩评定的依据或评分标准（附于实验报告成绩登记表后）。对迟交实验报告的学生要酌情扣分，对缺交和抄袭实验报告的学生应及时批评教育，并对该次实验报告的分数以零分处理。对单独设课的实验课程，如学生抄袭或缺交实验报告达该课程全学期实验报告总次数三分之一以上，不得同意其参加本课程的考核。 3.各实验项目的实验报告成绩登记在实验报告成绩登记表中。本学期实验项目全部完成后，给定实验报告综合成绩。 4.实验报告综合成绩应按课程教学大纲规定比例（一般为10-15%）计入实验课总评成绩；实验总评成绩原则上应包括考勤、实验报告、考核（操作、理论）等多方面成绩； 5.实验教师每学期负责对拟存档的学生实验报告按课程、学生收齐并装订，按如下顺序装订成册：实验报告封面、实验报告成绩登记表、实验报告成绩评定依据、实验报告（按教学进度表规定的实验项目顺序排序）。装订时统一靠左侧按“两钉三等分”原则装订。 应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表 实验报告 一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。 二、实验内容 【实验内容】 最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。 【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。 三、算法思想和实现【实现代码】 【实验数据】 假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。 部件重量表： 部件价格表： 【运行结果】 实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。 四、问题与讨论 影响回溯法效率的因素有哪些？ 答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井 算法分析与设计实验报告第四次附加实验 while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; //将基准元素放在合适的位置 a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果: 实验心得 快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是 重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度 很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确 定轴值，从而可以期望划分是较对称 的，减少了出现极端情况的次数，使得排序的效率挺高了很多， 化算法想呼应，而且关键的是对于随机生成函数，通过这一次的 学习终于弄明白是怎么回事了，不错。 与后面的随机实 验和自己的 实验得分助教签名 附录： 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude 算法分析与设计实验报告第三次附加实验 附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include { friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："< 一、实验目的 1．理解分治法的方法； 2. 掌握使用分治法解决一般问题的步骤； 3. 掌握分治算法求解数组的最大值和最小值的方法。 二、实验原理 在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。 假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接 循环的次数在算法第2行给出，为(n-2)+1=n-1次，因此，算法元素比较总次数为2(n-1)次。 现在采用分治的思想，假设数组的长度为2的整数幂，将数组分割成两半，分别为a[0…(n/2)-1]和a[n/2…n-1]，在每一半中分别查找最大值和最小值，并返回这两个最小值中的最小值以及两个最大值中的最大值。 假设给定数组为a，数组的下标上界和下界分别为low和high，则其算法伪 接比较数组的两个元素，选出最大值和最小值，此为函数的递归终止条件；代码第7行和第8行是两个递归调用，分别在数组的下标范围[low,mid]和 [mid+1,high]查找最小值和最大值，第9行比较两个最大值取其中较大者，第10行比较两个最小值取较大者。 代码的第2、9和10行涉及到元素的比较，第7、8行由于递归也产生元素比较，因此令算法总的元素比较次数为C(n)，则有 ???>+==2 2)2/(221)(n n C n n C 若若 对递推式进行求解 2 2/3 2 2)2/( 2)2(2 2 2...22)2/(2 ... 2 48)8/(824)2)8/(2(4 2 4)4/(42)2)4/(2(22)2/(2)(1 1122111-=-+=+=+++++==+++=+++=++=++=+=∑-=-----n n C n C n C n C n C n C n C n C k k j j k k k k k 得到minmax 算法的元素比较总次数为3n/2-2，优于直接比较的性能。 三、实验内容及要求 1. 编写程序使用分治算法MINMAX 求解数组的最小值和最大值，并用实际数组对算法进行测试。 2. 要求算法中元素比较的次数为3n/2-2，在程序中元素比较的地方进行记录，并在程序末尾输出数组最大值和最小值以及元素比较次数。 四、实验步骤 1. 定义结构体类型或类，用以在函数的返回值同时返回数组的最大值和最小值。算法设计与分析实验报告
Poisson方程九点差分格式_米瑞琪
回溯法实验(0-1背包问题)
算法实验报告
_实验1分治法
差分法求解偏微分方程MAAB
回溯法实验(最大团问题)
有限差分法实验报告
回溯法实验报告
分别用蛮力法、分治法、减治法实现a的N次方
回溯法实验报告
算法设计与分析实验报告
分治法实验报告一
差分方法实验报告
算法设计与分析：回溯法-实验报告
分治算法实验(用分治法实现快速排序算法)
回溯法实验(n皇后问题)(迭代法)
-实验1分治法
相关主题
文本预览