本文用递归方法解决一个智力题。题目如下：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>
// 得到最大利润分配
// 输入参数：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;
} 这道题的答案有些让人吃惊，本以为第一个人最危险，反而能获得较大利益。问题出在题目的假设：
每个人都是理性的且追求最大的利益，从而低估了生命的价值。