202003考试批次 《算法与数据分析》结课作业
学生姓名学号 专 业 满分作业
学习中心
年级层次
北京语言大学网络教育学院
《算法与数据分析》结课作业
注意：
本学期所布置的结课作业，请同学一律按照以下要求执行： 1) 结课作业提交起止时间：1月10日-------3月9日。（届时平台自动关闭，逾期不予接收。） 2) 结课作业课程均需通过“离线作业”栏目提交电子版，学院不收取纸介的结课作业，以纸介回寄的作业一律视为无效；
3）截止日期前可多次提交，平台只保留最后一次提交的文档，阅卷时以最后一次提交的结课作业为准，截止日期过后将关闭平台，逾期不交或科目提交错误者，按0分处理； 4) 提交文档要求：提交的文档格式为doc、rar，大小10M以内；
5) 必须严格按照每门课程的答题要求完成作业，没有按照学院要求来做的结课作业，将酌情扣分。
一. 论述题(本大题共5小题,请任选其中两道题作答,每小题25分，总分50分)
1、试述分治法的基本思想。
2、设计动态规划算法有哪些主要步骤。
答：( 1)找出最优解的性质，并刻划其结构特征。
( 2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息，构造最优解。
2、分治法与动态规划法的异同？
答： 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问
题，然后从这些子问题的解得到原问题的解。两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。
4、比较分支限界法与回溯法的异同？ 5、写出回溯法搜索子集树的算法。
二. 算法设计题(本大题5小题,请任选其中两道题作答,每小题25分，总分50分)
1、背包问题的贪心算法。
2、最大子段和: 动态规划算法。 答：
int MaxSum(int n, int a[]) {
int sum=0, b=0； //sum存储当前最大的b[j], b存储b[j] for (int j=1; j<=n; j++) { if (b>0) b+= a[j];
else b=a[i]; //一旦某个区段和为负，则从下一个位置累和 if(b>sum) sum=b; } return sum; }
3、贪心算法求活动安排问题。 4、排列问题。
5、回溯法解迷宫问题：迷宫用二维数组存储，用'H'表示墙,'O'表示通道。 答：
int x1,y1,success=0; //出口点 void MazePath(int x,int y)
{//递归求解:求迷宫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]='@'; //死胡同置为@ }
相关推荐：
loading