17级研究生算法考试

算法期末考

Posted by chochi on January 4, 2018

1简答题

  • 分值:10,题数:3

    1.1 走台阶。

  • n阶台阶,一共有两种走法,每次一步,或者两步。问共有几种走法。
    • 斐波那契数列。

      1.2 贪心与动态规划的异同点。

  • 动态规划和贪心算法都是一种递推算法均有局部最优解来推导全局最优解
  • 贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而之前的最优解则不作保留。贪心法正确的条件是:每一步的最优解一定包含上一步的最优解。

  • 动态规划算法,全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解.动态规划的关键是状态转移方程,即如何由以求出的局部最优解来推导全局最优解,需推倒边界条件。

1.3 分支限界法与回溯法的异同点。

  • 相同点:二者都是一种在问题的解空间树T上搜索问题解的算法。
  • 在一般情况下,分支限界法与回溯法的求解目标不同。 回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。
  • 回溯法与分支-限界法对解空间的搜索方式不同,回溯法通常采用尝试优先搜索,而分支限界法则通常采用广度优先搜索。
  • 对节点存储的常用数据结构以及节点存储特性也各不相同,除由搜索方式决定的不同的存储结构外,分支限界法通常需要存储一些额外的信息以利于进一步地展开搜索。

    2 算法题

    2.1 分支限界

  • N个任务分配给N给人,每个人完成每个任务的时间成本不同,求一种分支限界的分配算法,使得总成本最小。
    • PPT上的原题.. image image image image image

2.2 贪心

  • 工厂有一台A机器,和无限的B机器,有N个任务,每个任务要有从A机器的预处理时间 a 和 B机器的处理时间 b ,求一种分配方案,使得总处理时间最小,即最后一台从A机器开始工作到最后一台B机器处理完成的总时长最小。
    • 贪心,按任务的bi值降序排列。

      2.3 动态规划

  • 给你两个序列{Ai},{Bi},求这两个序列的递增子序列合并去重之后的元素最多。
  • 例如,在 {Ai} = { 2,6,1,3,5,7},递增子序列有{2,6,7},{1,3,5,7}等等…
  • {Bi} = {1,7,3,5,},递增子序列有{1,7},{1,3,5}等等。。
  • 最长的合并递增子序列为{1,2,3,5,6,7}

2.4 分治

  • 给你一个集合S,里面有N个不等的正数,求其中是否成立p+q=y。y为给定的数值。必须用分治。
    • 我的答案:排序 + 二分搜索。
    • 大佬的答案:排序,递归考虑序列映射到x轴上的左右区间,最再考虑左右两边,合并的话,左右两边分别维护两个指针,左边从小开始,右边从大开始,如果和大于x,右边指针往小移动,如果小于x,左边指针往大移动。

3 总结

两个小时时间不够,概念题就花了快一个小时,主要是自己写字慢。后面算法题字写到丑的飞起,每题基本都没有怎么想,大概看一眼第一个跳出来的想法就写进去了,主要是慌,觉得时间来不及了,怕写不完,结果全部写完了还剩五分钟,也不想改了。   老师是挺难过的,现场有看几个人的卷子,觉得大家都写的不好,确实比较难这次的卷子。像我这种不会dp的人,动态规划那题20分送他..