2020哈工大算法考试样例试题参考答案

Posted by

明天就参加算法考试了,详细写下过程练练步骤。(不全,以后可能会补)
答案参考了whk和rxz两位大佬的解法
附上rxz大佬的write up链接whk大佬的write up链接
发现自己是真的菜

大胆猜测一下明天考题的内容

1. 程序功能理解,分析复杂度(第一章第二章)
2. 关于复杂度函数的推导(第二章)
3. 分治、dp,贪心各一道,分别针对具体的问题设计算法,描述思想,写伪代码,分析复杂度(第三、四、五章)
4. 平摊分析(第六章)
5. 流算法,大概率是用Ford-fulkerson算法(第七章)
6. 随便来一道字符串相关的算法设计题,不限思路。(不知道直接暴力求解会不会扣分) (第9章)
7. 盲猜来道A*(第8章)
8. 差点忘了还会有道求解递归方程的题(第二章,大概率master定理可以直接求解)

考后说

讲真,当老师说今年题不会比去年简单,我是持怀疑态度的。但是考试试卷分分钟教我做人。第一题考的是循环不变量。还好,前一天临时看了看相关的内容不至于概念都不知道是啥,但是遗憾的是第一题原题在讲义上就有相关的内容,后悔看的时候直接略过了。后面有几道算法分析题,思路都不是很明确,迷迷糊糊的瞎写到第6题的时候时间还有半个小时(一共十道题,考试总时长两个小时,讲真遇到没明确让写伪代码的题还是不要画蛇添足了)。最后考了一道8数码问题,要写出搜索过程。乍一看这道题我以为老师会让我们搜索两三层就能得到答案。结果我还是低估了老师高估我们的程度(要不就是我太菜了)
总结一下,算法考试与其它的考试不同。准备算法考试的过程中,仔细看老师的讲义,弄懂老师上课讲的习题是最基本的事情。除非天赋异禀否则必须要提前一两个月复习。弄懂讲义后多见见题型,洛谷啥的都刷起来吧,不然不敢保证考试看见题能很快的有思路。还有就是别押题,老老实实复习比这有用。

1

解:
套了三层循环,最内层让x加1。列出合式的形式得到最终的x值。
\sum_{i=0}^{n}\sum_{j=1}^i\sum_{k=1}^{i+j}1=\sum_{i=0}^{n}\sum_{j=1}^i(i+j)=\sum_{i=0}^{n}i+\frac{i(i+1)}{2}=\frac{n(n+1)^2}{2}
所以算法的功能是计算\frac{n(n+1)^2}{2},共三层循环,故时间复杂度为O(n^3)

2


解:
由条件可知,
\exists c_1,c_2,c_3,c_4, N_1,N_2,\forall n>N_1,0<f(n)\le c_1g(n)
N=max(N_1,N_2)
同样的,有:
\forall n>N,0<f(n)\le c_1g(n),,\forall n>N,0<g(n)\le c_2h(n)
令:
c=c_1c_2\forall n>N,0<f(n)\le ch(n)
所以f(n)=O(h(n))

3

用master定理
log_22=1,n^1<n^4而且是多项式的小于,故复杂度为\theta (n^4)

4

刚开始我的想法是用类似快排的思路拆分A。具体过程是首先在A中选择一个基,把A中小于基的元素放到A的左边,大于基的元素放到A的右边。这个过程执行一遍后我们就可以知道基是A的第几个元素(假设是第m个)。这个过程是O(n)的。检查m是否在S中(O(k)的一个遍历)。在大于基的元素和小于基的元素两个序列中分别再执行上面的操作。最后应该是可以得到最终的答案。但是时间复杂度不符合要求。

参照两位大佬的思路,详细的写下步骤。
因为S是有序的,所以我们可以对S进行分治。选择S中间元素p_m,用线性第K小(大)算法可以找到A中第p_m小的元素a_{p_m},然后将A分成两个子序列A_1,A_2,序列中元素一个全部大于a_{p_m}另一个全部小于a_{p_m}。同样,S数组也被p_m分成了两部分S_1,S_2,在A_1,S_1和A_2,S_2分别作为两个子问题的参数进行分治求解。
伪代码如下:

def Function(A,S):
    p<-FindMid(S);
    a<-FindKMin(A,a);
    C<-A中比a小的元素;
    D<-A中比a大的元素;
    E<-S中比p小的元素;
    F<-S中比p大的元素,且所有元素数值减去p;
    G<-Function(C,E);
    H<-Function(D,F);
    return G∪{a}∪H;

时间复杂度分析:
T(n,k)=2T(n/2,k/2)+n,复杂度为O(nlogk)
线性第n小的算法可以使用课上讲的求中位数的算法,也可以参照快排的思想。

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注