装订线内 三、社会名流(20分)
在n个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。现在的问题是如果存在，试找出该社会名流。你可以使用的唯一方式是询问：“请问你知道那个人吗？”请给出提问次数为O(n)的算法，写出伪代码，分析算法的正确性，并给出算法运行时间的精确分析（即O(n)中隐藏的系数）。
（提示：当你问A是否认识B时，如果A认识B，则A不是社会名流；如果A不认识B，则B不是社会名流）
不要答题
四、地板覆盖（20分）
用2*1的地板块覆盖3*n的地面有多少种方案？如下图是一个覆盖的例子，函数fn可用于求解这个问题，请说明fn算法的正确性，并说明算法运行时间的上界和下界。
int fn(int n) { if (n % 2 == 1) return 0; int [] f = new int[n+1]; f[0] = 1; for (int i = 2; i <= n; i += 2) { 装 f[i] = f[i-2]*3; for (int j = i-4; j >= 0; j -= 2) 订 f[i] += f[j]*2; 线 } 内 return f[n]; }
不 要
答题
相关推荐：
loading