Chinaunix

标题: 突然想到的，算法强的进来看看 [打印本页]
作者: epegasus    时间: 2006-09-14 10:55
标题: 突然想到的，算法强的进来看看
以下3个智力题：
如何用计算机给出结果
1，海盗问题
5个海盗抢到了100块黄金，每一颗都一样的大小和价值连城。他们决定这么分：
　1、根据自己的厉害程度决定自己的编号,最厉害的为5号次为4号,以此类推

　　2、首先，由5号提出分配方案，然后大家5人进行表决，当且仅当超过或等于半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。

　　3、如果5号死后，再由4号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。

4、以次类推……

　　条件： 每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。

　　问题：第一个海盗提出怎样的分配方案才能够使自己的收益最大化？


2，囚犯问题
5个囚犯，分别按1-5号在装有100颗绿豆的麻袋抓绿豆，规定每人至少抓一颗，而抓得最多和最少的人将被处死，而且，他们之间不能交流，但在抓的时候，可以摸出剩下的豆子数。问他们中谁的存活几率最大？？
提示：
1，他们都是很聪明的人
2，他们的原则是先求保命，再去多杀人
3，100颗不必都分完
4，若有重复的情况，则也算最大或最小，一并处死

3，海盗问题2
10名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就 此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下提名最厉害的海盗又重复上述过程。
　　所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的，而且知道其他的海盗也是有理性的。此外，没有两名海盗是同等厉害的——这些海盗按照完全由 上到下的等级排好了座次，并且每个人都清楚自己和其他所有人的等级。这些金块不能再分，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。最凶的一名海盗应当提出什么样的分配方案才能使 他获得最多的金子呢？
作者: hellhell    时间: 2006-09-14 11:15
把500缩小到5,然后倒推
作者: epegasus    时间: 2006-09-14 11:41
我说的是计算机解法，顺便问一下，那女的是谁？
作者: uppet    时间: 2006-09-14 15:02
计算机的穷举可以解决一切问题，只要你受得了的话。。
不过，哪怕是真的要进行搜索，最好也先排排序，或者定定边界，这样效率才高。。

对于第三题(第一题类似)来说：
数据本身是有序的，就只谈边界吧。边界主要是两个——利益最大化和可以单向控制的票数（因为可以确定下家怎么投票）。可以得出这个表格

1
0

1    2
0 100

1    2    3
1    0   99

1    2    3    4
2    0    0   98

1    2    3    4    5
3    1    0    0   96

1    2    3    4    5    6
4    2    0    0    0    94

...........................................

对于第二题：
此时的数据也有两个边界，分别是(想想为什么吧^_^)
(1) 18 19 20 21 22
(2)   1   2   3   4   5
对于首个囚犯，他/她的主要任务是不去触碰边界，而且要最大化自己的生存机率
对于最后一个囚犯，比较闷，因为死定了，唯一的欣慰是在死前可以决定另一个
囚犯的生死~

理通边界和约束后，编程也没什么必要了，只是代数运算而已。。。
作者: net_robber    时间: 2006-09-14 15:16
说实话，花了半个小时，没看懂题目
作者: epegasus    时间: 2006-09-14 16:36
quote]原帖由 uppet 于 2006-9-14 15:02 发表
计算机的穷举可以解决一切问题，只要你受得了的话。。
不过，哪怕是真的要进行搜索，最好也先排排序，或者定定边界，这样效率才高。。

对于第三题(第一题类似)来说：
数据本身是有序的，就只谈边界吧。边界主 ... [/quote]

牛人啊~跑来第一贴，汗
对于囚犯我先用人脑想了一下（我自己的脑）：
每人必须拿一颗，但是后来的不够拿怎么办？所以把这条件去掉好了，规定不拿就是0颗；
囚犯1是必死的：他拿了后2囚决对不会去拿比他多的，为保命谁都不会去拿比前面的最大值还多的；所以囚1必死；
既然必死就要多害人，如果拿的数多余20少于100，那么2囚就可以活了；所以一定要拿少于20或者拿完；

囚1少于等于20，那么2囚不管拿多少都是死
所以他拿的数必定是使后面的人死的最多，建议和囚一拿一样的好了；接下了就不说了，5个人都是死。

[ 本帖最后由 epegasus 于 2006-9-14 16:39 编辑 ]
作者: assiss    时间: 2006-09-14 17:34
囚犯问题：
第三个不知道前两个各拿了多少，为保命，他拿（N1+N2）/2个。第四个拿（N1+N2+N3）/3，第五个拿（N1+N2+N3+N4）/4。

N1若<=20，则N5=N4=N3=N2=N1，5个人全死；
N1若>20，N1肯定死；N2会选20（若不足20,他会都拿，则N3、N4、N5全0），N3选20（若不足20，他会都拿）、N4同N2，N5肯定死。

N1必死，他若想害别人，则其它人跟他一起死。

所以，这个题目证明了自私的危害。
作者: assiss    时间: 2006-09-14 17:47
分金子问题：

  2. 以下三行分别是：
  3. 强盗代号（1-N）
  4. 所得金块（0~100）
  5. 所投票（0代表反对，1代表赞同）

  7. 1
  8. 100
  9. 1

  11. 1     2
  12. 100 0
  13. 1    0//2号永远都不会得到金块，他永远都会投反对票。如果让他当上1，他的利益才能最大化，但是这个愿望永远都不可能实现

  15. 1   2   3
  16. 99 0   1
  17. 1   0   1//3号不会反对，如果反对，2号成为1号，3号成为2号----他就什么都没有了（有一个金块总比什么都没有强）。

  19. 1   2   3   4
  20. 99 0   1   0
  21. 1   0   1   0//3号不会反对，若1号死，2号变1号，他会变2号----一无所有。4号肯定反对，但可惜他的反对意见此时不重要----任何时候他都不重要，可怜的四号。

  23. 1   2   3   4   5
  24. 98 0   1   0   1
  25. 1   0   1   0   1
  26. //3号不会反对，理由同上。但如果不给他，他同样一无所有，则很乐意看见一号死----所以1号必须给3号一点甜头。
  27. //4号与5号的争夺，看看给谁少能达到目的。
  28. //给4号必须2个，不然若只给一个或不给，他看1号死，他成为3号，他至少可以有1个金块
  29. //给5号只需要1个，他若反对，他会成为4号----一无所有的四号。
  30. //所以，5号入选。
复制代码


此题见证了黑社会里二头目与大头目的权力争夺，及与手下各人的拉拢、利益交易，是不可多得的人性教材。

[ 本帖最后由 assiss 于 2006-9-14 17:52 编辑 ]



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2