矮人戴帽子问题~

M5256

题目源于网上，答案是我自己想出来的

第11题、BitTorrent质量保障自动化工程师：巨人到矮人村庄里和矮人玩个游戏：10名矮人从矮到高排列，每名矮人只可看见排在自己前方的所有人。巨人随机给每人戴上白色或黑色帽子，矮人看不见自己帽子。巨人从个子最高的开始问每人帽子颜色（黑或白）。如矮人回答错误，巨人就杀死矮人。每名矮人能听到之前答案，但矮人被杀时听不到。采用什么策略使被杀死的矮人最少？（矮人不能做除报黑或白之外的所有事）
注
好想一想~
答案
运气好死0个，运气不好死一个（死的那个是最高的）
将白帽子设为 0 将黑帽子设为 1
第一个被问的矮人看前9个矮人的帽子，并用白0黑1相加。若所得的是偶数，回答巨人：白；奇数则答：黑
（9若分为2个数相加，那么这2个数一定一个是奇数，另一个是偶数）
到了第二个被问的小矮人，听到后面的回答，知道了这剩下的9个矮人帽子颜色的奇偶后，在看前面矮人白色黑色帽子数分别的奇偶，就能推出自己头上的帽子颜色了
于是除了第一个被问的矮人（最高的那个）外是生死由天，剩下9个都能活下来
得出答案：1或0
PS：若是难以理解，可以拿一张纸自己试一试，随机写1或0，写10个，用这种方法，玩一玩。
PS2：其实这个是用2进制原理解答的，还有一中解法也能得出答案，但解释起来太麻烦
PS3：这个题目曾出现在哈弗的面试中，只是原题是100个矮人，戴帽子的是巫师
PSP：能在短时间打出来的，新世界的建设就靠你们了~（555第一次发帖好哈子噶系。。）
4

谢拉卡姗娜

{:gua12:} 矮人和巨人有点误导偏题的意思

破损の音乐盒

{:gua12:}有种进击的巨人的即视感

M5256

谢拉卡姗娜 发表于 2013-8-25 10:43
矮人和巨人有点误导偏题的意思

先前排沾沾大神的仙气，其实原题不是 巨人 而是 巫师，好吧吐槽题目什么的。。。

风萧萧兮易水寒

最高的那个悲剧报自己看到的最多的，然后下面的一样就可以了吧。

其实什么策略都一样，矮人只是砧板上的肉，就算报对了，巨人要杀它还不是一样容易。
{:gua12:}

曲宅子・龟

不是随机么= =？怎么报也不能获得信息啊……

曲宅子・龟

策略是事先商量好的- -不是所有矮人独立思考的么？
好吧，我福本的作品看多了……

【怨念】

要是做出来我就不会在这里上网了 = =

墨岩彧

最高的矮人，告诉所有矮人从头开始算起，奇数有多少顶黑帽和白帽。
最高的矮人，告诉所有矮人从头开始算起，偶数有多少顶黑帽和白帽。
最终，最高的矮人告诉所有矮人，一共多少顶黑帽和白帽。
…尽力为之{:4_119:}

墨岩彧

…能不能稍微解释一下M5256桑{:4_129:}

....

{:4_119:}最高的矮人站在最后……
然后由高到矮一个个往前排下去……
（逻辑题极差，如果错了的话估计会被嘲讽成翔吧……）

墨岩彧

.... 发表于 2013-8-25 13:11
最高的矮人站在最后……
然后由高到矮一个个往前排下去……
（逻辑题极差，如果错了的话估计会被 ...

握手，前途君好{:4_126:}

....

墨岩彧 发表于 2013-8-25 13:13
握手，前途君好

{:4_117:}果然我还是渣渣……
比起这种题，我还是更喜欢做几何……

墨岩彧

.... 发表于 2013-8-25 13:14
果然我还是渣渣……
比起这种题，我还是更喜欢做几何……

果然是我太笨了么…没有看明白答案是什么意思{:4_129:}

墨岩彧

无言以对真·早终的数学老师{:4_119:}