有趣的海盗分金问题

摘要：这是一道推理、博弈的题目，同时也经常出现在面试过程中

---

前言：今天在刷题的时候，刷到了这道题，一开始没有做出来，后面百度后觉得非常有意思，就总结归纳了一下。

---

题目：

首先从5号海盗开始，因为他是最安全的，没有被扔下大海的风险，因此他的策略也最为简单，即最好前面的人全都死光光，那么他就可以独得这100枚金币了。

接下来看4号，他的生存机会完全取决于前面还有人存活着，因为如果1号到3号的海盗全都喂了鲨鱼，那么在只剩4号与5号的情况下，不管4号提出怎样的分配方案，5号一定都会投反对票来让4号去喂鲨鱼，以独吞全部的金币。哪怕4号为了保命而讨好5号，提出（0，100）这样的方案让5号独占金币，但是5号还有可能觉得留着4号有危险，而投票反对以让其喂鲨鱼。因此理性的4号是不应该冒这样的风险，把存活的希望寄托在5号的随机选择上的，他只有有支持3号的方案或者比3号更好的方案上才能绝对保证自身的性命。

再来看3号，他经过上述的逻辑推理之后，就会提出（100，0，0）这样的分配方案，因为他知道4号哪怕一无所获，也还是会无条件的支持他而投赞成票的，那么再加上自己的1票就可以使他稳获这100金币了。

但是，2号也经过推理得知了3号的分配方案，那么他就会提出（98，0，1，1）的方案。因为这个方案相对于3号的分配方案，4号和5号至少可以获得1枚金币，理性的4号和5号自然会觉得此方案对他们来说更有利而支持2号，不希望2号出局而由3号来进行分配。这样，2号就可以屁颠屁颠的拿走98枚金币了。

不幸的是，1号海盗更不是省油的灯，经过一番推理之后也洞悉了2号的分配方案。他将采取的策略是放弃2号，而给3号1枚金币，同时给4号或5号2枚金币，即提出（97，0，1，2，0）或（97，0，1，0，2）的分配方案。由于1号的分配方案对于3号与4号或5号来说，相比2号的方案可以获得更多的利益，那么他们将会投票支持1号，再加上1号自身的1票，97枚金币就可轻松落入1号的腰包了。

总结：

这里只考虑了金币的因素，其实生命的因素没有考虑上。所以个人认为这个标准答案也并不标准，不过这道题可以让人联想很多，是一道很意思的题目，现实生活中的这种博弈也有很多，很值得思考。下面这两篇文章写的也非常不错：

http://wemedia.ifeng.com/93859560/wemedia.shtml。

https://www.jianshu.com/p/ab2f71802733

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int gold[20000],bisi;

int main ()
{
    int i,j,k;
    int s;
    unsigned long int haidao,jinbi;
    unsigned long int left ;
    int xyjb,tmp,tmp1;
    int huilu1,huilu2;
    double bfb,bfs;
    scanf("%ld %ld %lf",&haidao,&jinbi,&bfb);
    bfs=100.0/bfb;
    //////////////////////处理特殊
    if(haidao==1||bfb==0)
    {printf("%d\n",jinbi );return 0;}
    if(haidao/bfs<1)
    {printf("%d\n",jinbi );return 0;}
    if(haidao/bfs>=haidao-1)
    {printf("-1\n");return 0;}
    memset(gold,0,sizeof(gold));
    //////////////////////////////////////////////
    if(bfb>=50)
    {
        bisi=1;
    }
    else
    {
        bisi=0;
        gold[0]=1;
    }
    xyjb=0;

    ///////////初始化
    for(i=3;i<=haidao;i++)
    {
        xyjb=0;
        huilu1=i/bfs;
        if(i/bfs>=i-1)
        {
            bisi++;
            continue;
        }
        if(i/bfs<1)
        {
            gold[0]=i-1;
            continue;
        }
        /////////// 特殊处理完毕

        huilu2=huilu1-bisi;
        if(huilu2<=0)
        {
            memset(gold,0,sizeof(gold));
            gold[0]=i-1;
            bisi=0;
            if(i==haidao)
            {
                printf("%d\n",jinbi);
                return 0;
            }
            continue;
        }
        else if(huilu2>0)
        {
            //////////////计算贿赂所需金币
            tmp=0;
            for(j=0;j<1000;j++)
            {
                tmp1=tmp;
                tmp+=gold[j];
                if(tmp>=huilu2) break;
                xyjb+=(j+1)*gold[j];
            }
            xyjb+=(huilu2-tmp1)*(j+1);
            if(xyjb>jinbi)
            {
                bisi++;
                if(i==haidao)
                {
                    printf("-1\n");
                    return 0;
                }
                continue;
            }
            else
            {
                left=jinbi-xyjb;
                gold[j+1]=huilu2-tmp1;
                for (k=j;k>0;k--)
                {
                    gold[k]=gold[k-1];
                }
                gold[0]=i-huilu2-1;
                s=(20000-j-5)*sizeof(gold[0]);
                memset(&gold[j+2],0,s);
                bisi=0;
                if(left<=1000) gold[left]++;
            }
        }
    }

    //end for

    if(bisi>0) printf("-1\n");
    else
    {
        printf("%d\n",left);
    }
}

• 本文作者： th3ee9ine
• 本文链接： https://www.blog.ajie39.top/2021/05/05/有趣的海盗分金问题/
• 版权声明： 本博客所有文章除特别声明外，均采用 LICENSE 下的许可协议。转载请注明出处！