《计算机算法与设计分析实验报告》由会员分享，可在线阅读，更多相关《计算机算法与设计分析实验报告（20页珍藏版）》请在金锄头文库上搜索。
1、计算机算法与设计分析实验报告班级： 姓名：学号：目录实验一 分治与递归 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、 通过本实验加深对递归过程的理解二、实验内容
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
3、,m-1)+1;return q(n,m-1)+q(n-m,m);实验结果： 结果分析：实验时入得数据为：所要划分的整数是7，他的划分的最大加数的值不得大于7，根据实际其划分的情况为15种，因而可知其程序的运行结果是正确的。二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、程序代码：#include
4、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+)coutboar
5、dij ;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型骨牌覆盖右下角 board
6、tr + 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
7、 = 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在数组中的位置。三、
8、程序代码：#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-
9、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
10、,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 *
