随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

智力题:5个强盗分100个金币

       本文用递归方法解决一个智力题。题目如下:5个强盗分100个金币,如果第一个人提出的分配方案得到半数以上(含半数)的人同意则执行,否则处死第一个人,再由第二个人提出方案,直到分配完成。第一个人提出怎样的方案才能既获得最大利益又没有杀身之祸?这里假设每个人都是理性的且追求最大的利益。

    第1提出的分配方案要满足两个条件,一是得到半数以上的人支持。二是使自己获得最大的利益。为了取得别人的支持需要给他们部分利益,显然这部分利益要超过他们在第2个人提出的可接受分配方案中所获得的利益。如果不这样,他们会反对,从而接受第2个人提出的方案。
    问题变成了求第2个人提出的可接受方案。他的方案也要满足上面的两点。以此类推,问题变成最后一个人提出可接受方案,显然可以提可接受的方案,因为没有人反对,把金币全部分给自己。

下面是他们的方案:
第5个人的方案0000100。(不需要别人的支持)
第4个人的方案0001000(不需要别人的支持)
第3个人的方案:009901。(第5个人会支持他)
第2个人的方案:099010。(第4个人会支持他)
第1个人的方案:980101。(第3,5个人会支持他)

    从分析中可得,这个问题可以用递归求解,把求n个人的分配问题变成求n-1个人的分配,实现代码如下。

#include <vector>

// 得到最大利润分配
// 输入参数:people有多少个人分配
// 输入参数:gold有多少金币
// 输出参数:p_get分别方案
void GetMaxProfits(
int people, int gold, std::vector<int>& p_get)
{
    
// 除去自己,还需要得到多少人的支持
    
int vote = (people+1)/2-1;
//    int vote = people/2;

    
if (vote > 0)    // 需要其他人的支持
    {
        
// 得到people-1个人数的最佳分配方案
        GetMaxProfits(people
-1, gold, p_get);

        
// 计算为了得到vote人数的支持,需要让出多少利益
        
int min = gold+1;    // 需要让出的利益,初始为一个较大的数
        std::vector
<int> tmpset(vote, 0);;    // 记录给哪些人让利

        
// 找出得到较少利益的vote个人
        
for (int i=0, c=0; i<people-1 && c<vote; i++)
        {
            
int seq = 0;
            
for (int j=0; j<people-1; j++)
            {
                
if (p_get[i] > p_get[j])
                    seq
++;
            }
            
if (seq < vote)
            {
                tmpset[c
++= i;
            }
        }

        
// 记录需要让利的人在people-1情况下的利益
        std::vector
<int> voteprofit(vote, 0);
        
for (int i=0; i<tmpset.size(); i++)
            voteprofit[i] 
= p_get[tmpset[i]];

        
// 不需要让利的人分配0个金币
        
for (int i=0; i<people-1; i++)
            p_get[i] 
= 0;

        
// 给需要让利的人分配金币
        
int surplus = gold;    // 还有多少可分配的
        
for (int i=0; i<tmpset.size(); i++)
        {
            p_get[tmpset[i]] 
= voteprofit[i];
            surplus 
-= voteprofit[i];
            
if (surplus > 0)    // 有余额多分配一个
            {
                p_get[tmpset[i]]
++;
                surplus
--;
            }
            
else
                break;
        }

        
// 自己的利益
        p_get[people
-1= surplus;
    }
    
else        // 不需要其他人的支持
    {
        
for (int i=0; i<people-1; i++)
            p_get[i] 
= 0;
        p_get[people
-1= gold;
    }
}

int main(void)
{
    
int gold;
    
int people;
    printf(
"Input gold, people:");
    scanf(
"%d,%d"&people, &gold);

    std::vector
<int> p_get(people, 0);
    GetMaxProfits(people, gold, p_get);
    
    
for (int i=0; i<people; i++)
        printf(
"%d\t",p_get[i]);
    
    return 
0;
}

        这道题的答案有些让人吃惊,本以为第一个人最危险,反而能获得较大利益。问题出在题目的假设:每个人都是理性的且追求最大的利益,从而低估了生命的价值。

posted on 2007-11-09 21:10 lemene 阅读(5260) 评论(10)  编辑 收藏 引用

评论

# re: 智力题:5个强盗分100个金币  回复  更多评论   

我觉得应该是这样的,第五个人可以一直反对,除非把所有的金币都给他。我假定如下,如果对下一个海盗来说,得到的金币数量没有变化的话,会选择赞同,每个人都很聪明。
我们给所有的强盗都编上号,从一号到五号。如果最后只剩下四号和五号,那么四号想活命的唯一选择是把钱都给5号。如果剩下3个人,三号想活命就比较好办,给4号一点钱就行,(0,0,99,1,0)对4号来说不同意就得死或者一个金币也没有(变成两个人)。如果有4个人,2号得选择如下,因为对3号来讲,他的最高可以到99,所以如果不到99,他可以尽情反对。所以这次是(0,98,0,1,1)对4号来说,这是可以接受的。对5号来说,这总比上一种情况要好。
1号需要两个人支持是(98,0,0,1,1),因为如果一号的方案通不过,2,3号都有机会拿到大头所以一定会反对。
现每个人在各种情况下的收益如下:(一个人,两个人,。。。五个人):
1号:(0,0,0,0,98)
2号:(0,0,0,99,0)
3号:(0,0,99,0,0)
4号:(0,0,1,1,1)
5号:(100,100,0,1,1)
2007-11-12 21:12 | 我思故我在

# re: 智力题:5个强盗分100个金币[未登录]  回复  更多评论   

可能我没有把题目说清楚,提出方案的人也能参与投票,而且只要达到半数的票方案就可以通过。在这样的前提下,如果只剩下4号和5号,4号会全部分给自己,因为4号会投自己一票,1vs1通过。@我思故我在

2007-11-12 21:47 | lemene

# re: 智力题:5个强盗分100个金币  回复  更多评论   

微软题,流行很久了,呵呵
2008-01-20 21:00 | 伏志

# re: 智力题:5个强盗分100个金币  回复  更多评论   

上述答案的漏洞在于:在这里你要考虑到4号,4号要是认为1号太贪得无厌的话,会不同意,支持3号也一样至少可以得到1元。还有,若剩下了3 、4、 5,你是3号的话你会冒着生命危险拿99吗!?你要是4号会不会一块不要而杀掉贪得无厌的3号!
2008-12-19 19:08 | 生之痕

# re: 智力题:5个强盗分100个金币  回复  更多评论   

你要是3号你会不会和4号每人50呢!?我想我会。那样安全的多。

# re: 智力题:5个强盗分100个金币[未登录]  回复  更多评论   

这个问题的假设是每个强盗追求最多的利益,而且强盗间没有联合。从第一个人的方案看,如果第3和第5号强盗不支持他,他们可能就一块金币也得不到。如果这问题考虑到生命的价值和互相联合,问题就复杂了。
2009-01-19 11:17 | lemene

# re: 智力题:5个强盗分100个金币  回复  更多评论   

楼主答案错误!~
原因是:第3个人和第一个人的分配方案中!对第5个人而言都是1枚金币!~
同等条件下,你不能保证5号会投一号的票!因为他还有一次选择的机会!!
所以应该是97、0、1、0、2!
用数学模型解释很不错!~
可是小于等于2和小于2的机会,在实际中是天壤之别的。5号的机会是小于等于2不是小于2,从心理学的角度上,这人如果正常肯定是肯定不会投1号的!
所以楼主的答案没有注意到这个小小的问题,导致你的推论于实际完全不符。
2009-04-07 12:38 | wx

# re: 智力题:5个强盗分100个金币[未登录]  回复  更多评论   

To wx
假设第5个人不投1号一票,那么在第2个人分配时,他的投票就不起作用,最终分配结果可能是:
1 2 3 4 5
X 99 0 1 0
那么5号就一个金币也得不到。
2009-04-08 21:33 | lemene

# re: 智力题:5个强盗分100个金币  回复  更多评论   

理性的强盗总是贪婪的。

如果各位是第三号强盗,你会同意1,2号强盗的意见吗?不会的,因为1,2号强盗死了,第四号强盗为了保命一定为同意三号强盗的任何分配意见的,因此,三号强盗能希望,1,2号都死,自己能获得最大的100。

第四号强盗为了避免自己的这种命运的发生肯定不会让1,2号强盗去死的,谁给他更多,他就会支持谁,他有2个选择,但是他同样清楚他必须联合第5个强盗,不然分配方案无法通过

而作为第五号强盗来说,知道让1,2号强盗死了,自己肯定什么也拿不到任何东西,所以他的心态和第四号强盗是一样的。

因此第一号强盗要生存,唯一的办法就是把100个金币平分给第四和第五个强盗,因为他不平分。第四和第五号强盗就会幻想第二号强盗给他们更多,第二号强盗就可能会平分给他们,

对于第一二号强盗来说,要有两票才能保命,而这两票就是第四五号强盗。

对于此时的第一号强盗还没有完,当他知道第二号强盗这样的心思的时候,他会考虑获得第二号强盗和第四号或者第五号强盗的支持,所以我人物结果可能是:

A,49,B,1,C,0,D,51,E,0

或者:A,49,B,1,C,0,D,0,E51
2011-05-18 16:20 | 流沙

# re: 智力题:5个强盗分100个金币  回复  更多评论   

试一下不登陆可不可以评论
2012-08-10 10:50 | xxoo

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理