本文用遞歸方法解決一個(gè)智力題。題目如下：5個(gè)強(qiáng)盜分100個(gè)金幣，如果第一個(gè)人提出的分配方案得到半數(shù)以上（含半數(shù)）的人同意則執(zhí)行，否則處死第一個(gè)人，再由第二個(gè)人提出方案，直到分配完成。第一個(gè)人提出怎樣的方案才能既獲得最大利益又沒(méi)有殺身之禍？這里假設(shè)每個(gè)人都是理性的且追求最大的利益。
第1個(gè)人提出的分配方案要滿足兩個(gè)條件，一是得到半數(shù)以上的人支持。二是使自己獲得最大的利益。為了取得別人的支持需要給他們部分利益，顯然這部分利益要超過(guò)他們?cè)诘?/span>2個(gè)人提出的可接受分配方案中所獲得的利益。如果不這樣，他們會(huì)反對(duì)，從而接受第2個(gè)人提出的方案。
問(wèn)題變成了求第2個(gè)人提出的可接受方案。他的方案也要滿足上面的兩點(diǎn)。以此類推，問(wèn)題變成最后一個(gè)人提出可接受方案，顯然可以提可接受的方案，因?yàn)闆](méi)有人反對(duì)，把金幣全部分給自己。
下面是他們的方案：
第5個(gè)人的方案：0，0，0，0，100。（不需要?jiǎng)e人的支持）
第4個(gè)人的方案：0，0，0，100，0。（不需要?jiǎng)e人的支持）
第3個(gè)人的方案：0，0，99，0，1。（第5個(gè)人會(huì)支持他）
第2個(gè)人的方案：0，99，0，1，0。（第4個(gè)人會(huì)支持他）
第1個(gè)人的方案：98，0，1，0，1。（第3，5個(gè)人會(huì)支持他）
從分析中可得，這個(gè)問(wèn)題可以用遞歸求解，把求n個(gè)人的分配問(wèn)題變成求n-1個(gè)人的分配，實(shí)現(xiàn)代碼如下。
#include <vector>
// 得到最大利潤(rùn)分配
// 輸入?yún)?shù)：people有多少個(gè)人分配
// 輸入?yún)?shù)：gold有多少金幣
// 輸出參數(shù)：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個(gè)人數(shù)的最佳分配方案
GetMaxProfits(people-1, gold, p_get);
// 計(jì)算為了得到vote人數(shù)的支持，需要讓出多少利益
int min = gold+1; // 需要讓出的利益，初始為一個(gè)較大的數(shù)
std::vector<int> tmpset(vote, 0);; // 記錄給哪些人讓利
// 找出得到較少利益的vote個(gè)人
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個(gè)金幣
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) // 有余額多分配一個(gè)
{
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;
} 這道題的答案有些讓人吃驚，本以為第一個(gè)人最危險(xiǎn)，反而能獲得較大利益。問(wèn)題出在題目的假設(shè)：
每個(gè)人都是理性的且追求最大的利益，從而低估了生命的價(jià)值。