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

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

2、在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方 格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的 将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能 否不用栈，直接消除递归，为什么？六、调试过程及实验结果程序的执行结果如下图所示:七、总结通过对本次的棋盘覆盖问题的求解，对递归与分治策略有了更进一步的了 解，分治法的设计思路是：将一个难以直接解决的大问题，分割成一些规模较小 的相同问题，以便各个击破，分而治之。在实际的上机操

3、作过程中，不仅是让我 们了解数算法的理论知识，更重要的是培养解决实际问题的能力，所以相信通过 此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下 良好的基础。八、附录源程序(核心代码)：#includeusing namespace std;int tile=1;/L型骨牌的编号(递增)int board100100; 棋盘void chessBoard ( int tr, int tc, int dr, int dc, int size )if ( size=1 )棋盘方格大小为1,说明递归到最里层return;int t=tile+;每次递增 1int s=size/2

4、;棋盘中间的行、列号(相等的)检查特殊方块是否在左上角子棋盘中if ( drtr+s & dctc+s )在chessBoard ( tr, tc, dr, dc, s );else/不在，将该子棋盘右下角的方块视为特殊方块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/不在，将该子棋盘左下角的方块视为特殊方块boardtr+s-1tc+s=t;chessBoard ( tr, t

5、c+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/不在，将该子棋盘左上角的方块视为特殊方块boardtr+stc+s=t;chessBoard ( tr+s, tc+s, tr+s, tc+s, s );void main()int size;coutsize;int index_x,index_y;coutindex_xindex_y;chessBoard ( 0,0,index_x,index_y,size )

6、;for ( int i=0; isize; i+ )for ( int j=0; jsize; j+ )coutboardij”;coutendl;课程名称：算法设计与分析班级：软件121实验日期：2014 11 14姓名：熊齐超学号：1208060220指导教师：程欣宇实验序号：二实验成绩：一、实验名称动态规划实验-滑雪问题二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对动态规划算法的理解；三、实验环境任意C或C+编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、找到题号为1088的题目-滑雪，阅读题目，建立其最优解的递归 表达式；3、

7、使用备忘录式的动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子 问题，就可能导致大量的重复计算。为了避免这些重复的计算，可以考虑的一个 办法就是动态规划算法。为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含 了子问题的最优解。滑雪问题描述：Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度， 滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降 机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维

8、数组给出。 数组的每个数字代表点的高度。下面是一个例子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 = 100)。下面是R行， 每行有C个整数，代表高度h，0=h=10000。Output输出最长区域的长度。实验步骤：1、建立滑雪问题的解的递归表达式递归表达式如下：if(d

9、pij DP(i+ak0,j+ak1) + 1)dpij = DP(i+ak0,j+ak1) + 1;2、构造算法框架首先定义一个状态转移函数，用来遍历搜索所需的最长路径int DP(int i,int j).在主函数中调用DP( i,j)函数，将所求最长路径的存放在变量 ans中int main(). 3、分析出算法复杂度因为DP( int i,int j)函数每调用一次，都要对i,j周围的四个数 进行比较，这样的工作要重复进行，故需要O( n2)的时间。六、调试过程及实验结果程序的执行结果如下图所示：EA算法设计与会析Debug诵手问题.exb1 2 3 4 516 17 18 19 61

10、5 24 25 20 714 23 22 21 813 12 11 10 925Press anp key to cont inue七、总结通过对本次的滑雪问题的动态规划算法求解，对动态规划算法有了更进一步 的了解，动态规划算法的设计思路是:分治算法将大的问题变成小的问题来解决， 但是如果划分过程中出现重叠子问题，就可能导致大量的重复计算。为了避免这 些重复的计算，可以考虑的一个办法就是动态规划算法。为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含 了子问题的最优解。在实际的上机操作过程中，不仅是让我们了解数算法的理论知识，更重要的 是培养解决实际问题的能力，所以相信通过此次

11、实习可以提高我们分析设计能力 和编程能力，为后续课程的学习及实践打下良好的基础。八、附录源程序(核心代码):#include #include using namespace std;/*“/*/ int h105105;/输入的高度值int dis_sk101101;/记录了每一个点作为起点的最长长度int dx=-1,1,0,0;/为了方便上下左右侧的滑行的最大距离而使用的数组int dy=0,0,-1,1;int r,c;/* 判 断 是 否 越 界*,bool in_bound(int i,int j)return i = 0 & i = 0 & j c; /*以查询方式写的动态规划实

12、现的从i,j下滑最大距离：“/*/int dis(int i,int j)int temp;if(dis_skij)return dis_skij;for(int k = 0; k h i+dxk j+dyk )temp = dis(i+dxk,j+dyk);/递归求 dis(i+dxk,j+dyk)，并保存在临时变量 temp中dis_skij = dis_skij temp ? dis_skij : temp + 1;/ 如果 dis_skij比 temp小，则取temp+1return dis_skij;/*main函数，取dis(i,j)的最大者就是所求的最长区域的长度：“/*,int

13、 main()int max dis = 0;int temp;int i,j;cin r c;for(i = 0; i r; i+)for(j = 0; j hij;dis_skij = 0;for(i = 0; i r; i+)for(j = 0; j temp ? max_dis : temp;cout max_dis + 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、分析出算法复杂度该算法只需计算一下产

14、品存放的空间，不满足则装在另外的箱子里，满足则 放入箱子，只需进行简单的比较即可，故所需的时间复杂度为O（n）。六、调试过程及实验结果程序的执行结果如下图所示：r -吒：算法设计与会析弟或我包装问虱exb0 0 4 0 8 127 5 10 0 010 0 0 0 0 0Press ankey to continue七、总结通过对本实验的学习，我解决问题的思路很重要，一个清晰的解题思路，可以 带来高效的解题效率；但是对于贪心算法，我还不太熟悉，在以后的学习中要对 该算法多加练习，直到掌握八、附录源程序(核心代码)：#includevoid main()int N,a,b,c,d,e,f,y,x

15、;/N用来存储需要的箱子数目，y用来存储2*2的空位数目，x用来存储1*1的空位数 目int u4=0,5,3,1;数组u表示3*3的产品数目分别是4的倍数,4的倍数+1,4的倍数+2,4的倍数+3时，为3*3的产品打开的新箱子中剩余的2*2的空位的个数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;/( c+3 ) / 4正好等于c除以4向上取整的结果，下同 y

16、=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);课程名称：算法设计与分析班级：软件121实验日期：2014-12-29姓名：熊齐超学号：1208060220指导教师：程欣宇实验序号：四实验成绩：一、实验名称回溯算法实验-频道分配问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对回溯算法的理解；

17、三、实验环境任意C或C+编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1129的题目-频道分配；2、阅读题目，分析出求解该问题的思路；3、使用回溯算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤回溯算法原理：回溯法是一个既带有系统性又带有跳跃性的搜索算法，用它可以系统地搜索 一个问题的所有解或任一解。它在问题的解空间树中，按深度优先的策略，从根 结点出发搜索解空间树。算法搜索全解空间树的任一结点时，先判断该结点是否 包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向 其祖先结点回溯。否则，进入该子

18、树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已经被搜索 遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。频道分配问题描述：当个无线站广播覆盖个非常大的区域时，需要使用转发器转发增强信 号。然而，每个转发器使用的频道数必须仔细的选择，以使得相邻的转发器之间 不会相互干扰。它们相互不干扰的条件是相邻的转发器使用不同的频道。因为无线频谱是非常稀有的资源，因此，所给的转发器网络使用的频道数量 必须最小化。你需要写一个程序读出转发器网络的描述，然后算出最小需要的频 道数量。注意：邻接关系具有对称性，如果A邻接B，则B邻接A。另外，因为转 发器网络

19、是平面的，所以通道不会交叉。输入输入由若干转发器网络的地图组成。每个地图的第一个行是转发器数量（1 至26，用0表示输入结束）。每个转发器由字母A至Z标识，每行列出和一个转发 器邻接的相邻转发器。输出对于每一个转发器网络地图，输出最少占用的频道数量（注意单复数）。例子输入2A:B:4A:BCB:ACDC:ABDD:BC4A:BCDB:ACDC:ABDD:ABC0例子输出1 channel needed.channels needed.channels needed.实验步骤：1、建立频道分配问题的解题思路首先构建回溯算法的基本框架，对每输入的若干转发器网络的地图（行数: lines），都对其所

20、有可能的路径进行比较，找出相邻路径不同的组合即可。回溯算法实现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&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+) s

21、etichj-A=1;result0 = 1;backtrack(1);3、分析出算法复杂度根据该算法的调度可知，每输入一个行数，遍历整个子树需要树的深度时间， 即O（N）时间，找到一个满足条件的值就跳出。六、调试过程及实验结果程序的执行结果如下图所示：七、总结通过对本实验的学习，我对回溯算法有了进一步的理解，在解决问题和分析问题 上的能力得到了一定的锻炼。不过，在本次实验过程中，也遇到一些困难，比如， 刚开始在算法逻辑上没有考虑周全，使得调试结果屡次出错，后通过同学的查找， 我发现了错误并给予解决。八、附录源程序(核心代码)：#include using namespace std; sta

22、tic bool D2727;static char C27;static int N;bool DFS(int num, int step)if (step = N) return true;for (int i = 1; i = num; +i) Cstep = i;bool valid = true;for (int j = 0; j N; +j)if (Dstepj = 1 & Cstep = Cj) valid = false;if (valid & DFS (num, step + 1) return true;Cstep = 0;return false; int main(in

23、t argc, char* argv)while(scanf(%dn, &N) & N != 0)char c;memset(D, 0, sizeof(D);for (int i = 0; i N; +i)scanf(%c:, &c);while (scanf(%c”, &c) & c != n)Dic-A = Dc-Ai = 1;memset(C, 0, sizeof(C);int num = 0;for (num = 1; num 4; +num)if (DFS(num , 0) break;if (num = 1) cout 1 channel needed.n”;else cout n

24、um channels needed.n;return 0;课程名称：算法设计与分析班级：软件121实验日期：2014-12-6姓名：熊齐超学号：1208060220指导教师：程欣宇实验序号：五实验成绩：一、实验名称分支限界法实验-抓住那头奶牛二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对分支限界算法的理解；三、实验环境任意C或C+编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为3278的题目-抓住那头奶牛；2、阅读题目，分析出求解该问题的思路；3、使用分支限界算法，实现本题；4、进行简单测试，完成之

25、后提交到POJ系统。五、算法描述及实验步骤分支界限算法原理：分支界限法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的 解空间树。问题的解空间树是表示问题解空间的 棵有序树。在搜索问题的解空 间树时，分支界限法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展 方式不同。在分支界限法中，每一个活结点只有一次机会扩展结点。活结点一旦 成为扩展结点，便一次性产生其所有儿子结点。在这些儿子结点中，舍弃掉不可 行解或导致非最优解的儿子结点，其余儿子结点被加入活结点表中。此后，从活 结点表中取下一结点成为当前扩展结点，并重复此结点扩展过程，直到找出所求 解或活结点表为空时为止。抓奶牛问题描述：

26、农夫约翰被告知逃跑的奶牛的位置，并且要求立即去抓住她。约翰开始的位 置在数轴上位置N(0 N 100,000)，而奶牛的位置在同样 个数轴上的K (0 K 100,000)。约翰有两种移动方式：步行和瞬间移动。*步行：从任意一点X移动到X+1或者X-1，花一分钟。*瞬间移动：从任意一点X移动到2X，花一分钟。如果奶牛没有意识到被抓捕，也就不会移动，最短时间是多少？农夫会抓到 奶牛？输入一行：用空格分开的两个整数：N和K输出一行：农夫抓到奶牛需要的最少分钟数。例子输入5 17例子输出4实验步骤：1、建立抓奶牛问题的解题思路解题思路：根据题意，示例有输入两个数据，第一个数据表示农夫所在位置，第二

27、个表示奶牛所在位置。再来分析奶牛吃草不动的情况：农夫到达奶牛每一步都有两种走法，花1分钟和2分钟。计算最短路径 即可。2、构造算法框架(1)农夫最快的抓捕路径是5-10-9-18-17,用时4分钟1、输入数据。scanf(d%d，&n,&m);(2)请给出算法框架！(流程图、纯文字语言、有注释的关键C代码均 可)for(i=0;it2) break;if (abt1-1=0)&(bt1-1=0)/分情况选择合适的路径(t2+;abt1-1 = 1;bt2=bt1-1;ct2=ct1 + 1; if (bt2 TOC o 1-5 h z =m)(pp=ct2; break; if (abt1+1=0)&(bt1 + 1=2*m)(t2+;abt1+1 = 1;bt2=bt1 + 1;c