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

计算机算法与设计分析实验报告班级： 姓名：学号：目录实验一 分治与递归 1 1、基本递归算法1 2、棋盘覆盖问题2 3、二分搜索3 4、实验小结5实验二 动态规划算法 5 1、最长公共子序列问题 5 2、最大子段和问题7 3、实验小结8实验三 贪心算法 8 1、多机调度问题8 2、用贪心算法求解最小生成树10 3、实验小结12实验四 回溯算法和分支限界法12 1、符号三角形问题 12 2、01背包问题14 3、实验小结 18 实验一 分治与递归（4学时）一：基本递归算法一、实验目的与要求1、 熟悉C/C+语言的集成开发环境；2、 通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。#include using namespace std;int main()int a,b,c;int q(int n,int m);cout请输入整数及大于最大加数的数ab; c=q(a,b);cout所需要的划分数为：cendl;return 0;int q(int n,int m)if (n1)|(m1) return 0;if (n=1)|(m=1) return 1;if (nm) return q(n,n);if (n=m) return q(n,m-1)+1;return q(n,m-1)+q(n-m,m);实验结果： 结果分析：实验时入得数据为：所要划分的整数是7，他的划分的最大加数的值不得大于7，根据实际其划分的情况为15种，因而可知其程序的运行结果是正确的。二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、程序代码：#include using namespace std;int tile=0; /全局变量，表示特殊格的号int board10001000;int main()int tr, tc, dr, dc, size;int tile=0; /全局变量，表示特殊格的号void chessBoard(int tr, int tc, int dr, int dc, int size);cout输入数据trtcdrdcsize;coutendlendl;chessBoard(tr, tc, dr, dc, size);for(int i=1;i=size;i+)for(int j=1;j=size;j+)coutboardij ;coutendl;return 0;void chessBoard(int tr, int tc, int dr, int dc, int size)/左上角行号、列号，特殊格的行号、列号棋盘大小 if (size = 1) return; /?tiao chu 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在数组中的位置。三、程序代码：#include using namespace std;int main()int const length=100;int n,x;int alength;cout依次输入数组的长度，数组内容，要查找的数n; /输入数组的长度for(int i=0;iai;cinx; void BinarySearch(int a,int n,int x); BinarySearch(a, n, x);return 0;void BinarySearch(int a,int n,int x) /n:数组长度，i，j分别表示下标 int i,j,mid=0,left=0; int right=n-1; while(left=0) int mid=(left+right)/2; if(x=amid)i=j=mid;break; if(xamid)left=mid+1;elseright=mid-1; if (i=j)&(i=0)cout所找的数据在数组中下标为：iendl;elsei=right;j=left;cout所找的数据不在数组中，其前后下标为：i,jendl;如上图所示数组的长度为5，其内容依次为1 2 3 4 5，所要找的数据位3，他的下表正好是2，结果是正确的如上图数组的长度为7，输入的数组是1 3 4 6 7 8 9，所要查找的数字式5，它不在数组中，其前后的下表分别为2,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的公共子序列。三、实验程序#includeusing namespace std;int fun(char *x)char *y=x;while(*y+);return y-x-1;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 =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);int main()char x50,y50;int m,n;int *c =new int*50,*b =new int*50;for(int i=0;i50;i+)ci =new int50;bi =new int50;/int c5050,b5050;coutx;couty;m=fun(x);n=fun(y);LCSLength(x,y,m,n,c,b);LCS(m,n,x,b);coutendl;return 0;四、运行结果二：最大子段和问题一、实验目的与要求1、熟悉最长最大字段和问题的算法；2、进一步掌握动态规划算法；二、实验题若给定n个整数组成的序列a1，a2，a3，an，求该序列形如aiai1an的最大值。三、程序清单#includeusing namespace std; int MaxSum(int n,int *a,int &besti,int &bestj) int sum=0; for(int i=0;in;i+) int thissum=0; for(int j=i;jsum) sum=thissum; besti=i; bestj=j; return sum; int main()int *a=new int50;int x,n,besti,bestj;coutn;cout请输入字符串中的每个数字： ;for(int i=0;iai;x=MaxSum(n,a,besti,bestj);cout最大子段和为：起始位置：besti+1至bestj+1结果为：xendl;return 0;四、运行结果实验小结第一个求公共子序列感觉和递归查询差不多，然后再查询第二列进行对比！最大子段和感觉就像求整列的和！实验三 贪心算法（2学时）一：多机调度问题一、实验目的与要求1、熟悉多机调度问题的算法；2、初步掌握贪心算法；二、实验题 要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。三、实验程序#include using namespace std;typedef struct Job int ID;/作业号 int time;/作业所花费的时间Job;Job J10;typedef struct JobNode /作业链表的节点 int ID; int time; JobNode *next;JobNode,*pJobNode;typedef struct Header /链表的表头,不同的机器？ int s; /表示其最大的容量 pJobNode next;Header,*pHeader; /int l=1;int main()/Job J10;Header M10;int m,n; /机器的个数cout请输入数据作业的个数与机器的个数nm;cout请输入所有的任务的相关数据endl;for(int i=1;i=m;i+)Mi.s=0; /表示其最大容量for( l=1;lJl.IDJl.time;int SelectMin(Header* M,int m);/SelectMin(M,m);for(l=1;l=n;l+)cout第l个任务在第MSelectMin(M,m)台机器上完成endl;return 0;int SelectMin(Header* M,int m) /有几台机器，就创建几个链表 int k=1; for(int i=1;i=m;i+) if(Mi.s=M1.s) /最小的加入,s标识时间的和值k=i; Mk.s+=Jl.time; return k; /k是标识第几台机器加入作业五、实验结果二：用贪心算法求解最小生成树一、实验要求与目的1、 熟悉贪心算法的基本原理与适用范围。2、 使用贪心算法编程，求解最小生成树问题。二、实验内容1、 任选一种贪心算法（Prim或Kruskal），求解最小生成树。对算法进行描述和复杂性分析。编程实现，并给出测试实例三、实验程序#include using namespace std;int const inf=100; int main()int n=6;cout所给图的最小生成树一次选定的边是表示为：endl;int c77=inf,inf,inf,inf,inf,inf,inf,inf,inf,6,1,5,inf,inf,inf,inf,inf,5,inf,3,inf,inf,1 , 5,inf,5,6,4,inf,5,inf,5,inf,inf,2,inf,inf,3,6,inf,inf,6,inf,inf,inf,4,2,6,inf;/c12=6;c14=5;c13=1;c23=5;c34=5;c25=3;c26=2;/c35=6;c36=4;c56=6;c21=6;c41=5;c31=1;c32=5;c43=5;c52=3;c62=2;/c53=6;c63=4;c65=6;void prim(int n,int c77);prim(n,c);return 0;void prim(int n,int c77)int lowcost7;int closet7;bool s10;s1=true;for(int i=2;i=n;i+)lowcosti=c1i;closeti=1;si=false;int j=1; for(i=1;in;i+)int min=inf;int j=1;for(int k=2;k=n;k+)if(lowcostk0)min=lowcostk;j=k;coutjclosetjendl; sj=true;for(k=2;k=n;k+)if(cjklowcostk)&(!sk)lowcostk=cjk;closetk=j;四、实验结果五、实验小结贪心算法上课老师讲的时候也能听懂，讲的例子也能明白，但是在实际调度时遇到了不小的麻烦！最后在老师和同学的帮助下完成了！尽管自己没有做出来，但是对贪心算法的实际操作有了更一步的把握！实验四 回溯算法和分支限界法（2学时）一：符号三角形问题一、实验目的与要求1、掌握符号三角形问题的算法；2、初步掌握回溯算法；二、实验题图下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相三、实验程序#include using namespace std;typedef unsigned char uchar;int sum; uchar* p; /符号存储空间；/表示满足要求的三角形个数char ch2=+,-; int n; /第一行符号总数int half; int count; /用来计算-的个数void BackTrace(int t)if (tn)sum+;cout第sum个三角形：endl;for (int i=1;i=n;i+)for (int j=1;ji;j+)cout ;for (j=1;j=n-i+1;j+)coutchpij ;coutendl;elsefor (int i=0;i=1;i+)p1t=i;/确定第一行第t个的值；count+=i;/用来计算-的个数；for (int j=2;j=t;j+)pjt-j+1=pj-1t-j+1pj-1t-j+2;/第一行大于等于2时确定后面从第2行开始增加的一count+=pjt-j+1;/列中符号，计算-个数；if (count = half & (t*(t+1)/2-count) = half) /约束条件；BackTrace(t+1);for (j=2;j=t;j+) /回溯，判断另一种符号情况；count-=pjt-j+1;count-=p1t; int main()coutn;count=0;sum=0;half=n*(n+1)/2;if (half%2=0)half=half/2;p=new uchar* n+1;for (int i=0;i=n;i+)pi=new ucharn+1;memset(pi,0,sizeof(uchar)*(n+1);BackTrace(1);for (i=0;i=n;i+)delete pi;delete p;cout满足要求的三角形符号共有：sum个;elsecout不存在这样的三角形符号！;return 0;五、实验结果二：01背包问题一、实验目的与要求1、掌握01背包问题的回溯算法；2、进一步掌握回溯算法；二、实验题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?三、实验程序#includeusing namespace std;class Knapfriend int Knapsack(int p,int w,int c,int n );public:void print()for(int m=1;m=n;m+)coutbestxm ;coutendl;private:int Bound(int i);void Backtrack(int i);int c;/背包容量int n; /物品数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前重量int cp;/当前价值int bestp;/当前最优值int *bestx;/当前最优解int *x;/当前解;int Knap:Bound(int i)/计算上界int cleft=c-cw;/剩余容量int b=cp;/以物品单位重量价值递减序装入物品while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;/装满背包if(in)if(bestpcp)for(int j=1;j=n;j+)bestxj=xj;bestp=cp;return;if(cw+wibestp)/搜索右子树xi=0;Backtrack(i+1);class Objectfriend int Knapsack(int p,int w,int c,int n);public:int operator=a.d);private:int ID;float d;int Knapsack(int p,int w,int c,int n)/为Knap:Backtrack初始化int W=0;int P=0;int i=1;Object *Q=new Objectn;for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi;if(W=c)return P;/装入所有物品/依物品单位重量排序float f;for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f; Knap K;K.p = new intn+1;K.w = new intn+1;K.x = new intn+1;K.bestx = new intn+1;K.x0=0;K.bestx0=0;for( i=1;i=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;/回溯搜索K.Backtrack(1);K.print();delete Q;delete K.w;delete K.p;return K.bestp;void main()int *p;int *w; int c=0;int n=0;int i=0;cout请输入背包个数：n;p=new intn+1;w=new intn+1;p0=0;w0=0;cout请输入各背包的价值：endl;for(i=1;ipi;cout请输入各背包的重量：endl;for(i=1;iwi;cout请输入背包容量：c;coutKnapsack(p,w,c,n)endl;四、实验结果实验小结：符号三角形问题以前在学C+时，自己做出来过这种图形，不过没有这么多，而且算法也不一样！原打算上周交的，最近在复习软件工程就一直没有弄这个！0-1背包问题也学了好多，但是学的不是很深，感觉有点看不透！最后感谢老师和同学的帮助及指导！