[计算机算法]微软面试题

coolsila

有100个强盗同一天入狱，入狱之前，典狱长对他们说“我会把你们关入100个分开的单人监狱，你们谁都不知道别人的情况，也不知道外界的任何情况，我每天会随即安排一个人出来放风，放风的那个人可以开关这个走廊里的这盏灯，如果哪一天你们那个人可以确定所有的人都出来放风过了，你们就可以被释放，如果说错了，你们都会被砍头。”问强盗在入狱的时候该如何商定出方案。

题目说的很清楚了：牢房里面看不到外界的任何情况，只有放风的那一个可以看到外界

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－


偶看了标准答案，发现该题真的有意思，希望广大算法爱好者积极参与答题～～～

coolsila

标准答案：

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

musicmadman

在下很愚，搜到个参考答案（传说中的微软面试题）：

（1）权限和状态设定：
1、ON开灯权限 （除1号外具有）
2、OFF关灯权限（仅1号具有）
3、COUNT 计数权限（仅1号具有）
（2）100个人事先约定第一天放出的人为Watcher（不妨假设为1号，为表述方便而编号），1号Watcher为计数者，不具有开灯（ON）权限，但具有关灯(OFF)权限，而且可以多次使用。其余99人事先赋予权限为开灯（ON），且该权限仅能使用一次，出来开过灯后权限消失，以后再出来将不再理会灯的开和关，回去了事。

（3）所以灯会在第二天亮起来，假设第二天放出的人为2号（若不继续放出和第一天同一个人（1号）的话。但不能假设第三天的人为3号，以下同），则2号开灯以后无论何时再被放出则不理会灯的状态。

（4）以后的一些天，除1号和不具有任何权限的2号外，其余人出来也不将关灯，因为他们本来就没有关灯权限。这样直到某天1号出来发现灯亮着，则1号COUNT＋1，并且将灯关掉。

（5）这样接下来的一天如果出来的是不再具有任何权限的2号，则灯保持关闭。并接下来出来的将迟早会是具有开灯权限的某个人，他开灯一次后同时失去权限。

（6）和第（4）类似，某天将继续由1号关灯并计数＋1。

……循环 （5）—>（6）—>（5）—>（6）……

当1号计数达99时，游戏结束，所有人都开过灯了，也就是Watcher确定所有人都出来放过风了，大家逃命去吧。

Microsoft Interview Questions

coolsila

既然楼上兄弟公布标准答案了，偶1楼也就不改了～～～

现在将题目改进一下，假如走廊上有2个开关分别控制的2盏灯，那算法又该如何？

wffw

看见这种题我的头就大！   

coolsila

下面是引用wffw于2005-12-25 17:36发表的:
看见这种题我的头就大！   

人生如算法，可以理解楼上的想法～～～