2015《算法分析与设计》实验指导书

算法分析与设计实验指导书算法分析与设计是面向设计的，它是计算机科学和软件工程应用的核心。

无论是计算机系统、系统软件和解决计算机的各种应用课题都可归结为算法的设计。

通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的精确的描述：分治法、贪心法、动态规划、回溯法等。

并掌握算法分析的方法。

从而将学生分析问题和解决问题的能力提高到高层理论的高度。

前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。

实验学时：18学时目录实验一递归与分治 (3)实验目的：理解递归与分治算法设计思想和方法。

(3)实验课时：4学时 (3)实验原理： (3)实验题目： (3)1、汉诺塔（hanoi）问题。

(3)2、二分查找问题 (4)3、快速排序问题 (5)思考问题： (6)实验二贪心选择算法 (7)实验目的：理解贪心选择算法的思想 (7)实验课时：4学时 (7)实验原理： (7)实验题目： (7)1、单源最短路径 (7)2、背包问题 (9)3、多机调度问题 (9)思考问题： (10)实验三动态规划算法 (11)实验目的：理解动态规划算法的思想 (11)实验课时：4学时 (11)实验原理： (11)实验题目： (11)1、长公共子序列问题 (11)2、最长最大字段和问题 (12)思考问题： (14)实验四搜索算法 (15)实验目的：理解搜索算法的思想 (15)实验课时：6学时 (15)实验原理： (15)实验题目： (15)1、n皇后问题 (15)2、0-1背包问题 (17)3、装载问题 (18)思考问题： (19)实验一递归与分治实验目的：理解递归与分治算法设计思想和方法。

实验课时：4学时实验原理：一个规模为n的复杂问题的求解：可以划分成若干个规模较小<n的子问题进行求解，再将子问题的解合并成原问题的解，这便是分治的思想。

若划分成的每一个子问题都与原问题的性质相同，可用相同的求解方法；当子问题规模划分一定小时，子问题的解已知，则逆求原问题的解，这是递归的思想。

实验题目：1、汉诺塔（hanoi）问题。

设有A、B、C 共3 根塔座，在塔座A 上堆叠n个金盘，每个盘大小不同，只允许小盘在大盘之上，最底层的盘最大，如下图所示。

现在要求将 A 上的盘全都移到C 上，在移的过程中要遵循以下原则：每次只能移动一个盘；圆盘可以插在A、B 和 C 任一个塔座上；在任何时刻，大盘不能放在小盘的上面。

hanoi问题递归求解思想：我们把一个规模为n的hanoi问题：1到n号盘按照移动规则从A上借助B 移到C上表示为H(A,B,C,n)；原问题划分成如下三个子问题：（1）将1到n-1号盘按照移动规则从A上借助C移到B上H(A,C,B,n-1);（2）将n号盘从A上直接移到C上；（3）将1到n-1号盘按照移动规则从B上借助A移到C上H(B,A,C,n-1);经过三个子问题求解，原问题的也即求解完成。

hanoi问题递归求解代码：void H(char A,char B,char C,int n){if(n>0){H(A,C,B,n-1);printf(“%d from %c to %c”,n,A,C);H(B,A,C,n-1);}}2、二分查找问题（1）设a[0:n-1]是一个已排好序的数组。

请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。

当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

（2）设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标i，0≤i ＜n，使得t[i]=i，设计一个有效的算法找到这个下标。

要求算法在最坏的情况下的计算时间为O（logn）。

bool BinarySearch(int a[],int n,int x,int& i,int& j){int left=0;int right=n-1;while(left<right){int mid=(left+right)/2;if(x==a[mid]){i=j=mid;return true;}if(x>a[mid])left=mid+1;elseright=mid-1;}i=right;j=left;return false;}int SearchTag(int a[],int n,int x){int left=0;int right=n-1;while(left<right){int mid=(left+right)/2;if(x==a[mid]) return mid;if(x>a[mid])right=mid-1;elseleft=mid+1;}return -1;}3、快速排序问题在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。

typedef int Type;void QuickSort (Type a[], int p, int r){if (p<r) {int q=Partition(a,p,r);QuickSort (a,p,q-1); //对左半段排序QuickSort (a,q+1,r); //对右半段排序}}template<class Type>int Partition (Type a[], int p, int r){int i = p, j = r + 1;Type x=a[p];// 将< x的元素交换到左边区域// 将> x的元素交换到右边区域while (true) {while (a[++i] <x);while (a[- -j] >x);if (i >= j) break;Swap(a[i], a[j]);}a[p] = a[j];a[j] = x;return j;}思考问题：1.递归的关键问题在哪里？2.递归与非递归之间程序的转换？实验二贪心选择算法实验目的：理解贪心选择算法的思想实验课时：4学时实验原理：贪心选择算法思想：（1）贪心选择能得到问题的最优解，要证明我们所做的第一步选择一定包含在一个最优解总，即存在一个最优解的第一步是从我们的贪心选择开始。

（2）在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的子问题 为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。

实验题目：1、单源最短路径在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。

按路径长度递增次序产生最短路径算法：把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）单源最短路径代码：void Dijkstra（AdjMGraph G，int v0，int *dist, int *path）{ int n=G.Vertices.size;int i,j,k ,pre ,min ;int *s=(int *)malloc(sizeof(int)*n);for（i=0;i<n;i++）//初始化{ s[i]= 0；dist[i] = G->edge[v0][i]；if(i!=v0&&dist[i]<MaxWeight) path[i] = v0；else path[i]=-1;｝s[v0] = 1；//标记v0已从集合T中加入到Sfor（i＝1；i<n；i++）//｛min=MaxWeight；for(j=0;j<n；j++)//找最小dist[j]if (s[j]==0&&dist[j]< min ){ min＝dist[j]; k=j; }if(min = = MaxWeight) return;S[k]=1; //标记k已从集合T中加入到Sfor（j＝0；j<n；j++）//修改dist[j]if（s[j]==0&&dist[j]>dist[k]+ G->edge[k][j]）｛dist[j]=dist[k]+G->edge[k][j]；path[j]=k; ｝｝}2、背包问题给定n种物品和一个背包。

物品i的重量是Wi，其价值为Vi，背包的容量为C。

应如何选择装入背包的物品，使得装入背包中物品的总价值最大?void Knapsack(int n,float M,float v[],float w[],float x[]){Sort(n,v,w);int i;for (i=1;i<=n;i++) x[i]=0;float c=M;for (i=1;i<=n;i++) {if (w[i]>c) break;x[i]=1;c-=w[i];}if (i<=n) x[i]=c/w[i];//最后一个物品运行部分转入}3、多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。

作业不能拆分成更小的子作业。

实验步骤：1）、把作业按加工所用的时间从大到小排序2）、如果作业数目比机器的数目少或相等，则直接把作业分配下去3）、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。

typedef struct Job{int ID;//作业号int time;//作业所花费的时间}Job;typedef struct JobNode //作业链表的节点{int ID;int time;JobNode *next;}JobNode,*pJobNode;typedef struct Header //链表的表头{int s;pJobNode next;}Header,pHeader;int SelectMin(Header* M,int m){int k=0;for(int i=1;i<m;i++){if(M[i].s<m[k].s)k=i;}return k;}思考问题：1、贪心算法与动态规划思想解题的区别？1、哈夫曼编码问题的编程实现？实验三动态规划算法实验目的：理解动态规划算法的思想实验课时：4学时实验原理：动态规划算法思想：把待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解得到原问题的解，但动态规划求解过的子问题的结果会被保留下来，不像递归那样每个子问题的求解都要从头开始返回求解。