算法与分析实验报告模板

贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：一实验成绩：一、实验名称分治算法实验-棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。三、实验环境VisualC++四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。五、算法描述及实验步骤分治算法原理：分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。棋盘覆盖问题描述：在一个2kx2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果。七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。八、附录源程序（核心代码）清单或使用说明书，可另附纸贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：2014-11-25姓名：学号：指导教师：程欣宇实验序号：二实验成绩：一、实验名称动态规划实验-滑雪问题二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对动态规划算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、找到题号为1088的题目-滑雪,阅读题目，建立其最优解的递归表达式；3、使用备忘录式的动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子问题，就可能导致大量的重复计算。为了避免这些重复的计算，可以考虑的一个办法就是动态规划算法。为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含了子问题的最优解。滑雪问题描述：Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子12345161718196152425207142322218131211109一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为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、建立滑雪问题的解的递归表达式请建立！2、构造算法框架请构造！3、分析出算法复杂度请分析！六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果。七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。八、附录#includestdio.h#includememory.hintR,C;inta[101][101];//各点高度intf[101][101];//各点最大滑雪长度inlineintmax(inta,intb){//inline表示编译时直接嵌入至调用处，节省调用函数的时间returnab?a:b;}inlineintmax(inta,intb,intc,intd){returnmax(max(a,b),max(c,d));}intdfs(introw,intcol,inth){//递归深搜if(row1||rowR||col1||colR||h=a[row][col])//超出范围或上一点高度低于该点高度return0;//则返回0if(f[row][col]=0)//如果已经搜索过returnf[row][col];//则直接返回该点最大化学长度f[row][col]=max(dfs(row-1,col,a[row][col]),dfs(row,col+1,a[row][col]),dfs(row+1,col,a[row][col]),dfs(row,col-1,a[row][col]))+1;//动规，当前最大滑雪长度为四周比该点低的最大滑雪长度加1returnf[row][col];}intmain(){intT,i,j;scanf(%d,&T);while(T--){intmax=0;memset(f,-1,sizeof(f));scanf(%d%d,&R,&C);for(i=1;i=R;++i){for(j=1;j=R;++j){scanf(%d,&a[i][j]);}}for(i=1;i=R;++i){for(j=1;j=R;++j){intnum=dfs(i,j,0xffffff);//通过16进制0xffffff方便地给出一个足够大的int型if(maxnum)max=num;}}printf(%d\n,max);}return0;}贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：124班（12级）实验日期：2014-12-02姓名：何航学号：1208060365指导教师：程欣宇实验序号：三实验成绩：一、实验名称贪心算法实验-包装问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对贪心算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1017的题目-包装；2、阅读题目，分析出求解该问题的思路；3、使用贪心算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤贪心算法原理：贪心算法通过一系列的选择来达到子问题的解。它所做的每一步选择都是当前状态下局部最好选择，即贪心选择。这种启发式的策略虽不能总是奏效，但大多数情况下确能达到预期目的，得到最优解。要使用贪心算法，问题必须具备两个基本要素。贪心选择性质和最优子结构性质。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。通常采用自顶向下的方式进行，这样每做一次贪心选择就将所求问题化为规模更小的子问题。当然，前提是所求问题本身的最优解包含其子问题的最优解，即具有最优子结构性质。包装问题描述：有一个工厂生产一种长宽为1*1、2*2、3*3、4*4、5*5、6*6的产品，这些产品交付到客户手中都是用6*6的包裹包装。因为费用问题，工厂希望使用最少的包裹寄送给订购货物的客户。一个好的程序能够根据订单找到最少需要的包裹数量。你被要求写这样一个程序。输入输入文件由若干行组成，每一行市一个订单，所有的订单都由6个整数组成，分别对应1*1产品到6*6产品的需求量。输入文件的最后一行由6个0组成。输出输出文件的每一行对应输入文件的每一行，它包含了最少需要的包裹数量。输入示例004001//4个3*3的产品和1个6*6的产品751000//7个1*1的产品、5个2*2的产品和1个3*3的产品000000//0结束输出示例2//至少需要2个包裹1//至少需要1个包裹实验步骤：1、建立包装问题的解题思路装箱问题，利用贪心的思想，从最大的开始装6×6，5×5和4×4的每个都需要一个箱子5×5的和11个1×1的装一起，4×4的和5个2×2的装一起3×3的分4种情况1.正好装满2.剩一个，则装5个2×2的，7个1×1的3.剩两个，则装3个2×2，6个1×1的4.剩三个，则装1个2×2的，5个1×1的还要多余的2×2的，装完后用1×1的填充若2×2的不够，原来用2×2的用1×1的填充2、构造算法框架3、分析出算法复杂度六、调试过程及实验结果七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。八、附录#includeiostream#includecstdiousingnamespacestd;intmain(){intp[4]={0,5,3,1},a[10];//3×3的放完后，余下的放入新箱子后，还可以放几个2×2的包裹（下标对应余数）while(1){intsum=0;for(inti=1;i=6;i++){scanf(%d,&a[i]);sum+=a[i];}if(sum==0)break;sum=0;sum=a[4]+a[5]+a[6]+(a[3]+3)/4;//6*6,5*5,4*4每个都要用一个箱子（画图），3×3的对4向上取整intneed2=a[4]*5+p[a[3]%4];//需要的2×2的个数if(need2a[2])//上取整sum+=(a[2]-need2+8)/9;intneed1=sum*36-a[2]*4-a[3]*9-a[4]*16-a[5]*25-a[6]*36;//需要的1×1的个数，即所有箱子的总面积减去后5种盒子的总面积if(need1a[1])sum+=(a[1]-need1+35)/36;//上取整printf(%d\n,sum);}return0;}贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：四实验成绩：一、实验名称回溯算法实验-频道分配问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对回溯算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1129的题目-频道分配；2、阅读题目，分析出求解该问题的思路；3、使用回溯算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤回溯算法原理：回溯法是一个既带有系统性又带有跳跃性的搜索算法，用它可以系统地搜索一个问题的所有解或任一解。它在问题的解空间树中，按深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已经被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。频道分配问题描述：当一个无线站广播覆盖一个非常大的区域时，需要使用转发器转发增强信号。然而，每个转发器使用的频道数必须仔细的选择，以使得相邻的转发器之间不会相互干扰。它们相互不干扰的条件是相邻的转发器使用不同的频道。因为无线频谱是非常稀有的资源，因此，所给的转发器网络使用的频道数量必须最小化。你需要写一个程序读出转发器网络的描述，然后算出最小需要的频道数量。注意：邻接关系具有对称性，如果A邻接B，则B邻接A。另外，因为转发器网络是平面的，所以通道不会交叉。输入输入由若干转发器网络的地图组成。每个地图的第一个行是转发器数量（1至26，用0表示输入结束）。每个转发器由字母A至Z标识，每行列出和一个转发器邻接的相邻转发器。输出对于每一个转发器网络地图，输出最少占用的频道数量（注意单复数）。例子输入2A:B:4A:BCB:ACDC:ABDD:BC4A:BCDB:ACDC:ABDD:ABC0例子输出1channelneed