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

算法设计与分析实验指导书本书是为配合算法分析与设计实践教学大纲而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。目录实验一 统计数字及字符编码（2学时）1实验二 蛮力法（2学时）3实验三 递归与分治法（2学时）5实验四 贪心算法（2学时）8实验五 回溯算法（2学时）10实验六 分支限界法（2学时）12实验七 动态规划算法（3学时）15实验一 统计数字及字符编码（2学时）一、实验目的与要求1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C+语言描述算法的方法。 4实现具体的编程与上机实验验证算法的时间复杂性函数二、实验内容 1、统计数字问题 1）问题描述一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示而不是06或006等。数字计数问题要求对给定书的总页码n计算出书的全部页码中分别用到多少次数字0、1、2、9。 2）编程任务给定表示书的总页码的10 进制整数n (1n109) 。编程计算书的全部页码中分别用到多少次数字0、1、2、9。3）程序算法将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个19作为个位数，余数代表有1余数本身这么多个数作为剩余的个位数。此外，商还代表1商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。2、字典序问题1）问题描述在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小 写英文字母组成A=a,b,z。该字母表产生的升序字符串是指字符串中字母按照从左到 右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1 次。例如， a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的所有长度不超过6 的升序 字符串按照字典序排列并编码如下。12262728abzabac对于任意长度不超过6 的升序字符串，迅速计算出它在上述字典中的编码。算法设计：对于给定的长度不超过6 的升序字符串，计算出它在上述字典中的编码。 数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第一行是一个正整数k，表示接 下来共有k行。接下来的k 行中，每行给出一个字符串。结果输出：将计算结果输出到文件output.txt中。文件共有k 行，每行对应于一个字符串的编码。实验二 蛮力法（2学时）一、实验目的与要求1、 掌握蛮力法的基本思想2、 使用蛮力法解决具体问题（通常，问题规模比较小时，此方法才有意义）二、实验内容 1、用C+/C编写程序实现BF算法，进行模式匹配。以下是该算法的伪代码，请进行调试。int BF(char S , char T ) i=0; j=0; while (istrlen(S) & j=strlen(T) return (i-j); else return 0;2、用C+/C编写程序实现KMP算法，进行模式匹配。 求模式串T的Next数组void GetNext(char T , int next ) next1=0; j=1; k=0; while (jT0) if (k= =0)| |(Tj= =Tk) j+; k+; nextj=k; else k=nextk; KMP算法伪代码1. 在串S和串T中分别设比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如果Si=Tj，则继续比较S和T的下一个字符；否则 2.2 将j向右滑动到nextj位置，即j=nextj； 2.3 如果j=0，则将ii+1，j=1，准备下一趟比较； 3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回03、以源串“ababcabccabccacbab”和模式串”abccac”w为例，编写程序，给出采用BF算法和KMP算法进行串匹配过程中的字符比较次数。实验三 递归与分治法（2学时）基本题一：基本递归算法一、实验目的与要求1、 熟悉C/C+语言的集成开发环境；2、 通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、实验步骤1 理解算法思想和问题要求；2 编程实现题目要求；3 上机输入和调试自己所编的程序；4 验证分析实验结果；5 整理出实验报告。基本题二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题： 盘覆盖问题：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、实验提示void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 提高题一：二分搜索一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。2、设有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标I，0in，使得ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。三、实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。bool BinarySearch(int a,int n,int x,int& i,int& j) int left=0; int right=n-1; while(leftamid) 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(leftamid) right=mid-1; else left=mid+1; return -1;提高题二： 用分治法实现元素选择一、实验要求与目的1、了解分治法的基本思想，掌握递归程序编写方法；2、使用分治法编程，求解线形序列中第k小元素。二、实验内容1、 给定线形序列集中n个元素和一个整数k，1kn，输出这n个元素中第k小元素的值及其位置。2、 简述该算法的原理、步骤。对该算法与直接排序查找进行比较。3、 编写并调试程序。测试要求：元素个数不少于100；分三种情况：k=1、k=n和k=中位数。实验四 贪心算法（2学时）基本题一：多机调度问题一、实验目的与要求1、熟悉多机调度问题的算法；2、初步掌握贪心算法；二、实验题 要求给出一种作业调度方案，使所给的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;im;i+) if(Mi.shalf)|(t*(t-1)/2-counthalf) return; if (tn) sum+; else for (int i=0;i2;i+) p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; Backtrack(t+1); for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; 基本题二：01背包问题一、实验目的与要求1、掌握01背包问题的回溯算法；2、进一步掌握回溯算法；二、实验题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?三、实验提示templateTypep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i H(1000); T *MinOut = new T n+1; / 计算MinOut = 离开顶点i的最小耗费边的耗费 T MinSum = 0; / 离开顶点i的最小耗费边的数目 for (int i = 1; i = n; i+) T Min = NoEdge; for (int j = 1; j = n; j+) if (aj != NoEdge & (aj Min | Min = NoEdge) Min = aj;if (Min = NoEdge) return NoEdge; / 此路不通 MinOut = Min; MinSum += Min; / 把E-节点初始化为树根 MinHeapNode E; E.x = new int n; for (i = 0; i n; i+) E.x = i + 1; E.s = 0; / 局部旅行路径为x 1 : 0 E.cc = 0; / 其耗费为0E.rcost = MinSum; T bestc = NoEdge; / 目前没有找到旅行路径 / 搜索排列树 while (E.s n - 1) / 不是叶子 if (E.s = n - 2) / 叶子的父节点 / 通过添加两条边来完成旅行 / 检查新的旅行路径是不是更好 if (aE.xn-2E.xn-1 != NoEdge & aE.xn-11 != NoEdge & (E.cc + aE.xn-2E.xn-1 + aE.xn-11 bestc | bestc = NoEdge) / 找到更优的旅行路径 bestc = E.cc + aE.xn-2E.xn-1 + aE.xn-11; E.cc = bestc; E.lcost = bestc; E . s + + ; H . I n s e r t ( E ) ; else delete E.x; else / 产生孩子 for (int i = E.s + 1; i n; i+) if (aE.xE.sE.x != NoEdge) / 可行的孩子, 限定了路径的耗费 T cc = E.cc + aE.xE.sE.x; T rcost = E.rcost - MinOutE.xE.s; T b = cc + rcost; /下限if (b bestc | bestc = NoEdge) / 子树可能有更好的叶子 / 把根保存到最大堆中 MinHeapNode N; N.x = new int n; for (int j = 0; j n; j+) N.xj = E.xj; N.xE.s+1 = E.x; N.x = E.xE.s+1; N.cc = cc; N.s = E.s + 1; N.lcost = b; N.rcost = rcost; H . I n s e r t ( N ) ; / 结束可行的孩子 delete E.x; / 对本节点的处理结束 try H.DeleteMin(E); / 取下一个E-节点 catch (OutOfBounds) break; / 没有未处理的节点 if (bestc = NoEdge) return NoEdge; / 没有旅行路径 / 将最优路径复制到v1:n 中for (i = 0; i n; i+) vi+1 = E.x; while (true) /释放最小堆中的所有节点 delete E.x; try H.DeleteMin(E); catch (OutOfBounds) break; return bestc; 实验七 动态规划算法（3学时）基本题一：最长公共子序列问题一、实验目的与要求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.hvoid 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 =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int