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