算法设计与分析案例.doc
实验一 C/C+环境及递归算法（4学时）一、实验目的与要求1、 熟悉C/C+语言的集成开发环境；2、 通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握排列问题的递归算法和Hanoi塔问题的递归算法。三、实验题1、设计一个递归算法生成n个元素r1,r2,rn的全排列。任意输入一串整数或字符，输出结果能够用递归方法实现整数或字符的全排列。2、设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。四、实验步骤1 理解算法思想和问题要求；2 编程实现题目要求；3 上机输入和调试自己所编的程序；4 验证分析实验结果；5 整理出实验报告。实验提示1、#include <iostream.h> inline void swap(int &a,int &b) int temp=a; a=b; b=temp; void perm(int list,int k,int m) if(k=m) for(int i=0;i<=m;i+) cout<<listi; cout<<endl; else for(int i=k;i<=m;i+) swap(listk,listi); perm(list,k+1,m); swap(listk,listi); void main() int list3=1,2,3; perm(list,0,2); 2、void hanoi(int n, int a, int b, int c) if (n > 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 实验二 分治算法（4学时）一、实验目的与要求1、熟悉二分搜索算法和快速排序算法；2、初步掌握分治算法；二、实验题1、设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。设有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标i，0in，使得ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。2、在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。三、实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。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=amid) i=j=mid; return true; if(x>amid) left=mid+1; else right=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=amid) return mid; if(x>amid) right=mid-1; else left=mid+1; return -1; 2、template<class 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=ap; / 将< x的元素交换到左边区域 / 将> x的元素交换到右边区域 while (true) while (a+i <x); while (a- -j >x); if (i >= j) break; Swap(ai, aj); ap = aj; aj = x; return j;实验三 归并排序的分治策略设计（4学时）实验目的. 熟悉二分检索问题的线性结构表示和二分检索树表示;. 熟悉不同存储表示下求解二分检索问题的递归算法设计;. 通过实例转换, 掌握将递归算法转换成迭代算法的方法;. 掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.预习要求. 认真阅读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问题的原理或方法;. 针对线性结构表示和二分检索树表示设计递归算法;. 参考教材和课堂教学内容, 根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.算法或程序设计参考线性结构int data10= /* 10个互异的、无序的原始整数 */ ;typedef struct int s100; int top; STACK;int Partition(int *data, int low, int high)功能: 将datalow, high进行快速分类划分, 返回枢轴记录关键字的位置索引.int QSort1(int *data, int low, int high)功能: 将datalow, high进行快速分类的递归算法.int QSort2(int *data, int low, int high)功能: 将datalow, high进行快速分类的迭代算法.int BSearch1(int *data, int key)功能: 在data数组中检索key的二分检索递归算法, 成功时返回位置索引, 否则返回-1.int BSearch2(int *data, int key)功能: 在data数组中检索key的二分检索迭代算法, 成功时返回位置索引, 否则返回-1.树结构typedef struct NODE int key; struct NODE *lch, *rch; TNODE, *BT;typedef struct Parameters BT *t; int key; BT f; BT *p PARA;typedef struct PARA s100; int top; STACK;int InsertBT(BT *t, int key)功能: 在二分检索树t中插入关键字为key的元素, 成功时返回1, 否则返回0.int TSearch1(BT *t, int key, BT f, BT *p)功能: 用递归算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.int TSearch2(BT *t, int key, BT f, BT *p)功能: 用迭代算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.实验步骤1. 调试线性结构表示下的快速分类与二分检索递归程序, 直至正确为止;2. 调试线性结构表示下的快速分类与二分检索迭代程序, 直至正确为止;3. 待各功能子程序调试完毕, 去掉测试程序, 将程序整理成功能模块存盘备用.实验报告要求1. 阐述实验目的和实验内容;2. 提交实验程序的功能模块;3. 阐述将递归算法改写成迭代算法的一般方法;4. 用类C语言阐述分治法递归与迭代实现抽象控制策略. 思考与练习1. 怎样优化由递归程序改写的迭代程序?2. 设计二分检索树的构造与检索递归程序, 并将其改写成相应的迭代算法。实验四 哈夫曼编码的贪心算法设计（4学时）实验目的. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;. 编程实现哈夫曼编译码器;. 掌握贪心算法的一般设计方法。预习要求1. 认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理;2. 设计和编制哈夫曼编译码器。参考数据类型或变量typedef ElemType char；typedef struct node int w; int flag; ElemType c; struct node *plink,*llink,*rlink; char codem;Node;Node *numn, *root;参考子程序接口与功能描述void SetTree( NODE *root )功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树void EnCode( Node *p )功能: 利用已建好的哈夫曼树，对输入的正文进行编码 void DeCode( void )功能: 利用已建好的哈夫曼树，将输入的代码进行译码实验步骤1. 设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2. 设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3. 设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4. 将你的程序整理成功能模块存盘备用。实验报告要求1. 阐述实验目的和实验内容;2. 提交实验程序的功能模块;3. 记录最终测试数据和测试结果。思考题1. 试证明哈夫曼问题具有贪心选择性质；试证明哈夫曼问题具有最优子结构性质。实验五 Kruskal算法的设计（4学时）实验目的. 根据算法设计需要, 掌握连通网的灵活表示方法;. 掌握最小生成树的Kruskal算法;. 基本掌握贪心算法的一般设计方法;. 进一步掌握集合的表示与操作算法的应用.预习要求. 认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法;. 设计Kruskal算法实验程序.参考数据类型或变量typedef NodeNumber int; /* 节点编号 */typedef CostType int; /* 成本值类型 */typedef ElemType NodeNumber /* 实型或任意其它元素类型 */typedef struct int ElemType; int tag; NODE;typedef struct CostType cost; NodeNumber node1, node2; EDGE;NODE set=1,-1,n,-1; /* 节点集, n为连通网的节点数 */ EDGE es =values of e1, values of em; /* 边集, m为连通网的边数 */EDGE stn-1; /* 最小生成树的边集 */参考子程序接口与功能描述int Find(NODE *set, ElemType elem)功能: 在数组set中顺序查找元素elem, 如果不成功, 返回-1; 否则, 使用带压缩规则的查找算法,返回所在子集的根节点索引. int Union(NODE *set, ElemType elem1, ElemType elem2)功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.void Sort(EDGE *es, int n)功能: 用任意分类算法将连通图的边集按成本值的非降次序分类.void Kruskal(EDGE *es, int m, NODE *set, int n, EDGE *st)功能: 对有n个节点, m条边的连通网, 应用Kruskal算法生成最小生成树, 最小生成树的边存储在数组st中.void Output(EDGE *st, int n)功能: 输出最小生成树的各条边.实验步骤1. 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止;2. 待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成功能模块存盘备用.实验报告要求1. 阐述实验目的和实验内容;2. 阐述Kruskal算法的原理方法;3. 提交实验程序的功能模块;4. 提供测试数据和相应的最小生成树.思考与练习1. 设计由连通网初始边集数组生成最小堆的算法;2. 设计输出堆顶元素, 并将剩余元素调整成最小堆的算法;3. 针对连通网初始边集最小堆表示, 设计Kruskal算法;4. 采用成本邻接矩阵表示连通网时, 在剩余边中如何实现最小成本边的查找?采用成本邻接矩阵表示连通网时, 用C语言实现Prim算法.实验六 动态规划算法（4学时） 一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题 若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 三、实验提示include "stdlib.h"#include "string.h" void LCSLength(char *x ,char *y,int m,int n, int *c, int *b) int i ,j; for (i = 1; i <= m; i+) ci0 = 0; for (i = 1; i <= n; i+) c0i = 0; for (i = 1; i <= m; i+) for (j = 1; j <= n; j+) if (xi=yj) cij=ci-1j-1+1; bij=1; else if (ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i ,int j, char *x ,int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1,j-1,x,b); printf("%c",xi); else if (bij= 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b);实验七 动态规划算法（4学时） 一、实验目的与要求1、熟悉最长最大字段和问题的算法；2、进一步掌握动态规划算法；二、实验题 若给定n个整数组成的序列a1，a2，a3，an，求该序列形如aiai1an的最大值。三、实验提示int MaxSum(int n,int *a,int &besti,int &bestj) intsum=0; for(int i=1;i<=n;i+) for(int j=i;j<=n;j+) int thissum=0; for(int K=i;k<=j;k+)thissum+=ak; if(thissum>sum) sum=thissum; besti=i; bestj=j; return sum; int MaxSum(int n,int *a,int &besti,int &bestj) intsum=0; for(int i=1;i<=n;i+) int thissum=0; for(intj=i;j<=n;j+) thissum+=aj; if(thissum>sum) sum=thissum; besti=i; bestj=j; return sum; 实验八 回溯算法（4学时） 一、实验目的与要求1、掌握装载问题的回溯算法；2、初步掌握回溯算法；二、实验题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。三、实验提示void backtrack (int i) / 搜索第i层结点 if (i > n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi; if (cw + wi <= c) / 搜索左子树 xi = 1; cw += wi; backtrack(i + 1); cw -= wi; if (cw + r > bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi; 实验（设计）报告参考格式多段图问题的动态规划算法与实现一、 设计目的1. 掌握有向网的成本邻接矩阵表示法；2. 掌握多段图问题的动态规划递推算法；3. 进一步掌握动态规划法的基本思想和算法设计方法；二、 设计内容1 任务描述1）多段图问题简介2）设计任务简介设计求解多段图问题的动态规划算法，即设计和实现多段图问题的表示方案、动态规划递推算法，设计对算法或程序的测试方案并完成测试。2 多段图问题的表示方案本设计采用成本邻接矩阵表示多段图，针对多段图(可插入图例)描述成本邻接矩阵的规模与元素意义3 递推过程的抽象描述本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对多段图问题的求解（抽象地）描述递推过程4 主要数据类型与变量typedef NodeNumber int; /* 节点编号 */typedef CostType int; /* 成本值类型 */CostType costnn=; /* 成本邻接矩阵, n为顶点数 */NodeNumber pathk; /* k段图最短路径上的节点编号数组 */NodeNumber cur= -1; /* 当前邻接节点 */（必要时，可对数据类型和变量进一步解释或说明，增加可读性）5 算法或程序模块int FindForward(CostType *costn, NodeNumber i, NodeNumber cur)功能: 根据邻接矩阵查找节点i的下一个前向邻接节点, 成功时返回节点编号, 否则返回-1; cur为当前的前向邻接节点, 第一次调用时其值为-1.int FindBackward(CostType *costn, NodeNumber i, NodeNumber cur)功能: 根据邻接矩阵查找节点i的下一个后向邻接节点, 成功时返回节点编号, 否则返回-1; cur为当前的后向邻接节点, 第一次调用时其值为-1.（必要时，可对算法或程序模块进一步解释或说明，增加可读性）三、 测试1 方案描述测试方案、测试模块、测试数据实例（文字数据、图或表等形式）2 结果结合测试数据实例描述测试过程和测试结果，最好给出表示测试过程和结果的抓图，对测试结果进行分析并得出结论。四、 总结与讨论可针对本设计谈体会、谈改进、谈设想等，展示你的概括、归纳和创新思维能力，看重的不是你的对与错，而是鼓励你的想象和创新思维。
