分治算法设计与应用
实验报告
课程算法设计与分析实验实验名称分治算法设计与应用第 1 页
一、实验目的
1.加深对分治算法的基本思想、基本步骤和一般形式的理解，掌握分治算法设计的基本方法。
2.用分治法设计L型组件填图问题的算法，分析其复杂性，并实现；
3.用分治法设计求数列中的第1～k小元素的算法，分析其复杂性，并实现。
二、实验内容
(一)L型组件填图问题
1.问题描述
设B是一个n×n棋盘，n=2k,(k=1,2,3,…)。用分治法设计一个算法，使得：用若干个L型条块可以覆盖住B的除一个特殊方格外的所有方格。其中，一个L 型条块可以覆盖3个方格。且任意两个L型条块不能重叠覆盖棋盘。
例如：如果n=2，则存在4个方格，其中，除一个方格外，其余3个方格可被一L型条块覆盖；当n=4时，则存在16个方格，其中，除一个方格外，其余15个方格被5个L型条块覆盖。
2. 具体要求
输入一个正整数n，表示棋盘的大小是n*n的。输出一个被L型条块覆盖的n*n棋盘。该棋盘除一个方格外，其余各方格都被L型条块覆盖住。为区别出各个方格是被哪个L型条块所覆盖，每个L型条块用不同的数字或颜色、标记表示。
3. 测试数据（仅作为参考）
输入：8
输出：A 2 3 3 7 7 8 8
2 2 1
3 7 6 6 8
4 1 1
5 9 9
6 10
4 4
5 5 0 9 10 10
12 12 13 0 0 17 18 18
12 11 13 13 17 17 16 18
14 11 11 15 19 16 16 20
14 14 15 15 19 19 20 20
4. 设计与实现的提示
对2k×2k的棋盘可以划分成若干块，每块棋盘是原棋盘的子棋盘或者可以转化成原棋盘的子棋盘。
注意：特殊方格的位置是任意的。而且，L型条块是可以旋转放置的。
为了区分出棋盘上的方格被不同的L型条块所覆盖，每个L型条块可以用不同的数字、颜色等来标记区分。
5. 扩展内容
可以采用可视化界面来表示各L型条块，显示其覆盖棋盘的情况。
(二) 求数列中的第1～k小元素
1.问题描述
设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题，这里k不是常量，即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。
2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1764题
输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由三行组成，其中其中，第一行输入一个正整数n，表示元素的个数；第二行输入n个整数，整数之间用一个空格隔开。第三行输入一个正整数k，表示求该组测试例中的前k个最小元素。（设给出的每个整数序列中的元素是唯一的。）
输出：对于每个测试例输出一行，由k个整数组成，表示输入的n个整数中前k个最小元素。整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行。
若在ACM平台上提交程序，输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。
3. 测试数据
输入：2
19
56 34 22 7 16 95 46 37 81 12 73 26 19 31 68 42 3 72 51
8
26
8 33 28 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 2 32 54 5 16 22
23 7
13
输出：3 7 12 16 19 22 26 31
2 3 5 6 7 8 11 12 13 14 16 17 22
4. 设计与实现的提示
注意题目中算法时间复杂性的限制。如果采用排序算法解决此问题并返回
A[1…k],则耗费时间为O(nlogn),超出要求；如果运行算法SELECT k次，耗费Θ(kn)= O(n2),因为k不是常量，因此不能简单地运行算法SELECT k次。
若在ACM平台上提交程序，输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。
三、实验环境
硬件：Windows XP计算机、鼠标、键盘、显示器
开发环境：Microsoft Visual C++ 6.0
四、实验步骤
（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）
①、点击开始菜单中的程序-Microsoft Visual C++ 6.0
点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中
写入“实验三.(1).cpp”,再点击确定.
②、编写程序如下：
#include
#define MAX 100
int line=1;
int A[MAX][MAX];
void qipan(int h,int l,int row,int lin,int m)
{
if(m==1)
return;
int p=line++,
f=m/2;
if(row qipan(h,l,row,lin,f);//特殊方格在此盘中 else { A[h+f-1][l+f-1]=p; //此盘中无特殊方格 qipan(h,l,row+f-1,lin+f-1,f); //覆盖其余方格 } if(row qipan(h,l+f,row,lin,f); else { A[h+f-1][l+f]=p; qipan(h,l+f,row+f-1,lin+f,f); } if(row>=h+f&&lin qipan(h+f,l,row,lin,f); else { A[h+f][l+f-1]=p; qipan(h+f,l,row+f,lin+f-1,f); } if(row>=h+f&&lin>=l+f)//以N为8举例，f=4，那么此时相当于在第四象限，递归 qipan(h+f,l+f,row,lin,f); else { A[h+f][l+f]=p; qipan(h+f,l+f,row+f,lin+f,f); } } void main() { int i,j,n,hen,zong; printf("输入棋盘大小格局：\n"); scanf("%d",&n); printf("输入特殊格的横纵坐标：\n"); scanf("%d",&hen); scanf("%d",&zong); if(hen<0||hen>n||zong<0||zong>n) { printf("输入不正确！请重新输入！\n"); return; } qipan(0,0,hen,zong,n); for(i=0;i { for(j=0;j { if((i==hen)&&(j==zong)) printf(" A",A[i][j]); else printf("%5d",A[i][j]); } printf("\n"); } } ③、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入“实验三.(2).cpp”,再点击确定. ④、编写程序如下： #include #define MAX 50 struct data { int number; int elem[MAX]; int k; int output[MAX]; }Data[MAX]; /*-----------------输出前K小元素-------------*/ void find(int A[],int n,int k) { int i,j; int s=0; int B[MAX]; for(i=1;i { for(j=0;j { if(A[j]==A[i]) break; if(j==i-1) B[s++]=A[i]; } } for(i=0;i printf("%4d",B[i]); } /*--------------------排序--------------------*/ void sort(int n,int* a) { int i,temp,j; for(i=0;i { for(j=i+1;j { if(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } } } /*----------------求第K小元素--------------------*/ int select(int k,int* S,int num) { int num1,num2,i,j,m,n1,n2,n3; int temp[5],M[MAX],S1[MAX],S2[MAX],S3[MAX]; if(num<44) { sort(num,S); return S[k-1]; } else { num1=num/ 5; j=0; num2=0; for(i=0;i { temp[j]=S[i]; j++; if(j==5) { j=0; sort(5,temp); M[num2]=temp[2]; num2++; } } m=select((num1+1)/2,M,num2); n1=n2=n3=0; for(i=0;i { if(S[i] { S1[n1]=S[i]; n1++; } else if(S[i]==m) { S2[n2]=S[i]; n2++; } else { S3[n3]=S[i]; n3++; } } if(n1>k) return(select(k,S1,n1)); else if(n1+n2>=k) return m; else return(select(k-n1-n2,S3,n3)); } } /*----------------主函数------------------*/ void main() { int m,i,t,j; printf("输入测例个数：\n"); scanf("%d",&m); for(i=1;i<=m;i++) { printf("第%2d个测例数如下：\n",i); scanf("%d",&Data[i].number); for(j=1;j<=Data[i].number;j++) { scanf("%d",&Data[i].elem[j]); } scanf("%d",&Data[i].k); printf("\n"); printf("第%2d个测例的前%d小元素是: \n",i,Data[i].k); for(t=1;t<=Data[i].number;t++) { Data[i].output[t]=select(t,Data[i].elem,Data[i].number); } find(Data[i].output,Data[i].number,Data[i].k); printf("\n\n"); } } 五、实验结果 实验三.(1).cpp 按照实验要求输入测试例，得到的实验结果是： 实验三.(2).cpp 按照实验要求输入测试例，得到的实验结果是： 六、总结 1.主要要注意实验中的细节 2.在写算法的时候要注意时间复杂性。 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 问题场景：在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。 问题描述：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。 1、一维最接近点对问题 算法思路： 这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n^2)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S 的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n^2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n^2)。整个算法所需计算时间T(n)应满足:T(n)=2T(n/2)+O(n^2)。它的解为T(n)=O(n^2)，即与合并步骤的耗时同阶，这不比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。 设S中的n个点为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，在排序算法已经证明，时间复杂度为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S|x≤m}；S2={x∈S|x>m}。这样一来，对于所有p∈S1和q∈S2有p 目录 1031 输油管道问题 (2) 解题思路 (2) 程序代码 (2) 1032 邮局选址 (5) 解题思路 (5) 程序源代码 (5) 1034 集合划分2 (7) 解题思路： (7) 程序源代码： (7) 1033 集合划分 (9) 解题思路 (9) 程序源代码 (9) 1031 输油管道问题 解题思路 本题目可以分为两个步骤： 1、找出主管道的位置； 2、根据主管道的位置，计算各个油井到主管道的长度之和。 根据题意，设主管道贯穿东西，与y 轴平行。而各个子油井则分布在主输油管道的上下两侧。如下图： 由上图，其实只需要确定主管道的y 坐标，而与各个子油井的x 坐标无关！根据猜测，易知：主管道的y 坐标就是所有子油井y 坐标的中位数。（可以用平面几何知识证明，略） 求中位数的方法可以用排序后取a[(left+right)/2]，当然更推荐用书上的线性时间选择算法解决。记求得的主管道为m y ，最后要输出的结果只需要计算：1||n i m i y y =-∑，输出即可。 另外要提醒的是本题多Case 。 程序代码 #include //本函数求arr[p:q]的一个划分i，使arr[p:i-1]都小于arr[i]，arr[i+1,q]都大于arr[i] int partition(int *arr,int p,int q) { int index = p-1,start = p,base = arr[q]; for(;start 回溯算法的应用 课程名称：算法设计与分析 院系：************************ 学生姓名：****** 学号：************ 专业班级：***************************** 指导教师：****** 2013年12月27日 回溯法的应用 摘要：回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 回溯法，其意义是在递归直到可解的最小问题后，逐步返回原问题的过程。而这里所说的回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。 全排列和求最优解问题是比较经典的问题，我们可以采用多种算法去求解此问题，比如动态规划法、分支限界法、回溯法。在这里我们采用回溯法来解决这个问题。 关键词：回溯法全排列最优值枚举 动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 搜索与回溯算法介绍 一、概述： 计算机常用算法大致有两大类：一类叫蛮干算法，一类叫贪心算法。前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。后者在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解。 二、搜索与回溯： 这里着重介绍搜索与回溯。当很多问题无法根据某种确定的计算法则来求解时可以利用搜索与回溯的技术求解。回溯是搜索算法中既带有系统性又带有跳跃性的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索。在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进。如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。 【建立解空间】 问题的解应该如何描述，如何建立呢？问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。借助图论的思想，可以用图来描述，图的定义为G，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。 确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向 分治法 【摘要】：分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。本文主要叙述了分治法的设计思想及与之有关的递归思想，了解使用分治法解决问题的过程。 【关键词】：分治法分解算法递归二分搜索 Partition Method （Junna Wei） 【abstract 】: the partition method can explain to popular: decomposition, put a slice of territory is decomposed into several pieces of small, then pieces of land occupation of conquest, the decomposition can be different political factions or something, then let them each other alienation. This paper mainly describes the design idea of the partition method and recursive thinking, related to understand the process of solving the problem using the partition method. 【key words 】: partition method decomposition algorithm recursive Binary search 1.引论 算法分析与设计实验报告第四次附加实验 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 中原工学院信息商务学院 实验报告 实验项目名称回溯划算法的应用 课程名称算法设计与分析 学院(系、部)中原工学院信息商务学院学科专业计算机科学与技术系班级学号计科132班17号姓名程一涵 任课教师邬迎 日期2014年12月9日 实验五回溯算法的应用 一、实验目的 1．掌握回溯算法的基本概念 2．熟练掌握回溯算法解决问题的基本步骤。 3．学会利用回溯算法解决实际问题。 二．问题描述 题目一：N皇后问题 要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解要求：键盘输入皇后的个数n (n ≤ 13) 输出有多少种放置方法 输入输出实例： 三．算法设计 首先，确定第一行皇后的位置，再确定第二行的位置，并且要注意不能同行同列同对角线，若是发现有错则返回上一层，继续判断。满足约束条件时，则开始搜索下一个皇后的位置，直到找出问题的解。 四.程序调试及运行结果分析 五.实验总结 通过这次试验，使得我们面对问题时的解题思路变得更加灵活和多变，并且使我们的编写能力稍稍的提高一些。初步了解了回溯算法，回溯算法实际是一个类似枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。他特别适用于求解那些涉及到寻求一组解的问题或者求满足某些约束条件的最优解的问题。此算法具有结构清晰，容易理解且可读性强等优点，并且通过稍加变通也可以适用于其他类似问题 附录：程序清单（程序过长，可附主要部分） #include 算法分析(第二章)：递归与分治法 一、递归的概念 知识再现：等比数列求和公式： 1、定义：直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2、与分治法的关系： 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。 3、递推方程： (1)定义：设序列01,....n a a a简记为{ n a}，把n a与某些个() i a i n <联系起来的等式叫做关于该序列的递推方程。 (2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。 4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序 5、优缺点： 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 二、递归算法改进： 1、迭代法： (1)不断用递推方程的右部替代左部 (2)每一次替换，随着n的降低在和式中多出一项 (3)直到出现初值以后停止迭代 (4)将初值代入并对和式求和 (5)可用数学归纳法验证解的正确性 2、举例： -----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1 (1)1 T n T n T =?+ = ()(1)1 W n W n n W =?+? （1）=0 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 回溯算法实例一 【问题】填字游戏 问题描述：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，使得所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。 可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。 为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。 回溯法找一个解的算法： { int m=0,ok=1; int n=8; do{ if (ok) 扩展; else 调整; ok=检查前m个整数填放的合理性; } while ((!ok||m!=n)&&(m!=0)) if (m!=0) 输出解; else 输出无解报告； } 如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下： 回溯法找全部解的算法： { int m=0,ok=1; int n=8; do{ if (ok) { if (m==n) { 输出解； 调整； } else 扩展; } else 调整; ok=检查前m个整数填放的合理性; } while (m!=0); 递归与分治实验报告 班级：计科1102 姓名：赵春晓学号：2011310200631 实验目的：进一步掌握递归与分治算法的设计思想，通过实际问题来应用递归与分治设计算法。 实际问题：1集合划分问题，2输油管道问题，3邮局选址问题，4整数因子分解问题，5众数问题。 问题1：集合划分 算法思想：对于n个元素的集合，可以划分为由m个子集构成的集合，例如{{1,2}{3,4}}就是由2个子集构成的非空子集。假设f（n，m）表示将n个元素划分成由m个子集构成的集合的个数。那么1）若m == 1 ，则f（n，m）= 1 ；2）若n == m ，则f（n，m）= 1 ；3）若不是上面两种情况则有下面两种情况构成：3.1）向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；3.2）向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。 实验代码： #include 安徽文达信息工程学院学生实验报告（计算机语言编程类适用） 一、【实验目的】 1.熟悉分治算法思想。 2.验证具体问题算法的设计及程序实现。 二、【实验内容】 1、有N枚硬币，其中一枚是假币，假币和真币重量不同，可以用一个没有刻度的天平测，求出假币是哪一枚，现要求采用分治法解决，请写出算法设计思路。(不需要编程) 答：（1）N为偶数时，将N枚硬币分成N/2，N/2的两份将第一份分成N/4，N/4的两份，分别置于天平两端，如果天平倾斜，则假币在第一份N/2中，反之水平，则假币在第二份N/2中; （2）N为奇数时，将N枚硬币分成（N+1）/2，（N-1）/2的两份,将第一份分成（N+1）/4，(N+1)/4的两份，分别置于天平两端，如果天平倾斜，则假币在第一份(N+1)/2中，反之水平，则假币在第二份(N-1)/2中， （3）将含假币的的币数赋值给N，N为偶数执行步骤（1），N为奇数执行步骤（2），如此执行直至找出含假币的2或3枚硬币，如果是2枚硬币则找1枚硬币构成3枚，3枚则直接两两置于天平两端，找到使天平水平的两枚硬币，则假币是剩下的硬币。 2、格雷码问题： 对于给定的正整数n，格雷码为满足如下条件的一个编码序列： (1) 序列由2n个编码组成，每个编码都是长度为n的二进制位串。 (2) 序列中无相同的编码。 (3) 序列中位置相邻的两个编码恰有一位不同。 例如：n=1时的格雷码为：{0, 1}。 n=2时的格雷码为：{00, 01, 11, 10}。 n=3时的格雷码为：{000, 001, 011, 010,110,111,101,100}。 gray码问题求解思想： 将一个规模n位gray码序列表示为G(n), G(n)以相反顺序排列的序列表示为G’(n)。则gray 码的构造规则即子问题的划分规则为：G(n+1)= 0G(n) 1G’(n) 或G(n+1)= G(n) 0G’(n)1。 请尝试编写程序，完成格雷码问题的处理。 实验四回溯法的应用------跳马算法 学号：012124345 姓名：梁文耀 一、实验目的 掌握使用回溯法求解问题的基本思路；理解其特点。 二、实验思想 算法的基本思路是： 定义结构体：struct PLACE{int x, int y}表示棋盘上的位置。 依题意，马每跳一步之后都可以从七个不同的方向选择下一步的跳马，当然，前提是跳的这一步在棋盘内且它前面的任何一步都没跳到这一格子上（限界），就可以认为这一步跳成功，否则跳马不成功。若跳马不成功，则找下一个方向尝试跳马，若七个方向都跳马不成功，则回溯。 假设棋盘的行（列）数为n。 在本算法中设置这样一个全局数组：c[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}}; 来记录跳马的八个方向。 三、程序分析（主要算法） int map[12][12], status[12][12], kp; int start,finsh; int c[8][2]={{2,1},{2,-1},{1,2},{1,-2}, {-2,1},{-2,-1},{-1,2},{-1,-2}}; int flag = 0; void prt(int a[][12]) /* 打印棋盘状态*/ { int i,j; printf("\n"); for (i=2;i<=9;i++) { for (j=2;j<=9;j++) printf("%4d",a[i][j]); printf("\n"); } } void status2(void) /* 计算棋盘各点条件数*/ { int i,j,k,i2,j2,kz; for(i=0;i<12;i++) for(j=0;j<12;j++) status[i][j]=100; for(i=2;i<=9;i++) for(j=2;j<=9;j++) { kz=0; 实验五：0/1背包问题的回溯算法设计实验目的：0/1背包问题的回溯算法设计 实验原理：回溯算法设计。 实验要求：基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想:0-1背包问题:给定n种物品和一背包.物品i的重量是wi,其价值为ui,背包的容量为C.问如何选择装入背包的物品,使得装入背包中物品的总价值最大? 分析: 0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题.第一步确定解空间：装入哪几种物品 第二步确定易于搜索的解空间结构： 可以用数组p,w分别表示各个物品价值和重量。 用数组x记录，是否选种物品 第三步以深度优先的方式搜索解空间，并在搜索的过程中剪枝要求：（1）使用C++或TC2.0 （2）上机前要有源代码或流程图。#include for(int m=1;m<=n;m++) { cout< 分治算法举例 文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58- 1设X[0：n-1]和Y[0：n-1]为两个数组，每个数组中含有n个已排序好的数。试设计一个O(logn)时间的分治算法，找出X和Y的2n个数的中位数，并证明算法的时间复杂性为O(l o g n)。注：个数为奇数，则处于最中间位置的数； 个数为偶数，则中间两个数据的平均数。 解： 利用二分查找思想： 对于两个等长的数组， 如果数组长度为奇数，令mid为数组的最中间元素的位置，则有 X[mid]，Y[mid]分别为两个数组的中位数，则存在以下情况： （1）如果X[mid] 为y=(Y[mid]+Y[mid+1])/2.0(这里考虑到中位数不一定为整数)。则存在以下情况： （1）如果x算法设计与分析复习题目及答案
0007算法笔记——【分治法】最接近点对问题
分治算法例题
回溯算法的应用(DOC)
算法分析与程序设计动态规划及回溯法解背包问题
算法设计与分析：递归与分治法-实验报告
算法分析实验报告--分治策略
搜索与回溯算法介绍
分治法
分治算法实验(用分治法实现快速排序算法)
回溯算法实验
算法之2章递归与分治
算法分析实验报告--分治策略
回溯算法实例一培训讲学
递归与分治实验报告
分治算法设计
实验四 回溯法的应用------跳马算法
实验五：01背包问题的回溯算法设计
分治算法举例
- 回溯法求一组解或最优解论文 算法设计
- 回溯算法的应用
- 回溯算法(C++版)
- 实验6---子集和问题的回溯算法设计与实现(报告)
- 《计算机算法设计与分析》习题及答案
- 回溯算法实验
- 算法设计与分析学习提纲,第七章回溯
- 算法设计与分析：第8章 回溯法
- 回溯算法报告
- 回溯法_ppt课件
- 深度优先搜索与回溯算法
- 算法分析与程序设计动态规划及回溯法解01背包问题
- 算法设计与分析--回溯法
- 算法分析与设计部分含计算的复习题及参考答案
- 《算法设计与分析》-第五章 回溯法
- 回溯算法的应用
- 《算法设计与分析》考试题目与答案
- 回溯法论文-回溯法的分析与应用
- 算法分析与设计实验报告实验2：回溯法的应用
- 回溯算法的应用