Let’s Play Games!

我要吃章鱼丸子

Let’s Play Games!Posted on 2011-03-09 13:43 苍梧 阅读(4529) 评论(6) 编辑 收藏
. ]) q  l* Z1 Y6 _

第1题

　　Alice和她的同学Bob通过网上聊天商量明天早晨谁去教室打扫卫生的事，Bob说：“我在桌上放了一枚硬币，你猜一下，是正面朝上还是反面朝上？如果猜对了，我去扫地。如果猜错了，嘿嘿…。”

      Alice显然不会同意，担心自己不论猜正面还是反面，Bob都说她错了。

分析：

看到这题，我的第一反应是葛优的“分歧终端机”。(╯▽╰)

最关键是要找到一种方法使得Alice给出她的猜测后Bob不能抵赖。一种参考答案如下：

3 z8 X! V; x8 \# e6 i& K

1.    Bob与Alice商量选取一个哈希函数hash()，hash()的值域应该尽可能大。

2.    Bob选择一个大随机数x，计算hash(x)；通过网络告诉Alice hash(x)的值

3.    Alice告诉Bob对x的奇偶性猜测（偶数表示“正面”；奇数代表“背面”）

4.    Bob告诉Alice x的值

5.    Alice验证hash(x)

- h3 W! T/ e, O1 B( F

但是这样也不是100%能够防止Bob作弊的。Bob如果想抵赖，那么他应该事先找出两个大整数，一奇一偶，而且哈希函数值相同。（抵赖的难度就取决于hash函数的选择了）

, Q! l& v) }7 F# O

3 t6 b+ a9 }' ]3 k2 T

第2题

       Alice与Bob相爱了，他们想通过书信来商量私奔的事。暗恋Alice的邮递员Chuck经常利用职权之便偷看他们之间的通信。Alice与Bob各有一把锁和只能打开自己那把锁的钥匙。另外Bob还有一个能够上锁的铁盒子。问如何防止Chunk偷看他们之间的通信？

分析：

       Bob将情书放进铁盒，用自己的锁给盒子上锁。Alice收到后给盒子加上自己的锁，然后将盒子寄回给Bob。Bob收到后将自己的锁取下，再将盒子寄给Alice。Alice收到盒子后取下自己的锁就可以看信了。

第3题

某人第一天由 A地去B地，第二天由 B地沿原路返回 A 地。问：在什么条件下，可以保证途中至少存在一地，此人在两天中的同一时间到达该地。

分析：

假如我们换一种想法，把第二天的返回改变成另一人在同一天由B去A，问题就化为在什么条件下，两人至少在途中相遇一次，这样结论就很容易得出了：只要其中一个人在另外一个人到达之前出发，则两人必会在途中相遇。

第4题

       一条长度为L的竹竿上分布着N个蚂蚁，已知所有蚂蚁的行进速度都是v，两只蚂蚁碰头后会掉头走，给定初始时刻蚂蚁的行进方向。问如何计算所有蚂蚁离开竹竿要多长时间？

分析：

       最直接也是最笨的方法就是对每个蚂蚁的行动进行模拟。这样谁都能想到的答案当然不是出题者想要的了。

       换个角度想，2个蚂蚁碰头后掉头走实质上是等价于它们碰头后擦肩而过继续赶路。（如果你将所有蚂蚁都看作一样的话）

       好了，这样一想，过程简单多了。对于每个蚂蚁，都假设竹竿上只有它一个蚂蚁，然后计算出它离开竹竿的时间。所需时间最长的蚂蚁所耗的时间就是题目的答案了。

第5题

一对情侣一起去买了一块饼

女生吃了3/7块饼

男生吃掉剩下的4/7块饼

男生比女生多出了4.5元

请问这块饼多少元?

分析：

　　4.5元（有回答31.5的么？举个手？）

参考资料：

[1]《编程之美》小组.《编程之美》

[2] matrix67. 密码学协议举例（五）：两个人能够在电话上打牌吗？

http://www.matrix67.com/blog/archives/1407

! [; l' P: S9 i8 F6 Y% H
2 ^: ?, c& u4 ?" v3 v4 K! j( N