利益最大化是他们共同的目的,我们从代码上看出,分为五个海盗:
如果老大死了,则有老二海盗分配,老二海盗面临同样的问题,需要看自己死后的利益分配变化。然后是老三海盗,老四海盗。我么不妨先把老大称作五级海盗,老二称作四级海盗。
所以:
2级海盗无论提出什么方案,都不会有多数人反对(自己支持,另一个人反对不能构成多数反对)。所以2级海盗肯定会提出100,0的分配方案,自己独享所有金币。
猜到2级海盗的分配方案后,3级海盗会提出99,0,1的分配方案。这样1级海盗因获得了比2级海盗方案中更多的金币,所以会支持3级海盗的方案。
猜到3级海盗的分配方案后,4级海盗会提出99,0,1,0的分配方案。这样2级海盗获得了比3级海盗方案中更多的金币,所以会支持4级海盗的方案。
猜到4级海盗的分配方案后,5级海盗会提出98,0,1,0,1的分配方案。这样1级海盗和3级海盗获得了比4级海盗方案中更多的金币,所以会支持5级海盗的方案。
所以,5级海盗提出的分配方案为98,0,1,0,1.
直接点直接上代码,我觉的看代码更容易分析出,不会的再看分析
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<memory.h>
//打印数组
void display(int *a,int n)
{
int i;
for (i=0;i<n-1;i++)
{
printf("%d, ",a[i]);
}
printf("%d\n",a[i]);
}
//从小到大排序,不交换数据
void sort(int *a,int n,int zc,int m)
{
int *point=NULL;
int i,j,k,l=0,sum=0,temp;
n--;
if (zc>=n)
{
a[n]=-1;
return;
}
point = (int*)malloc( sizeof(int)*n );
for (i=0;i<n;i++)//对角标初始化
{
point[i]=i;
}
for (i=0;i<n-1;i++)
{
k=i;
for (j=i+1;j<n;j++)
{
if (a[point[k]]>a[point[j]])
{
k = j;
}
}
if (k!=i)
{
temp = point[i];
point[i] = point[k];
point[k] = temp;
}
}//end for
//display(point,n);
//开始贿赂zc个人
for (i=0;i<zc;i++)
{
if (a[point[i]]==-1)
{
a[point[i]]=0;
continue;
}
a[point[i]]++;
sum+=a[point[i]];//统计花费的金币
}
for (;i<n;i++)
{
a[point[i]] = 0;
}
//表示第n个人必死,因为金币不够分
if (m>sum)
{
a[n]=m-sum;
}else
{
a[n]=-1;
}
free(point);//释放内存
}
//n:海盗数
//m:金币数
//q:支持人数比例
void fun(int n,int m,int q)
{
int i,zc,*person;//zc表示支持的人数
//过滤参数不合法的情况,q的合法值为
if (n<=0||m<=0|| q<0 ||q>100)
{
return ;
}
if ( n==1 ) //
{
printf("%d\n",m);
return;
}
//如果需要支持率100,除最后一个外,其余都得挂掉
if (q==100)
{
for (i=0;i<n-1;i++)
{
printf("-1 , ");
}
printf("%d",m);
return ;
}
person = (int*)malloc(sizeof(int)*n);//n个人
person[0] = m;
for (i=2;i<=n;i++)
{
zc = i * q/100;//zc的值表示除了出方案的人支持外还另外需要支持的人数
sort(person,i,zc,m);
}
display(person,n);//打印结果
free(person);//释放内存
}
int main()
{
int i=1;
for (i=0;i<=7;i++)
{
fun(i,100,60);
}
system("pause");
return 0;
}