最近 作者: 主题: 内容:
 进入版区才能发表文章 
 您当前的位置: 推理之门 > 谜题解析 > 谜题大全   【版主】:tl,艾米,popodian 字体大小:
1页/共1页(总计6个回复)
主 题: 传说中的三大难题及其解法~~(人气:748)
 tl小律师打开tl的博客
1 楼: 传说中的三大难题及其解法~~ 07年05月21日22点18分


第一题:海盗分金币问题,不过是108个人分100个金币。
解法:
使用大家最熟悉的倒推法。
为了叙述方便,不妨将倒数第一号海盗到第一号海盗编号分别1到108。

若2到108都死掉了……
__则1独吞所有100g(用g代表金币)。
若3到108都死掉了……
__则2为活命,只好将100g给1,自己0g。
若4到108都死掉了……
__则3为了获得最大利益,应该给2一金币。因为如果不给2金币,则2无论同不同意得到的利益是相同的,所以只要给2一金币,2就一定会同意3的提案,3得到99g。
若5到108都死掉了……
__除非4把100g给3,否则无法得到3的支持,所以就不给3了,(阴险~~~~)那么4为了夺得1和2的支持,只要分别给他们比3的提案多的金币就可以了,即1得到1g,2得到2g,这样4得到97g。
若6到108都死掉了……
__4得到0g,3得到1g,1得到2g,2得到0g。
……

多推几组(这里推了10组),得到一个二维数组(第i行表示有i个人的分金情况,用"_"代替空格):
_100
_100___0
___0___1__99
___1___2___0__97
___2___0___1___0__97
___0___1___2___1___0__96
___1___2___0___0___1___0__96
___2___0___1___1___0___1___0__95
___0___1___2___0___1___0___1___0__95
___1___2___0___1___0___1___0___1___0__94

明显可以发现,n(0<n<=108)如果想得到最大利益,首先应该得到n-1的方案中得不到金币的人的支持,因为只要给他们每人1g就可以了。
而根据上面的二维数组可以发现,每个人为了得到最大利益,总是将金币分给尽可能少的人(也就是刚刚能够超过半数的人数)。
所以n-1的方案中剩下得不到金币的人就应该有:下取整((n-2)/2)(n>1)。
那么在n的方案中,加上自己的一票和那接近半数的人,只要再多得到一个人的支持,就可以使自己的方案得到实施。
那么当然是找花钱最少的咯~~~~就任选一个n-1方案中给1g的人,给他2g就行了。
所以总共n可以得到的金币数f(n)=100-下取整((n-2)/2)-2;

算法明确之后,因为n=108,所以
f(108)=100-下取整((108-2)/2)-2=45枚金币。


  点击复制本贴地址:






推门,其实一直都在

※来源: 【 推理之门 Tuili.Com 】.

 tl小律师打开tl的博客
2 楼: Re:传说中的三大难题及其解法~~ 07年05月21日22点19分


第二题:12个乒乓球外形完全相同,有一个重量异常,用无砝码的天平三次称出这个球。
解法:
这道题其实并不难,大家只是忽略了一些隐含条件而已~~~~
为了方便叙述,将12个球分别编号1到12;
并将12个球分成三组:A1(1,2,3,4),A2(5,6,7,8),A3(9,10,11,12);

先将A1,A2分别放在天平两个托盘上称:
(1) 平衡,则1到8号球都是正常的球。
第二次这样称:(9,10),(7,8):
1)平衡,9和10是正常的球,7和8中有一个异常的球;
2)不平衡,9和10中有一个异常的球;
第三次只要将两个异常的球(u,v)中u拿出来和1称,若不平衡,则u是异常的球;否则就是v是不正常的球。

(2) 不平衡(不妨设A1>A2),则9到12号都是正常的球。
重新分一下组:B1(1,2,5),B2(3,4,9),B3(6,7,8),B4(10,11,12);
第二次这样称:B1,B2:
1)平衡,1到5是正常的球,6,7,8中有一个球比正常的球要重(因为6,7,8是从较重的A2中拿出来的,而A1中都是正常的球);
第三次只要从6,7,8中拿出6和7称,平衡则8是异常的球,不平衡则较重的是异常的球。

2)不平衡,则6,7,8是正常的球。
若B1>B2,则(1,2)中有一个比正常球轻的球(因为1,2是在较轻的A1中),其他球正常。
那么第三次就只要将1和2称一下就可以了。
若B1<B2,则(3,4)中有一个比正常球轻的球或是5比正常球重,其他球正常。
那么第三次就只要将3和4称一下,如果平衡,则5是异常球;否则就是3,4中较轻的球不正常。

这样就将所有情况讨论完了。








推门,其实一直都在

※来源: 【 推理之门 Tuili.Com 】.

 tl小律师打开tl的博客
3 楼: Re:传说中的三大难题及其解法~~ 07年05月21日22点20分


第三题:荒岛提问:某岛上有三种人:只说真话的,只说假话的,真假随机的.现各有一人在你面前,问他们三个可用"是否"回答的问题,每题只能问其中一人,三题后判断出三人各是哪种人.
解法:
这道题我确实没有自己想出来,我和另外一个同学讨论一中午加走神两节课想出来的~~~~(不过这两节都是语文,老师看见我写的满草稿纸极具“哲理”的问句,赞赏地点了点头,我还极其嚣张地问了关于双重否定的问题……)

首先嘛,还是先编号……三个人是1,2,3。
在提问之前,先给大家补一点语文知识(上课问的):
双重肯定句是表示肯定,双重否定句也是表示肯定。

我们先来看这样一道简化的问题:
[引]传说人死了之后,在黄泉路上会遇到一个三叉路口,一条路通往天堂,一条路通往地狱。这里有一个菩萨在看守,这个菩萨只会说“是”和“否”,但他有时候说真话,有时候说假话,而你肯定是不知道他到底说真说假。那么你如何在只问一个问题(一定有答案的问题)的条件下,问出哪一条路是前往天堂的呢?
解决这个问题,要做到无论菩萨是否说真话,都要回答相同的答案。那么结合我刚才介绍的语文知识,如果菩萨说真话,就让他双重肯定;如果菩萨说假话,就让他双重否定。
根据这个条件,可以得到一个问句:“当我问你‘左边这条路是通往天堂的路吗?’的时候,你的回答是‘是’吗?”
这样的话,对于“左边这条路是通往天堂的路吗?”这个问题,说真话和说假话的答案是不同的,但是如果在问他回答是不是“是”,说真话的双重肯定不变答案,而说假话的则会双重否定,将答案板正。

提出这个问题有什么意义呢?你想啊,如果你可以让一个人无论说真话说假话,都让他们的答案是一致的,那……
是了,仿照引题的答案,我们可以问三个人这样三个问题:
问1:“当我问你‘3是说真话的人吗?’的时候,你的回答是‘是’吗?”
问2:“当我问你‘3是说假话的人吗?’的时候,你的回答是‘是’吗?”
问完这两个问题,就可以确定3是什么样的人,如果3是说真话或说假话的人,就直接问他1是不是真假随机的人就行了;如果3是真假随机的人,那么再这样问:“当我问你‘1是说真话的人吗?’的时候,你的回答是‘是’吗?”就可以知道1是什么样的人,三个人的身份也就确定了。

其实这三道题就是绕了一点小弯儿,只要绕过去,就没什么难的了。







推门,其实一直都在

※来源: 【 推理之门 Tuili.Com 】.

 暗夜花儿开新参者打开暗夜花儿开的博客
4 楼: Re:传说中的三大难题及其解法~~ 07年05月22日09点18分


强,拜服.






有你的天空没有风/有你的湖水露笑容
有你的草地真舒坦/有你的夜晚出星星
你是我的好朋友/有你的冬天不会冷
你是我的好朋友/有你的梦境不愿醒


※来源: 【 推理之门 Tuili.Com 】.

 solomondk张华
5 楼: Re:Re:传说中的三大难题及其解法... 07年05月22日10点23分


都是些精髓的题.海盗的还是最困难的,关键是思维的转换.其它的两道都没有什么难度.






______________________________________________________
http://www.cgame.cn/comic/scenario.aspx?sceID=132
http://ktit.bizz.st/ZS/ranking75-94/rank100.htm
http://www.mysterybbs.com/article.aspx?articleid=130
http://lz.zzlwx.com/html/281/content.html
http://v.xuxule.net/index.html
6694599999913899973658792
38QMLT FJCBQM 5s7s74 0oB100
MICIHVFM
http://www.btz.cn/Sorting/Catalog68/Sorting_Indate_Desc_1.html
bt2.5qzone.net
http://www.fxhy.net/soft/
http://www.detectivecn.com/bbs/ 
http://bbs.btpig.com/forumdisplay.php?fid=306

※来源: 【 推理之门 Tuili.Com 】.

 earthmoon地月打开earthmoon的博客
6 楼: Re:传说中的三大难题及其解法~~ 07年05月22日11点19分


条件阿条件……

转题不给全假定就是谋杀别人时间。当初我做三个人说假话的那道题时,就是这样被摆了一道……

(哦,看错了。我说的是那道该死的da,ja……)

[此贴被earthmoon于2007-5-22 11:23:11修改过]






我路过山的时候山不说话 
我路过海的时候海不说话   
我乘着的毛驴一步一步滴滴答答  
我带着的倚天喑哑  
人们说我爱着杨过大侠  
找不到所以在峨嵋安家  
其实我只是爱山中的烟雾  
象十六岁那年绽放的烟花

※来源: 【 推理之门 Tuili.Com 】.

 ding198282无花要闭关修炼打开ding198282的博客
7 楼: Re:Re:传说中的三大难题及其解法... 07年05月22日15点26分


【tl在大作中谈到:】

>第二题:12个乒乓球外形完全相同,有一个重量异常,用无砝码的天平三次称出这个球。
>解法:
>这道题其实并不难,大家只是忽略了一些隐含条件而已~~~~
>为了方便叙述,将12个球分别编号1到12;
>并将12个球分成三组:A1(1,2,3,4),A2(5,6,7,8),A3(9,10,11,12);

>先将A1,A2分别放在天平两个托盘上称:
>(1) 平衡,则1到8号球都是正常的球。
> 第二次这样称:(9,10),(7,8):
> 1)平衡,9和10是正常的球,7和8中有一个异常的球; ----应该是11.12有一个异常的球才对。
> 2)不平衡,9和10中有一个异常的球;
> 第三次只要将两个异常的球(u,v)中u拿出来和1称,若不平衡,则u是异常的球;否则就是v是不正常的球。

>(2) 不平衡(不妨设A1>A2),则9到12号都是正常的球。
> 重新分一下组:B1(1,2,5),B2(3,4,9),B3(6,7,8),B4(10,11,12);
> 第二次这样称:B1,B2:
> 1)平衡,1到5是正常的球,6,7,8中有一个球比正常的球要重(因为6,7,8是从较重的A2中拿出来的,而A1中都是正常的球);
> 第三次只要从6,7,8中拿出6和7称,平衡则8是异常的球,不平衡则较重的是异常的球。

> 2)不平衡,则6,7,8是正常的球。
> 若B1>B2,则(1,2)中有一个比正常球轻的球(因为1,2是在较轻的A1中),其他球正常。
> 那么第三次就只要将1和2称一下就可以了。
> 若B1<B2,则(3,4)中有一个比正常球轻的球或是5比正常球重,其他球正常。
> 那么第三次就只要将3和4称一下,如果平衡,则5是异常球;否则就是3,4中较轻的球不正常。

>这样就将所有情况讨论完了。







献给死去的爱人
            立道原造
你已化为幽灵,    被人忘记,却在我的眼前,    若离若即。
当那陌生的土地上,    苹果花飘香时节,你在那遥远的夜空下,    上面星光熠熠。

也许那里的春夏,    不会匆匆交替,——你不曾为我,    嫣然一笑,
——也不曾和我,    窃窃低语。你悄悄地生病,静静地死去,    宛如在睡梦中吟着小曲。

你为今霄的悲哀,    拨亮了灯芯,
我为你献上几枝,    欲谢的玫瑰。
这就是我为你守夜,    和那残月的月光一起。

也许你的脑海里,    没有我的影子,
也不接受我的,    这番悲戚。
但愿你在结满绿苹果的树下,    永远得到安息。

※来源: 【 推理之门 Tuili.Com 】.

1页/共1页(总计6个回复)
每次上网自动访问推理之门   |    将推理之门加入收藏夹
邮件联系:zhejiong@126.com  沪ICP备2021006552号  沪公网安备31011502006128号  推理之门  版权所有 2000-2024