算法分析与设计-课程设计报告.docx

《算法分析与设计-课程设计报告.docx》由会员分享，可在线阅读，更多相关《算法分析与设计-课程设计报告.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.XXXX 大学算法设计与分析课程设计报告院 （系）：年级：姓名：专 业： 计算机科学与技术研究方向： 互联网与网络技术指导教师：X X X X 大 学;.目录题目 1 电梯调度11.1 题目描述11.2 算法文字描述11.3 算法程序流程41.4 算法的程序实现代码8题目 2 切割木材102.1 题目描述102.2 算法文字描述102.3 算法程序流程112.4 算法的程序实现代码15题目 3 设计题173.1 题目描述173.2 输入要求173.3 输出要求173.4 样例输入173.5 样例输出173.6 测试样例输入183.7 测试样例输出183.8 算法实现的文字描述183.9 算法

2、程序流程193.10 算法的程序实现代码20算法分析与设计课程总结23参考文献241.1 题目描述题目 1 电梯调度一栋高达 31 层的写字楼只有一部电梯，其中电梯每走一层需花费 4 秒，并且在每一层楼停靠的时间为 10 秒，乘客上下一楼需要 20 秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去 4 楼、5 楼和 10 楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为 3*4=12 秒、4*4+10=26 秒、4*9+2*10=56 秒，则最后一位乘客到达办公室的时间为 56 秒，相应的停靠计划为 4

3、 5 10 均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第 4 楼的乘客所需时间为3*4=12 秒，到第 5 楼的乘客所需时间为 3*4+20=32 秒，到第 10 楼的乘客所需时间为 9*4+10=46 秒，即最后到达目的楼层的顾客所需时间为 46 秒。输入要求：输入的第 1 行为整数 n f1 f2 fn，其中 n 表示有 n 层楼需要停靠，n=0 表示没有更多的测试用例，程序终止运行。 f1 f2 fn 表示需要停靠的楼层（n=30，2=f1f2fn=1NY将当前停靠请求保存到fi返回flag值函数执行结束图 2 Input 函数流程图;.主函数开始调用input函数主函数结

4、束NInput函数返回结果为真？Y调用solve函数求解图 4main 函数流程图solve 函数开始执行初始化 dp 数组元素值为 0和nextJ 数组元素为 0调用 calculate 函数调用 rebuildSolution函数solve 函数结束图 3solve 函数流程图i=topFloor1calculate函数开始执行输出dp1nNi=1YtopFloor=f1Ncalculate函数执行结束j=1j=1i=i1Nj=nYj=n将dpij置为整型数最大值j=j+1Yjj=0调用tLeave(topFloor,1,j) 函数并将计算结果保存至dptopFloorjNj+jjtmpd

5、pij=tmpnextJij=jjY图 5calculate 函数流程图tLeave函数开始执行res=0lrYtLeave函数执行结束Nres=max(abs(currF-fl),abs(currF-fr) * vw图 7tLeave 函数流程图返回res值函数执行结束tStay函数开始执行res=0res=dpi+1jj+veYj=jjNY1=iNres=0Y0=jjNres=dpI+1jj+ve+st图 6tStay 函数流程图1.4 算法的程序实现代码# include # include# include #include# include #include using namesp

6、ace std;const int maxN=30,maxF=31;/ 电梯上一层楼所需时间，电梯每次停靠时长，人走一层楼所需时间const int ve=4,st=10,vw=20;int n,fmaxN+1;/数据读取bool input()cinn;if(n=0) return false;/ 注意：f1.n中楼层数从高到低排列for(int i=n;i=1;i-) cinfi;return true;int dpmaxF+1maxN+1,nextJmaxF+1maxN+1;/ 目前电梯在第currF 层, 第 L 层到第R 层乘客离开电梯/ 函数返回这些离开电梯的乘客中最晚到达目的层所

7、需时间int tLeave(int currF,int l,int r)if(lr) return 0;/ 仅需考虑两端, 无论此刻电梯在何处, 第 l-r 层花时间最多的/ 一定是离电梯当前所在楼层最远的乘客return max(abs(currF-fl),abs(currF-fr)*vw;/ 现在电梯在第i 层, 电梯里面本来有j 位乘客, 离开电梯的乘客剩下jj 位int tStay(int i,int j,int jj)/ 没有乘客离开,电梯不停if(j=jj | i=1)return dpi+1jj +ve;/ 所有人都离开电梯else if(jj=0)return 0;/ 一般情况

8、，电梯在第i 层停靠elsereturn dpi+1jj+ve+st;/void calculate()/ 边界：电梯在顶楼时所有人都必须下电梯int topFloor=f1;for(int j=1;j=1;i-)/ i 表示电梯此刻所在位置for(int j=1;j=n;j+) dpij=numeric_limits:max(); for(int jj=0;jjtmp) dpij=tmp;/ jj 以前的乘客均离开电梯nextJij=jj;coutdp1nendl;/ 重构最优解void rebuildSolution() vector stops;int j=nextJ1n,topFloo

9、r=f1;for(int i=2;i=topFloor;i+)if(nextJij!=j)stops.push_back(i); j=nextJij; if(j=0) break;coutstops.size();for(int i=0;istops.size();i+) cout stopsi;coutendl;void solve()memset(dp,0,sizeof(dp); memset(nextJ,0,sizeof(nextJ); calculate();rebuildSolution();2.1 题目描述题目 2 切割木材一个木匠从木材公司买了一批木材，每块木材的长度均相同，但由

10、于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。同时每次切割时由于锯子本身有一定的宽度，因此每切割一次就会浪费掉一些木料。请设计一个程序使木匠能够用最少的木材切割出所需的木块。输入描述：输入有若干个测试样例，每个测试样例占一行。每行由若干个整数构成，第一个整数为所购买的木块的长度 L（0L=30000）,第二个整数为锯子的宽度 W（0W=1000）,其后的若干个整数分别表示制作家具时需要的木块的长度。输出描述：每个测试样例输出一行，为一个整数 N，表示制作家具时需要购买的木块的数量。样例输入：1000 100 250 250 500 650 10001000 50

11、200 250 250 500 650 970样例输出：342.2 算法文字描述此题目是装载问题的一个变种，与装载问题不同的是此问题没有给出“船” 数量，但是给出了船的载重量，因此仍旧可以借鉴解装载问题的思路，即让每一根原材料可以切出更多符合要求的木料，类似于装载问题中“将第一艘轮船尽可能地装满”，即保证切割以后剩余的原材料是最少的。算法具体描述如下：Step 1：声明求解结果变量 res=0，剩余未切割木料数量 count=n，当前已切割木料长度和 cw=0，目前最大切割长度bestW=0，求解标记数组visitedn， 当前最优求解数组 nVisitedn，问题求解状态记录数组 res_a

12、rrn，锯口宽度sw；Step 2：当剩余未切割木料数量count 大于 0 时，利用回溯法进行最大子集和 求 解。 当 in-1 时 ， 搜索左子树的条件： 当 前节点未被 访问且cw+datain-1 时，获得一种切割方案，若此次求解结果优于已得求解结果，即 bestW0N返回res值结束Yres=res+1cw=0,count=0,bestW=0,i=0调用backtrack(0,0)函数求解Nin1YbestWcwNYfalse=res_arribestW=cwYi=0cw+datai+k*sw=wYNini=i+1Nvisitedi=true,cw+=datai,k=k+1Y递归调用

13、backtrack(i+1,k)nVisitedi=visitediNcw=datai,k=k1visitedi=falseN递归调用backtrack(i+1,k)结束图 11backtrack 函数流程图2.4 算法的程序实现代码# include # include # include# define MAX_SAMPLE_LENGTH 50/*回溯法求解*/int* in=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int); int* data=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int);bool* vis

14、ited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool); bool* nVisited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool); bool* res_arr=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool); int w;/ 原材料长度int n;/ 数据元素个数int sw;/ 锯口宽度int cw;/ 当前已锯木头长度和int res;/ 求解结果int bestW; / 当前求解最大值bool input()bool flag=true;/初始化数据

15、保存数组memset(in,0,MAX_SAMPLE_LENGTH*sizeof(int); memset(visited,false,MAX_SAMPLE_LENGTH*sizeof(bool); memset(res_arr,false,MAX_SAMPLE_LENGTH*sizeof(bool); memset(nVisited,false,MAX_SAMPLE_LENGTH*sizeof(bool);/ 记录输入数据个数n=0;/ 读取数据-原材料(木头)长度scanf(%d,&w);if(0=w) flag=false;/ 锯口宽度scanf(%d,&sw); while(flag)

16、scanf(%d,data+n); n+;char ch=getchar();if(ch=n) break;return flag;void backtrack(int i,int k)if(in-1)if(bestWcw)/ 记录最优值bestW=cw;/ 记录当前最优解for(int i=0;in;i+) nVisitedi=visitedi;return ;/ 进入右子树条件if(!res_arri&cw+datai+k*sw0)/ 初始化,cw 当前已锯木头长度和,/ count 剩余未锯木头数量,bestW 本次求解最大长度和cw=0,count=0,bestW=0; backtra

17、ck(0,0);for(int i=0;i(2,1)-(3,1)-(4,2)-(5,3)3.6 测试样例输入7119 812 10 74 15 23 1917 8 21 12 1632 25 24 28 31 278 5 9 10 11 13 153.7 测试样例输出113(1,1)-(2,1)-(3,2)-(4,3)-(5,3)-(6,4)-(7,5)3.8 算法实现的文字描述动态规划采用自底向上逐层分阶段决策1) 第 1 次决策，针对第 4 层如果最优路径经过 6，则从第 4 层到第 5 层应该经过 12，则第 4+第 5 层的最大路径为 6+12=18如果最优路径经过 14，则从第 4

18、层到第 5 层应该经过 13，则第 4+第 5 层的最大路径为 13+14=27这样实际上将 5 阶数塔变为 4 阶数塔问题了。2) 逐层向上递推，最后得到问题的最优解根据题意，待处理的数据规模同数塔的层数有关，同时数据节点的个数与层数相同，所以可以使用二维数组 data 存储待处理节点数值，只有一半的节点有数值，实际上是一个下三角矩阵。可以较为容易地得到问题状态转移方程：Step 1：声明变量数塔层数 n，待处理数据节点数值数组 datann,结果（状态）数组 dnn;Step 2：输入数塔层数 n，维数组 data 和 d 分配内存空间； Step 3：初始化第 n 层结果（状态）数组值；

19、Step 4：根据状态转移方程求解 d(i,j)，其中 i 从 n-1 到 1，j 从 1 到 i； Step 5：输出 d(1,1)；Step 6：根据数组 d 求解具体路径并输出。.3.9 算法程序流程开始结束输入n为数组data分配内存空间并将所有元素置为0调用print_result函数打印求解结果为数组dp分配内存空间并将所有元素置为0index=0,i=0调用tower_walk函数求解inNYi=i+1j=0Njnj=j+1Yindex=i*n+j输入第i行第j列数值并保存至dataindex图 13 main 函数流程图;.开始index1=0,index2=0i=0i=0Nd

20、pindex1=dataindex1index1=(n-1)*n+i结束Yj=0j=j+1jnNi=i-1dpindex2=temp_max+dataindex2Ytemp_max=max(dpindex1,dpindex1+1)index1=(i+1)*n+j,index2=i*n+j图 14tower_walk 函数流程图3.10 算法的程序实现代码#include #include #include #includeusing namespace std;int* data=NULL;/存储数塔原始数据int* dp=NULL;/状态值记录int n;/塔的层数/*动态规划实现数塔求解*

21、/void tower_walk()int index1=0,index2=0;/ dp 初始化for (int i = 0; i = 0; -i)for (int j = 0; j dpindex1 + 1)?dpindex1:dpindex1+1; dpindex2 = temp_max + dataindex2;/*打印最终结果*/void print_result()int index=0; printf(%dn,dpindex ); int node_value;/ 首先输出塔顶元素int j = 0,i=0; printf(%d,%d),i+1,j+1); for (i = 1;

22、i (%d,%d),i+1,j+1);printf(n);int main()scanf(%d,&n); data=(int*)malloc(n*n*sizeof(int); memset(data,0,n*n*sizeof(int); dp=(int*)malloc(n*n*sizeof(int); memset(dp,0,n*n*sizeof(int);int index=0;for (int i = 0; i n; +i)for (int j = 0; j = i; +j)index=i*n+j; scanf(%d,data+index); char ch=getchar();tower

23、_walk();print_result();算法分析与设计课程总结通过本课程各个专题模块的学习，回顾和巩固了曾经学习过的知识，并且有了新的感受和收获。老师的教学具有很强的启发性，在整个学习过程中，通过具体的示例详细地讲解了穷举法、动态规划、贪心算法、回溯法和分支限界法等不同类型的算法，是我对学习算法充满了热情。学习算法对逻辑思维能力、推理能力和表达能力都有一定的要求，同时学习过程也有助于提高个人的逻辑思维能力，有助于培养分析问题和解决问题的习惯。最后感谢黄海于老师的悉心指导。参考文献1 王晓东. 算法设计与分析. 清华大学出版社. 2014.2 Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein. 算法导论. 机械工业出版社. 2011.