本文用递归方法解决一个智力题。题目如下:5个强盗分100个金币,如果第一个人提出的分配方案得到半数以上(含半数)的人同意则执行,否则处死第一个人,再由第二个人提出方案,直到分配完成。第一个人提出怎样的方案才能既获得最大利益又没有杀身之祸?这里假设每个人都是理性的且追求最大的利益。
第1个人提出的分配方案要满足两个条件,一是得到半数以上的人支持。二是使自己获得最大的利益。为了取得别人的支持需要给他们部分利益,显然这部分利益要超过他们在第2个人提出的可接受分配方案中所获得的利益。如果不这样,他们会反对,从而接受第2个人提出的方案。
问题变成了求第2个人提出的可接受方案。他的方案也要满足上面的两点。以此类推,问题变成最后一个人提出可接受方案,显然可以提可接受的方案,因为没有人反对,把金币全部分给自己。
下面是他们的方案:
第5个人的方案:0,0,0,0,100。(不需要别人的支持)
第4个人的方案:0,0,0,100,0。(不需要别人的支持)
第3个人的方案:0,0,99,0,1。(第5个人会支持他)
第2个人的方案:0,99,0,1,0。(第4个人会支持他)
第1个人的方案:98,0,1,0,1。(第3,5个人会支持他)
从分析中可得,这个问题可以用递归求解,把求n个人的分配问题变成求n-1个人的分配,实现代码如下。
#include <vector>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 得到最大利润分配
// 输入参数: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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
if (vote > 0) // 需要其他人的支持
{
// 得到people-1个人数的最佳分配方案
GetMaxProfits(people-1, gold, p_get);
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 计算为了得到vote人数的支持,需要让出多少利益
int min = gold+1; // 需要让出的利益,初始为一个较大的数
std::vector<int> tmpset(vote, 0);; // 记录给哪些人让利
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 找出得到较少利益的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;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 记录需要让利的人在people-1情况下的利益
std::vector<int> voteprofit(vote, 0);
for (int i=0; i<tmpset.size(); i++)
voteprofit[i] = p_get[tmpset[i]];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 不需要让利的人分配0个金币
for (int i=0; i<people-1; i++)
p_get[i] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 给需要让利的人分配金币
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 自己的利益
p_get[people-1] = surplus;
}
else // 不需要其他人的支持
{
for (int i=0; i<people-1; i++)
p_get[i] = 0;
p_get[people-1] = gold;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main(void)
{
int gold;
int people;
printf("Input gold, people:");
scanf("%d,%d", &people, &gold);
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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;
}
这道题的答案有些让人吃惊,本以为第一个人最危险,反而能获得较大利益。问题出在题目的假设:
每个人都是理性的且追求最大的利益,从而低估了生命的价值。