贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：一实验成绩：一、实验名称分治算法实验- 棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。
三、实验环境Visual C++四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。
有余力的同学尝试消去递归求解。
五、算法描述及实验步骤分治算法原理：分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。
棋盘覆盖问题描述：在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。
实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录源程序（核心代码）清单或使用说明书，可另附纸贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：2014-11-25姓名：学号：指导教师：程欣宇实验序号：二实验成绩：一、实验名称动态规划实验- 滑雪问题二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对动态规划算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、找到题号为1088的题目-滑雪,阅读题目，建立其最优解的递归表达式；3、使用备忘录式的动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。
五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子问题，就可能导致大量的重复计算。
为了避免这些重复的计算，可以考虑的一个办法就是动态规划算法。
为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含了子问题的最优解。
滑雪问题描述：Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。
可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
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 <= 100)。
下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output输出最长区域的长度。
实验步骤：1、建立滑雪问题的解的递归表达式请建立！2、构造算法框架请构造！3、分析出算法复杂度请分析！六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录#include<stdio.h>#include<memory.h>int R, C;int a[101][101];//各点高度int f[101][101];//各点最大滑雪长度inline int max(int a, int b){ //inline表示编译时直接嵌入至调用处，节省调用函数的时间return a>b?a:b;}inline int max(int a, int b, int c, int d){return max(max(a, b), max(c, d));}int dfs(int row, int col, int h){ //递归深搜if(row < 1 || row > R || col < 1 || col > R || h <= a[row][col]) //超出范围或上一点高度低于该点高度return 0; //则返回0if(f[row][col] >= 0) //如果已经搜索过return f[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; //动规，当前最大滑雪长度为四周比该点低的最大滑雪长度加1return f[row][col]; }int main(){ int T, i, j;scanf("%d", &T);while(T--){ int max = 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){ int num = dfs(i, j, 0xffffff); //通过16进制0xffffff方便地给出一个足够大的int型if(max < num) max = num; }} printf("%d\n", max); }return 0; }贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：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组成。
输出输出文件的每一行对应输入文件的每一行，它包含了最少需要的包裹数量。
输入示例0 0 4 0 0 1 //4个3*3的产品和1个6*6的产品7 5 1 0 0 0 //7个1*1的产品、5个2*2的产品和1个3*3的产品0 0 0 0 0 0 //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、分析出算法复杂度六、调试过程及实验结果七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录#include<iostream>#include<cstdio>using namespace std;int main(){int p[4]={0,5,3,1},a[10]; //3×3的放完后，余下的放入新箱子后，还可以放几个2×2的包裹（下标对应余数）while(1){int sum=0;for(int i=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向上取整int need2=a[4]*5+p[a[3]%4]; //需要的2×2的个数if(need2<a[2]) //上取整sum+=(a[2]-need2+8)/9;int need1=sum*36-a[2]*4-a[3]*9-a[4]*16-a[5]*25-a[6]*36; //需要的1×1的个数，即所有箱子的总面积减去后5种盒子的总面积if(need1<a[1])sum+=(a[1]-need1+35)/36; //上取整printf("%d\n",sum);}return 0;}贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：四实验成绩：一、实验名称回溯算法实验- 频道分配问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对回溯算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1129的题目-频道分配；2、阅读题目，分析出求解该问题的思路；3、使用回溯算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。