201803考试批次《算法与数据分析》(结课作业)

201803考试批次《算法与数据分析》结课作业学生姓名学习中心学号考号专业年级层次北京语言大学网络教育学院《算法与数据分析》结课作业注意：本学期所布置的结课作业，请同学一律按照以下要求执行：一、学生必须预约才能在学生平台看见相关课程的“结课作业”按钮；二、提交路径：个人平台首页--学习中的课程，点击该课程名称--点击“结课作业”--点击“浏览”按钮，选择要上传的文档后点击“提交作业”即可。三、结课作业提交起止时间：2018年2月1日--3月12日。（届时平台自动关闭，逾期不予接收。）四、提交的文档格式必须为word文档，截止日期前可多次提交，平台只保留最后一次提交的文档；五、严格按照课程名称提交相应课程结课作业，提交错误的结课作业，按0分处理。一.论述题(本大题共5小题,请任选其中两道题作答,每小题25分，总分50分)1、试述分治法的基本思想。答：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解2、设计动态规划算法有哪些主要步骤。答：设计动态规划算法的主要步骤为：（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解3、分治法与动态规划法的异同？答：分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。4、比较分支限界法与回溯法的异同？答：相同点：二者都是一种在问题的解空间树T上搜索问题解的算法。不同点：1.在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。2.回溯法与分支-限界法对解空间的搜索方式不同，回溯法通常采用尝试优先搜索，而分支限界法则通常采用广度优先搜索。3.对节点存储的常用数据结构以及节点存储特性也各不相同，除由搜索方式决定的不同的存储结构外，分支限界法通常需要存储一些额外的信息以利于进一步地展开搜索5、写出回溯法搜索子集树的算法。二.算法设计题(本大题5小题,请任选其中两道题作答,每小题25分，总分50分)1、背包问题的贪心算法。答：voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){//重量为w[1..n]],价值为v[1..n]的n个物品，装入容量为M的背包//用贪心算法求最优解向量x[1..n]inti;Sort(n,v,w);for(i=1;i=n;i++)x[i]=0;floatc=M;for(i=1;i=n;i++){if(w[i]c)break;x[i]=1;c-=w[i];}if(i=n)x[i]=c/w[i];}2、最大子段和:动态规划算法。答：intMaxSum(intn,inta[]){intsum=0,b=0；//sum存储当前最大的b[j],b存储b[j]for(intj=1;j=n;j++){if(b0)b+=a[j];elseb=a[i];//一旦某个区段和为负，则从下一个位置累和if(bsum)sum=b;}returnsum;}3、贪心算法求活动安排问题。答：templateclassTypevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i=n;i++)if(s[i]=f[j]){A[i]=true;j=i;}elseA[i]=false;}4、排列问题。答：templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}5、回溯法解迷宫问题：迷宫用二维数组存储，用'H'表示墙,'O'表示通道。答：intx1,y1,success=0;//出口点voidMazePath(intx,inty){//递归求解:求迷宫maze从入口(x,y)到出口(x1,y1)的一条路径maze[x][y]='*';//路径置为*if((x==x1)&&(y==y1))success=1;//到出口则成功else{if(maze[x][y+1]=='O')MazePath(x,++y);//东邻方格是通路,向东尝试if((!success)&&(maze[x+1][y]=='O'))MazePath(++x,y);//不成功且南邻方格是通路,向南尝试if((!success)&&(maze[x][y-1]=='O'))MazePath(x,--y);//不成功且西邻方格是通路,向西尝试if((!success)&&(maze[x-1][y]=='O'))MazePath(--x,y);//不成功且北邻方格是通路,向北尝试}if(!success)maze[x][y]='@';//死胡同置为@}