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

1、考试批次算法与数据分析结课作业学生姓名 学习中心 学号 专 业 年级层次 北京语言大学网络教育学院算法与数据分析结课作业注意：本学期所布置的结课作业，请同学一律按照以下要求执行：1) 结课作业提交起止时间：2018年8月1日-9月10日。（届时平台自动关闭，逾期不予接收。）2) 结课作业课程均需通过“离线作业”栏目提交电子版，学院不收取纸介的结课作业，以纸介回寄的作业一律视为无效；3）截止日期前可多次提交，平台只保留最后一次提交的文档，阅卷时以最后一次提交的结课作业为准，截止日期过后将关闭平台，逾期不交或科目提交错误者，按0分处理；4) 提交文档要求：提交的文档格式为doc、rar，大小10M

2、以内；5) 必须严格按照每门课程的答题要求完成作业，没有按照学院要求来做的结课作业，将酌情扣分。一. 论述题(本大题共5小题,请任选其中两道题作答,每小题25分，总分50分)1、试述分治法的基本思想。2、设计动态规划算法有哪些主要步骤。答：( 1)找出最优解的性质，并刻划其结构特征。( 2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。3、分治法与动态规划法的异同？答：分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子

3、问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。4、比较分支限界法与回溯法的异同？5、写出回溯法搜索子集树的算法。二. 算法设计题(本大题5小题,请任选其中两道题作答,每小题25分，总分50分)1、 背包问题的贪心算法。2、 最大子段和: 动态规划算法。答：一般理论最大子段和问题复杂度为O(n)的解法，在上篇博客最大连续子序列中已经谈过了。这里在稍微提及一下，主要是更形式化的说明为什么是用动态规划。然后谈一下这个问题的分治解法。设所要求的序列为， 记： 也就是说：那么原问题转化为：而数组b是可以递归表达的，如下：或者表示为：这样就很明显的显示出了最优子结构性质

4、。具体算法就不给了，上篇博客已经给出了。3、 贪心算法求活动安排问题。答：1、建立数学模型描述问题。我在这里将时间理解成一条直线，上面有若干个点，可能是某些活动的起始时间点，或终止时间点。在具体一下，如果编程来实现的话，将时间抽象成链表数组，数组下标代表其实时间，该下标对应的链表代表在这个时间起始的活动都有哪些，具体参照程序注释。2、问题分解。为了安排更多的活动，那么每次选取占用时间最少的活动就好。那么从一开始就选取结束时间最早的，然后寻找在这个时间点上起始的活动，以此类推就可以找出贪心解。程序代码：#includestruct inode /自定义的结构体int end; /表示结束时间inode *next; /指向下一个节点的指针;int main()inode start10001,*pt;int a,b,i,num=0; /num负责计数，i控制循环，a，b输入时候使用for(i=0;iend=b;pt-next=starta.next;starta.next=pt;i=0;while(inext)if(pt-endend;i=temp; /将当前时间设置成前一子问题的终止时间num+;