算法实验报告

1、贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件101实验日期：2012-10-23姓名：学号：指导教师：实验序号：一实验成绩：一、实验名称分治算法实验-棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。三、实验环境Visual C+四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学 尝试消去递归求解。五、算法描述及实验步骤分治算法原理：分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到 子问题规模小到可以直

2、接求解。棋盘覆盖问题描述：在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方 格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的 将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能 否不用栈，直接消除递归，为什么？六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。通过对本实验的学习，对分治算法有了进一步的认识，对棋盘覆盖问

3、题和其他分治问题进行了对比。八、附录源程序(核心代码)清单或使用说明书，可另附纸/覆盖左下角子棋盘if(dr=tr+s&dc=tr+s&dc=tc+s) chessboard(tr+s,tc+s,dr,dc,s);else(boardtr+stc+s=t;chessboard(tr+s,tc+s,tr+s,tc+s,s);int main()(int k,tr,tc,size,i,j;cinktrtc;size=pow(2,k);chessboard(0,0,tr,tc,size);for(i=0;isize;i+)(for(j=0;jsize;j+) coutboardij; coutend

4、l;#include#include#includeusing namespace std;int board100100,tile=1;void chessboard(int tr,int tc,int dr,int dc,int size)/tr 棋盘左上角方格的行号，tc棋盘左上角方格的列号。 dr特殊方格所在的行号。dc特殊方格所在的列号。size棋盘的大小2Ak.(int s;if(size=1)return ;int t=tile+;s=size/2;覆盖左上角棋盘if(drtr+s&dctc+s)chessboard(tr,tc,dr,dc,s);else(boardtr+s-1

5、tc+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(boardtr+s-1tc+s=t;chessboard(tr,tc+s,tr+s-1,tc+s,s);贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件101实验日期：2012-11-6姓名：学号：指导教师：实验序号：二实验成绩：一、实验名称动态规划实验-滑雪问题二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对动态规划算法的理

6、解；三、实验环境任意C或C+编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、找到题号为1088的题目-滑雪，阅读题目，建立其最优解的递归 表达式；3、使用备忘录式的动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子 问题，就可能导致大量的重复计算。为了避免这些重复的计算，可以考虑的一个 办法就是动态规划算法。为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含 了子问题的最优解。滑雪问题描述：Michael喜欢滑雪百这并不奇怪，因为滑雪的确很

7、刺激。可是为了获得速度， 滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降 机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。 数组的每个数字代表点的高度。下面是一个例子1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-.-3-2-1更长。事实上，这是最长的一条。Input输入的第一行表示区域的行数R和列数C(1 = R,C = 10

8、0)。下面是R行， 每行有C个整数，代表高度h，0=h=10000。Output输出最长区域的长度。实验步骤：1、建立滑雪问题的解的递归表达式递归表达式如下：if(dpij l- 口L 2 34 5LB1718196IS24ssaa714%5221RIM1511侦925Presc any cj tc continue七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。通过本实验的学习，我对递归算法有了进一步的了解，在验证试验结果时， 首先输入5行5列的数组大小和数据，主函数调用DP(inti,intj)函数，求出最 长的路径；该算法的在时间复杂度上得进一步改进，如果对于大一点的

9、数据，遍 历效率就不高了。八、附录源程序(核心代码)清单或使用说明书，可另附纸#include #include #include using namespace std;const int M = 110;int a42 = -1,0,1,0,0,-1,0,1;int dpMM;int mapMM;int ans,tmp;int R,C;int DP(int i, int j)if (dpij 0)return dpij;for (int k = 0; k = 1) & (i+ak0 = R) & (j+ak1 =1) & map i+ak0 j+ak1 mapij)if(dpij R C;

10、for (i = 1; i = R; i+)for(int j = 1; j = C; j+) scanf(%d”,&mapij);for (i = 1; i = R; i+)for(int j = 1; j = C; j+)int aa = DP(i,j);if (ans aa)ans = aa;cout ans + 1 y) N += (b - y + 8 ) / 9;x = 36 * N - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b;if(a x) N += ( a - x + 35 ) / 36;3、分析出算法复杂度该算法只需计算一下产品存放的空

11、间，不满足则装在另外的箱子里，满足则 放入箱子，只需进行简单的比较即可，故所需的时间复杂度为O（n）。六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果。按输入示例输入数据如下：七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。通过对本实验的学习，我解决问题的思路很重要，一个清晰的解题思路，可以带来高效的解题效率；但是对于贪心算法，我还不太熟 悉，在以后的学习中要对该算法多加练习，直到掌握。八、附录源程序（核心代码）清单或使用说明书，可另附纸#include void main()int N, a, b, c, d, e, f, y, x;

12、int u4 = 0, 5, 3, 1);while (1)scanf(%d%d%d%d%d%d”, &a, &b, &c, &d, &e, &f);if (a = 0 & b = 0 &c=0&d= 0&e= 0 & f = 0) break;N = f + e + d + (c + 3)/4;y = 5 * d + uc % 4;if (b y) N += (b - y +8) / 9;x = 36 * N - 36 * f - 25* e-16*d - 9*c-4 * b;if (a x) N += ( a - x + 35 ) / 36;printf(%dn”, N);)贵州大学计算机

13、科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件101实验日期：2012-12-4姓名：学号：指导教师：实验序号：四实验成绩：一、实验名称回溯算法实验-频道分配问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对回溯算法的理解；三、实验环境任意C或C+编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1129的题目-频道分配；2、阅读题目，分析出求解该问题的思路；3、使用回溯算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤回溯算法原理：回溯法

14、是一个既带有系统性又带有跳跃性的搜索算法，用它可以系统地搜索 一个问题的所有解或任一解。它在问题的解空间树中，按深度优先的策略，从根 结点出发搜索解空间树。算法搜索全解空间树的任一结点时，先判断该结点是否 包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向 其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已经被搜索 遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。频道分配问题描述：当个无线站广播覆盖个非常大的区域时，需要使用转发器转发增强信 号。然而，每个转发器使用的频道数必须仔细的选择，以

15、使得相邻的转发器之间 不会相互干扰。它们相互不干扰的条件是相邻的转发器使用不同的频道。因为无线频谱是非常稀有的资源，因此，所给的转发器网络使用的频道数量 必须最小化。你需要写一个程序读出转发器网络的描述，然后算出最小需要的频 道数量。注意：邻接关系具有对称性，如果A邻接B，则B邻接A。另外，因为转 发器网络是平面的，所以通道不会交叉。输入输入由若干转发器网络的地图组成。每个地图的第一个行是转发器数量（1 至26，用0表示输入结束）。每个转发器由字母A至Z标识，每行列出和一个转发 器邻接的相邻转发器。输出对于每一个转发器网络地图，输出最少占用的频道数量（注意单复数）。例子输入2A:B:4A:BC

16、B:ACDC:ABDD:BC4A:BCDB:ACDC:ABDD:ABC0例子输出1 channel needed.channels needed.channels needed.实验步骤：1、建立频道分配问题的解题思路首先构建回溯算法的基本框架，对每输入的若干转发器网络的地图（行数: lines），都对其所有可能的路径进行比较，找出相邻路径不同的组合即可。2、构造算法框架构造频道分配问题回溯算法如下:回溯算法实现void backtrack(int x)if (x = lines)int get=0;for (int i=0;iget)get = resulti;if(getm)m = get

17、;return;int j;for (int i=1;i=4;i+)for(j=0;jlines&lines)主函数调用实现while (cinlines&lines)int step = 1;m = 5;memset(set,0, sizeof (set);memset(result,0, sizeof (result);for (int i=0;ich;for(int j=2;chj!=0 ;j+) setichj-A=1;result0 = 1;backtrack(1);根据该算法的调度可知，每输入一个行数，遍历整个子树需要树的深度时间， 即O（N）时间，找到一个满足条件的值就跳出。六、

18、调试过程及实验结果 按照输入示例输入数据如下:E Cz- Documents and SeHinWascTDebiJ叭klj.exe- X2A：B：1 channel needed.4A：BCB：ACDC：ABDD：BCchannels needed.4A： BCDB：ACDC：ABDD：ABCchannels needed.Ppess any key to continue由此可知，调试结果与预期结论一致。七、总结通过对本实验的学习，我对回溯算法有了进一步的理解，在解决 问题和分析问题上的能力得到了一定的锻炼。不过，在本次实验过程 中，也遇到一些困难，比如，刚开始在算法逻辑上没有考虑周全，使

19、 得调试结果屡次出错，后通过同学的查找，我发现了错误并给予解决。八、附录源程序（核心代码）清单或使用说明书，可另附纸#includeusing namespace std;#define MAX 27int setMAXMAX;int resultMAX;int lines;int m;void backtrack(int x)if (x = lines)int get=0;for (int i=0;iget)get = resulti;if (getm)m = get;return;int j;for(int i=1;i=4;i+)for(j=0;jlines;j+)if (setxj=1&

20、resultj=i) break;if (j=lines)(resultx = i;backtrack(x+1);int main()贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：软件101实验日期：2012-12-4姓名：学号：指导教师：实验序号：五实验成绩：一、实验名称动态规划算法-邮局问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对动态规划算法的理解；三、实验环境C+编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1160号题目-邮局问题；2、阅读题目

21、，分析出求解该问题的思路；3、使用动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子问题， 就可能导致大量的重复计算。为了避免这些重复的计算，可以考虑的一个办法就是动态 规划算法。为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含了子问 题的最优解。邮局问题描述：There is a straight highway with villages alongside the highway. The highway is represented as an

22、integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.Post offices will be built in some, but not necessari

23、ly all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.You are to write a program which, given the positions

24、 of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.【题日大意】：用数轴描述一条高速公路，有V个村庄，每一个村庄坐落在 数轴的某个点上，需要选择P个村庄在其中建立邮局，要求每个村庄到最 近邮局的距离和最小。OutputThe first line contains one integer S, which is the sum of all distanc

25、es between each village and its nearest post office.Sample Input10 51 2 3 6 7 9 11 22 44 50Sample Output9实验步骤:1、建立邮局问题的解题思路【题日大意】：用数轴描述一条高速公路，有V个村庄，每一个村庄坐落 在数轴的某个点上，需要选择P个村庄在其中建立邮局，要求每个村庄到 最近邮局的距离和最小。【解题分析】：就假设有m个村庄，分别为V1V2 V3Vm，要建n个邮 局，分别为P1 P2 P3Pn。1、考虑在m个村庄中只建立【一个】邮局的情况，显然可以知道，将邮局 建立在中间的那个村庄即可。也就

26、是在V1到Vm间建立一个邮局，若使消 耗最小，则应该将邮局建立在(V+Vm)/2这个村庄上。2、接下来考虑建立【多个】邮局的问题。不妨设，该邮局建在Vk+i.Vm之 间的某个村庄里，而且规定Vk+1.Vm之间再不允许建立其他邮局了。因此， 剩下的n-1个邮局必然出现在Vi.Vk之间的村庄内，这样问题就转换成： 在前k个村庄里选n-1个邮局的问题。3、状态表示，由上面的讨论，可以设两个数组设dp( m,n )表示在VVm之间建立n个邮局时的最短距离。L( i, j )表示在V；Vj之间建立一个邮局的最短距离。dp(k,n-1)L(k+1,m)1K K+1mdp(m,n)注：dp(m,n)表示前m个村庄中选n个邮局dp(k,n-1)表示前k个村庄中选n-1个邮局L (k+1, m)表示在Vk+1.Vm之间再建立一个邮局2、构造算法框架DP