1 某机器需要处理n个请求，每个请求都有其运行所需的存储空间(R[i])及运行之后输出所占用的存储空间(O[i])，且O[i]小于r[i]。假设CPU只能同时处理一个请求。现在该机器共有m个存储空间，请设计一个算法来安排这n个请求的处理顺序，使得所有请求都能被处理。并简要说明该算法的正确性。如果无论如何安排也不能处理完这些请求，算法也应能给出判断。SOL: 贪心法， 按照R[i]-O[i]降序排列请求
2 在一个空间里有m（m为偶数）只老虎，n只兔子，还有一个你，总共m+n+1只东西（什么，你说你不是东西？）每次随机地抽出两只东西发生互动（通常造成可怕的结果），幸存者再放回去。具体规则如下：
1）老虎和老虎->两相残杀
2）老虎和兔子->老虎吃掉兔子
3）兔子和兔子->没事
4）老虎和你->你成为老虎的美餐
5）你和兔子->你可以选择放回去或煮了兔子
问题是：最后你虎口余生(即，出现山中无老虎，猴子称大王的局面）的概率是多少（你需要在兔子问题上作出最优决策使此概率最大）
SOL: 1/(m+1) 本题最大的trick在于认识到兔子的存在其实根本不影响最后结果，可以直接忽略所有的兔子。剩下m只老虎和一个你。所求概率相当于你排在最后一位的概率。
3 16个人背后各贴一个数字，每个数字都可能取1到16的任意整数值（即可以重复，可以有数字不出现），每个人可以看到其他人的数字，但看不到自己的，贴好数字之后不可以进行任何形式的交流（诸如使用排队次序传达信息之类的伎俩无效），每人猜一个数字，问事先如何安排可以保证至少有一人猜中自己的数字。
SOL: 16个人每个人分别猜自己背后的数字,也就是16个人分别猜16个1-16的数字,显然无法保证一定一人猜中。但是如果16个人集中猜同一个1-16的数字X则能保证一定有一个人猜中, 方法是每一个人分别猜一个数，遍历解空间。这里我们这样人为制造出X:X = X1 xor X2 xor X3... xor X16 (X_i是第i个人背后数字).所以这个X对于所有人是一样的.于是可以第i个人可以猜测一个数Yi,这个数Yi满足和其他所有能看见的人背后的数字的xor之和为i.
No comments:
Post a Comment