算法设计与分析实验报告.doc

算法设计与分析课程报告课题名称：_算法设计与分析_课题负责人名（学号）： 同组成员名单（角色）： 指导教师： 评阅成绩： 评阅意见： 提交报告时间：2013年 6月 12日第二章 递归与分治策略2-3 改写二分搜索算法1. 问题描述：设a0:n-1是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。2. 分析与证明：设a0:n-1是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相等，均为x在数组中的位置。 3. 代码实现：template int BinarySearch(Type a ,const Type& x,int left,int right, int &i, int &j ) while (left=right) int mid = (left+right)/2; if (x = amid) i=j=mid; return 1; if (x amid) right = mid-1; else left = mid+1; i=right; j=left;/或i=left-1;j=left return 0; 5.问题：改写二分搜索算法，返回小于x的最大元素位置i和大于x的最小元素位置j。当找到与x同的元素时，i和j相同，均为x在数组中的位置第三章 动态规划3-5 编辑距离问题1. 问题描述：设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：1) 删除一个字符；2) 插入一个字符；3) 将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称谓字符串A到B的编辑距离，记为d（A,B）。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d（A,B）。2. 分析与证明：a. 开一个二维数组dij来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求 b. 具体算法： c. 首先给定第一行和第一列，然后，每个值di,j这样计算：dij = min(di-1j+1, dij-1+1, di-1j-1+(s1i=s2j?0:1); d. 最后一行，最后一列的那个值就是最小编辑距离3. 代码实现：#include #include #include #include int i,j;char* s1 = new char80;char* s2 = new char80;int md8181; int min(int a, int b, int c); int editDistance(int len1, int len2); /最短编辑距离void main() fstream inDst;inDst.open(E:input.txt,ios:in,0); inDsts1; inDsts2; inDst.close();fstream outDst;outDst.open(E:output.txt,ios:app,0); outDsteditDistance(strlen(s1), strlen(s2); outDst.close(); int min(int a, int b, int c) int temp=(ab) ? a : b; return (tempc) ? temp : c; /最短编辑距离int editDistance(int len1, int len2) /当某一个字符串为空时，最短编辑距离是另外一个字符串的长度。 for(i=0; i=len1; i+) mdi0=i; for(j=0; j=len2; j+) md0j=j; for(i=1; i=len1; i+) for(j=1; j=len2; j+) int cost=(s1i-1=s2j-1) ? 0 : 1; int delet=mdi-1j+1; int insert=mdij-1+1; int substit=mdi-1j-1+cost; mdij=min(delet, insert, substit); return mdlen1len2; 4. 测试数据：Input.txtfxpimuxwrs运行结果：Output.txt 55复杂度分析：二重for循环复杂度为O(n2)第四章 贪心算法4-9 汽车加油问题1. 问题描述：一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。2. 证明与分析：1 解题思路： 先判断是否有解，再对数组从1到k+1计算尽量往前走，直至不能走就+1，计算出最大2 算法策略：贪心算法3 基本变量描述： data和数组a都是用来保存k+1个距离值，sum和total均用来记录最少加油次数，total=-1表无解3. 代码实现：#include#include#include#includeint CarInGas(int a,int n,int k);int main()int i,k,n,data100,total;fstream rData;rData.open(E:input.txt,ios:in,0);rDatank;for(i=1;idatai;total = CarInGas(data,n,k);rData.close();fstream wData;wData.open(E:output.txt,ios:app,0);if(!wData)coutFalse to open file.endl;if(total=-1)coutNo solution!endl;wDataNo solution!endl;elsecouttotalendl;wDatatotalendl;wData.close();system(pause);return 0;int CarInGas(int a100,int n,int k)int i,sum=0,curDistan=0;for(i=1;in)return -1;for(i=1;in)sum+;curDistan=ai;return sum;4. 测试数据：Input.txt7 71 2 3 4 5 1 6 6运行结果：Output.txt45. 复杂度分析： for(i=1;idatai; 复杂度为：O(n) CarInGas(a,n,k)也为 O(n) 两者互不嵌套，所以为O(n) 第五章 回溯法5-13 工作分配问题1. 问题描述：设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法。为每一个人都分配1件不同的工作，并使总费用达到最小。2. 分析与证明：由于每个人都必须分配到工作，在这里可以建一个二维数组allotij，用以表示i号工人完成j号工作所需的费用。给定一个循环，从第1个工人开始循环分配工作，直到所有工人都分配到。为第i个工人分配工作时，再循环检查每个工作是否已被分配，没有则分配给i号工人，否则检查下一个工作。可以用一个一维数组flagj来表示第j 号工作是否被分配，未分配则flagj=0，否则flagj=1。利用回溯思想，在工人循环结束后回到上一工人，取消此次分配的工作，而去分配下一工作直到可以分配为止。这样，一直回溯到第1个工人后，就能得到所有的可行解。在检查工作分配时，其实就是判断取得可行解时的二维数组的一下标都不相同，二下标同样不相同。这样，得到了所有的可行解。为了得到最少的费用，即可行解中和最小的一个，故需要再定义一个全局变量cost表示最终的总费用，初始cost为allotii之和，即对角线费用相加。在所有工人分配完工作时，比较sumFare与cost的大小，如果sumFare小于cost,证明在回溯时找到了一个最优解，此时就把sumFare赋给cost。 考虑到算法的复杂度，可以设计一个剪枝函数。就是在每次计算局部费用变量sumFare的值时，如果判断sumFare已经大于cost，就没必要再往下分配了，因为这时得到的解必然不是最优解。3. 代码实现：#include#include /using namespace std;#include int n; int cost=0; /现行最小费用int flag100; /工作是否被分配，“1”代表已分配int allot100100; /表示i号工人完成j号工作的费用int WorkAllocation(int i,int sumFare);int main()fstream rData;rData.open(E:input.txt,ios:in,0);rDatan; for(int i=1;i=n;i+) for(int j=1;jallotij;flagj = 0; cost+=allotii; /对角线费用相加，用于剪枝 rData.close();fstream wData;wData.open(E:output.txt,ios:app,0);if (!wData)coutFalse to open file.endl; wDataWorkAllocation(1,0)n & sumFarecost) /大于cost则必定不是最优解，跳过cost = sumFare;return 1; if(sumFarecost)for(int j=1;j=n;j+)if(flagj = 0) flagj = 1; WorkAllocation(i+1,sumFare+allotij); flagj = 0; return cost;4. 测试数据：Input.txt310 2 32 3 43 4 5运行结果：Output.txt 95.复杂度分析:从main函数中的for循环中可以看出其算法复杂度为O(n2)第六章 分支限界法6-6 n皇后问题1. 问题描述：在n x n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题等价于在n x n各的棋盘上放置n个皇后，任何两个皇后不放在同一行或者同一列或者同一斜线上。设计一个解n皇后问题的队列式分支限界法，计算在n x n个方格上放置彼此不受攻击的n个皇后的一个放置方案。2. 分析与证明：题目要求我们只需要输出摆放皇后的一中解，所以在分支限界法时，每一种皇后的摆放即为一条分支，而遍历解空间相当于广度优先遍历树，因此只要将n个皇后摆放完成，便可以输出解，并不存在最优解的情况。3. 代码实现：#include #include #include using namespace std;fstream minput(D:input.txt); fstream moutput(D:output.txt); class Nodepublic: Node(int n) t=0; this-n=n; loc = new intn+1; for (int i=0;it=other.t; this-n=other.n; this-loc=new intn+1; for (int i=0;iloci=other.loci; int t; int *loc; int n; bool checkNext(int next); void printQ();bool Node:checkNext(int next) int i; for (i=1;i=t;+i) if (loci=next) return false; if (loci-next=t+1-i) return false; if (loci-next=i-t-1) return false; return true;void Node:printQ() for (int i=1;i=n;+i) moutputloci ; moutputn=n; ansNum=0; void ArrangQueen();void Queen:ArrangQu