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

.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 算法程序流程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 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<=f1<f2fn<=31），每一个数字都用一个空格隔开。输出要求：对于每一个测试用例，第 1 行输出最后一位乘客到达目的楼层所需时间，第2 行输出停靠次数和相应的停靠方案，每一个数字用一个空格隔开。1.2 算法文字描述程序实现的算法思想，将待求解问题分解成若干个子问题，先求解子问题， 然后从这些子问题的解得到远问题的解。与分治法不同的是，适合用动态规划发求解的子问题往往不是相互独立。若用分治法求解这类问题，则分解的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常是多项式量级。在分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时在找出以求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以采用一个表来记录所有已解决的子问题的答案。不管子问题以后是否被使用，只要他被计算过，就将其结果填入表中。动态规划算法适合求解最优化问题，设计动态规划算法的具体步骤如下：1 找出最优解的性质，并刻画其结构；2 递归地定义最优值；3 以自底向上的方式计算最优值；4 根据计算最优值时得到的信息，构造最优解。.例如：给定金额 n 以及 1，2,5 分硬币，求找 n 的最少硬币数。对于大于 1 分的找零理所当然可以找零 1 分，大于 2 分和 5 分的找零与此类似，那么找零时就有三种选择，即找零后剩余金额为n-1，n-2，n-5，这三种选择总的找零数最少的方案即为所求解的方案。显然，最终的找零方案与执行当前选择后剩余的金额的找零相关，即金额n 的最优找零方案包含了金额 n-1，n-2， n-5 的最优找零方案，于是可得如下状态转移方程：具体的求解过程：F(1)F(2)F(3)F(4)F(5)F(6)F(n)11 minF(2)+1,F(1)+1=2minF(2)+1,F(3)+1=2 1minF(1)+1,F(4)+1,F(1)+1=2minF(n-1)+1,F(n-2)+1,F(n-5)+1初始化 F(1)=1,F(2),F(5)=1算法设计思路及求解过程思路：题目所描述的整个过程是“并行的”，而且所有人到达各自楼层的用时只与最晚到达的人有关。由于去各个楼层的具体数目对结果没有影响，所以可以将“电梯还剩 i 个人”表述成“电梯里面的乘客还要去 i 个楼层”。电梯从第1 层开始向上运行，任意时刻的状态都可以由“电梯当前所处楼层”和“电梯里面都有哪些乘客确定”，初始状态为“电梯在 1 楼”和“所有乘客都在电梯上”。在电梯运行的每一个阶段都需要作出相应的决策，哪些乘客乘坐电梯到目的层，哪些乘客选择爬楼梯到达目的地。决策后，电梯里面的乘客被分成两部分： 乘客留在电梯里面继续上升；乘客离开电梯走楼梯到达。求当前状态下电梯里面的乘客所有人到达目的所需要的最短时间，只需要找到一个最优决策，使得下电梯的乘客和留在电梯中的乘客最晚到达时间越短越好，这个最短时间就是当前状态下的最优解。如果假设决策后留在电梯里面的乘客到达各自楼层所需要的时间;.为 T1，离开电梯的各自到达目的地所需时间为 T2，则 minmax(T1,T2)就是当前状态的最优解，其中 T1 可以由“当前层数+1”和“决策后剩下的人”确定的状态得到；T2 则为下电梯走楼梯到达目的走楼梯最多的那一位乘客所花时间。如果去第 k 层的乘客选择在当前楼层下电梯，那么第 1，2k-1 层的乘客也应该选择在此时下电梯（如图 1 所示），这样就可以得到当前决策下的一个最优解。n第k 楼的乘客选择在此下电梯k k-1无论电梯当前位于何处3k 层以下的乘客此刻都应离开电梯21图 1 解题结论为了进一步处理停靠请求，对楼层按从高到低进行排序，并以此进行编号， 如此可以避免在求解过层中处理不连续的请求，如：4，5，10。使用i,j 两个参数表示电梯当前的状态，即电梯在第 i 层，电梯中有 j 位乘客。综上所述，可得如下状态转移方程：f(i,j)表示电梯在第 i 层楼时，电梯中 j 个人都到达目的地所需要的最短时间。具体求解过程：第一步：计算初始状态 f(topFloor,1),f(topFloor,2),f(topFloor,n); 第二步：根据状态转移方程计算 f(i,j);第三步：根据计算最优值时记录的信息求解最优解。.1.3 算法程序流程开始声明布尔变量flag，初始值为真输入n0=nYflag=falseNi=ni=i1i>=1NY将当前停靠请求保存到fi返回flag值函数执行结束图 2 Input 函数流程图;.主函数开始调用input函数主函数结束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+jj<=jY调用函数tStay(I,j,jj) 计算留在电梯中的乘客到达目的地所需时间t1调用tLeave(I,jj+1,j)计算离开电梯的乘客到达目的地所需时间t2tmp=max(t1,t2)jj=jj+1Ndpij>tmpdpij=tmpnextJij=jjY图 5calculate 函数流程图tLeave函数开始执行res=0l>rYtLeave函数执行结束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<iostream> # include<cstring># include<algorithm> #include<cmath># include<limits> #include<vector> using namespace std;const int maxN=30,maxF=31;/ 电梯上一层楼所需时间，电梯每次停靠时长，人走一层楼所需时间const int ve=4,st=10,vw=20;int n,fmaxN+1;/数据读取bool input()cin>>n;if(n=0) return false;/ 注意：f1.n中楼层数从高到低排列for(int i=n;i>=1;i-) cin>>fi;return true;int dpmaxF+1maxN+1,nextJmaxF+1maxN+1;/ 目前电梯在第currF 层, 第 L 层到第R 层乘客离开电梯/ 函数返回这些离开电梯的乘客中最晚到达目的层所需时间int tLeave(int currF,int l,int r)if(l>r) 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;/ 一般情况，电梯在第i 层停靠elsereturn dpi+1jj+ve+st;/void calculate()/ 边界：电梯在顶楼时所有人都必须下电梯int topFloor=f1;for(int j=1;j<=n;j+)/ 1,j 表示停靠请求的编号,编号越小表示编号停靠楼层越高dptopFloorj=tLeave(topFloor,1,j);for(int i=topFloor-1;i>=1;i-)/ i 表示电梯此刻所在位置for(int j=1;j<=n;j+) dpij=numeric_limits<int>:max(); for(int jj=0;jj<=j;jj+)/ 计算离开电梯的人和留在电梯里面的人中到达目的地最晚的int tmp=max(tStay(i,j,jj),tLeave(i,jj+1,j);/ 在此求解花费时间最短的乘客if(dpij>tmp) dpij=tmp;/ jj 以前的乘客均离开电梯nextJij=jj;cout<<dp1n<<endl;/ 重构最优解void rebuildSolution() vector<int> stops;int j=nextJ1n,topFloor=f1;for(int i=2;i<=topFloor;i+)if(nextJij!=j)stops.push_back(i); j=nextJij; if(j=0) break;cout<<stops.size();for(int i=0;i<stops.size();i+) cout<<" "<<stopsi;cout<<endl;void solve()memset(dp,0,sizeof(dp); memset(nextJ,0,sizeof(nextJ); calculate();rebuildSolution();2.1 题目描述题目 2 切割木材一个木匠从木材公司买了一批木材，每块木材的长度均相同，但由于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。同时每次切割时由于锯子本身有一定的宽度，因此每切割一次就会浪费掉一些木料。请设计一个程序使木匠能够用最少的木材切割出所需的木块。输入描述：输入有若干个测试样例，每个测试样例占一行。每行由若干个整数构成，第一个整数为所购买的木块的长度 L（0<L<=30000）,第二个整数为锯子的宽度 W（0<W<=1000）,其后的若干个整数分别表示制作家具时需要的木块的长度。输出描述：每个测试样例输出一行，为一个整数 N，表示制作家具时需要购买的木块的数量。样例输入：1000 100 250 250 500 650 10001000 50 200 250 250 500 650 970样例输出：342.2 算法文字描述此题目是装载问题的一个变种，与装载问题不同的是此问题没有给出“船” 数量，但是给出了船的载重量，因此仍旧可以借鉴解装载问题的思路，即让每一根原材料可以切出更多符合要求的木料，类似于装载问题中“将第一艘轮船尽可能地装满”，即保证切割以后剩余的原材料是最少的。算法具体描述如下：Step 1：声明求解结果变量 res=0，剩余未切割木料数量 count=n，当前已切割木料长度和 cw=0，目前最大切割长度bestW=0，求解标记数组visitedn， 当前最优求解数组 nVisitedn，问题求解状态记录数组 res_arrn，锯口宽度sw；Step 2：当剩余未切割木料数量count 大于 0 时，利用回溯法进行最大子集和 求 解。 当 i<n-1 时 ， 搜索左子树的条件： 当 前节点未被 访问且cw+datai<=w+sw，访问左子树时第 i 层相应节点时将相应访问标记visitedi置为 true，递归搜索该节点的左子树；递归搜索右子树时，将当前节点访问标记 visitedi置为 false；Step 3：当i>n-1 时，获得一种切割方案，若此次求解结果优于已得求解结果，即 bestW<cw，使用 nVisited 数组记录当前求解状态，同时更新 bestW 的值；Step 4：利用回溯法完成 1 次木料切割后，更当前问题求解状态res_arr 数组，根据最新的求解状态更新未切割木料数量 count，同时 res+，若 count=0 则求解结束，否则重复 2,3,4 直至 count=0。2.3 算法程序流程开始调用input函数读取测试用例读取数据成功与否？Y调用solve函数求解N输出结果res值结束图 8 main 函数流程图开始flag=true,n=0读取原材料长度w0=wYflag=falseN读取锯口宽度swNYtrue=flagNY返回flag值程序结束读取木材长度，并保存至数组data第n个位置ch='n'n=n+1读取下一个字符ch图 9input 函数流程图开始res=0,count=ncount>0N返回res值结束Yres=res+1cw=0,count=0,bestW=0,i=0调用backtrack(0,0)函数求解Ni<nYfalse=res_arriYNres_arri=nVisitedii=i+1false=res_arriNYcount=count+1图 10solve 函数流程图开始i>n1YbestW<cwNYfalse=res_arribestW=cwYi=0cw+datai+k*sw<=wYNi<ni=i+1Nvisitedi=true,cw+=datai,k=k+1Y递归调用backtrack(i+1,k)nVisitedi=visitediNcw=datai,k=k1visitedi=falseN递归调用backtrack(i+1,k)结束图 11backtrack 函数流程图2.4 算法的程序实现代码# include<stdio.h> # include<malloc.h> # include<cstring># define MAX_SAMPLE_LENGTH 50/*回溯法求解*/int* in=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int); int* data=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int);bool* visited=(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;/初始化数据保存数组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)scanf("%d",data+n); n+;char ch=getchar();if(ch='n') break;return flag;void backtrack(int i,int k)if(i>n-1)if(bestW<cw)/ 记录最优值bestW=cw;/ 记录当前最优解for(int i=0;i<n;i+) nVisitedi=visitedi;return ;/ 进入右子树条件if(!res_arri&&cw+datai+k*sw<=w)/ 记录当前已锯木头数量k+;/ 进入右子树实际操作cw+=datai;/ 访问标记visitedi=true; backtrack(i+1,k); cw-=datai;k-;visitedi=false; backtrack(i+1,k);int solve(int* data,int n)res=0; / 求解结果初始化int count=n; while(count>0)/ 初始化,cw 当前已锯木头长度和,/ count 剩余未锯木头数量,bestW 本次求解最大长度和cw=0,count=0,bestW=0; backtrack(0,0);for(int i=0;i<n;i+)/ 更新待解决问题状态if(!res_arri)res_arri=nVisitedi;/ 剩余未求解元素个数if(!res_arri)count+;/ 记录求解结果res+;return res;int main()while(input()solve(data,n); printf("n%dn",res);.;.3.1 题目描述题目 3 设计题给定一个数塔，如图 12 所示。在此数塔中，从顶部出发，在每一节点可以选择向左走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。3.2 输入要求图 12 数 塔第一行输入一个整数 n，n 表示数塔的层数，第2，n+1 行为数塔对应节点的数值。3.3 输出要求第一行输出路径数值和，第二行输出具体路径。3.4 样例输入51311 1240 7 166 14 15 812 7 13 24 113.5 样例输出91(1,1)->(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 层到第 5 层应该经过 13，则第 4+第 5 层的最大路径为 13+14=27这样实际上将 5 阶数塔变为 4 阶数塔问题了。2) 逐层向上递推，最后得到问题的最优解根据题意，待处理的数据规模同数塔的层数有关，同时数据节点的个数与层数相同，所以可以使用二维数组 data 存储待处理节点数值，只有一半的节点有数值，实际上是一个下三角矩阵。可以较为容易地得到问题状态转移方程：Step 1：声明变量数塔层数 n，待处理数据节点数值数组 datann,结果（状态）数组 dnn;Step 2：输入数塔层数 n，维数组 data 和 d 分配内存空间； Step 3：初始化第 n 层结果（状态）数组值；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函数求解i<nNYi=i+1j=0Nj<nj=j+1Yindex=i*n+j输入第i行第j列数值并保存至dataindex图 13 main 函数流程图;.开始index1=0,index2=0i=0i<nNi=n-2i=i+1Yi>=0Ndpindex1=dataindex1index1=(n-1)*n+i结束Yj=0j=j+1j<nNi=i-1dpindex2=temp_max+dataindex2Ytemp_max=max(dpindex1,dpindex1+1)index1=(i+1)*n+j,index2=i*n+j图 14tower_walk 函数流程图3.10 算法的程序实现代码#include<stdio.h> #include<cstring> #include<malloc.h> #include<math.h>using namespace std;int* data=NULL;/存储数塔原始数据int* dp=NULL;/状态值记录int n;/塔的层数/*动态规划实现数塔求解*/void tower_walk()int index1=0,index2=0;/ dp 初始化for (int i = 0; i < n; +i)index1=(n-1)*n+i; dpindex1 = dataindex1;int temp_max;for (int i = n - 2; i >= 0; -i)for (int j = 0; j <= i; +j)/ 使用递推公式计算dp 的值index1=(i+1)*n+j; index2=i*n+j;temp_max = (dpindex1>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; i < n; +i)index=(i-1)*n+j;node_value = dpindex - dataindex;/如果node_value = dpij则说明下一步应该是dataij;/如果node_value = dpij + 1则说明下一步应该是dataij + 1.index=i*n+j+1;if (node_value = dpindex) +j; printf("->(%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_walk();print_result();算法分析与设计课程总结通过本课程各个专题模块的学习，回顾和巩固了曾经学习过的知识，并且有了新的感受和收获。老师的教学具有很强的启发性，在整个学习过程中，通过具体的示例详细地讲解了穷举法、动态规划、贪心算法、回溯法和分支限界法等不同类型的算法，是我对学习算法充满了热情。学习算法对逻辑思维能力、推理能力和表达能力都有一定的要求，同时学习过程也有助于提高个人的逻辑思维能力，有助于培养分析问题和解决问题的习惯。最后感谢黄海于老师的悉心指导。参考文献1 王晓东. 算法设计与分析. 清华大学出版社. 2014.2 Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein. 算法导论. 机械工业出版社. 2011.