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

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

学生姓名 学号 专 业 学习中心 年级层次

北京语言大学网络教育学院

《算法与数据分析》结课作业

注意：

本学期所布置的结课作业，请同学一律按照以下要求执行：

1) 结课作业提交起止时间：2018年2月1日--3月19日。（届时平台自动关闭，逾期不予接收。）

2) 结课作业课程均需通过“离线作业”栏目提交电子版，学院不收取纸介的结课作业，以纸介回寄的作业一律视为无效；

3）截止日期前可多次提交，平台只保留最后一次提交的文档，阅卷时以最后一次提交的结课作业为准，截止日期过后将关闭平台，逾期不交或科目提交错误者，按0分处理； 4) 提交文档要求：提交的文档格式为doc、rar，大小10M以内；

5) 必须严格按照每门课程的答题要求完成作业，没有按照学院要求来做的结课作业，将酌情扣分。

一. 论述题(本大题共5小题,请任选其中两道题作答,每小题25分，总分50分)

1、试述分治法的基本思想。

答：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

2、设计动态规划算法有哪些主要步骤。

答：设计动态规划算法的主要步骤为： （1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。

3、分治法与动态规划法的异同？

答：分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

4、比较分支限界法与回溯法的异同？ 5、写出回溯法搜索子集树的算法。

二. 算法设计题(本大题5小题,请任选其中两道题作答,每小题25分，总分50分)

1、背包问题的贪心算法。

void Knapsack(int n,float M,float v[],float w[],float x[])

{//重量为w[1..n]],价值为v[1..n]的 n个物品，装入容量为M的背包

本文来源：https://www.bwwdw.com/article/aa5t.html