本文實(shí)例講述了C#實(shí)現(xiàn)的海盜分金算法。分享給大家供大家參考，具體如下：
海盜分金的故事
5個(gè)海盜搶到了100顆寶石，每一顆都一樣的大小和價(jià)值連城。
他們決定這么分：
1。抽簽決定自己的號(hào)碼（1，2，3，4，5）
2。首先，由1號(hào)提出分配方案，然后大家5人進(jìn)行表決，當(dāng)且僅當(dāng)半數(shù)和超過(guò)半數(shù)的人同意時(shí)，按照他的提案進(jìn)行分配，否則將被扔入大海喂鯊魚(yú)。
3。如果1號(hào)死后，再由2號(hào)提出分配方案，然后大家4人進(jìn)行表決，當(dāng)且僅當(dāng)半數(shù)和超過(guò)半數(shù)的人同意時(shí)，按照他的提案進(jìn)行分配，否則將被扔入大海喂鯊魚(yú)。
4。依次類(lèi)推......
問(wèn)題：第一個(gè)海盜提出怎樣的分配方案才能夠使自己的收益最大化
條件：每個(gè)海盜都是很聰明的人,如果前面的人提出的方案對(duì)自己沒(méi)好處肯定會(huì)否決,如果好處比后面持續(xù)下去的方案好就投票。
解決：網(wǎng)上很多解決方法(百度百科：http://baike.baidu.com/view/5221.htm )，下面就是算法總結(jié)，目的就是讓自己得到1半或以上的票。
算法：從后向前來(lái)推理，
i 海盜分為1-5號(hào)，如果只剩下第4,5號(hào)海盜兩個(gè)人分配，4號(hào)則給自己投一票>=50%，條件成立，自己獨(dú)吞總金幣，5號(hào)什么也得不到。
ii 3號(hào)推出了4號(hào)的方案，發(fā)一枚金幣給5號(hào)，拉一票，因?yàn)?號(hào)知道在4號(hào)的方案中自己得不到所以投3號(hào)一票，加上3號(hào)投自己的一票>=50%條件成立，3號(hào)獲得100-1=99枚金幣。
iii 2號(hào)得出3號(hào)方案，給4號(hào)一枚金幣拉一票，同理，2號(hào)票數(shù)(1+1)/4>=50%條件成立，獲得100-1=99枚金幣。
iv 1號(hào)推斷2號(hào)方案中,3號(hào)和5號(hào)不能獲得金幣，于是給他們各一枚金幣則拉兩票，(1+1+1)/5>=50%條件成立，自己獲得100-1-1=98枚金幣。
從上面的推論可以看出，從后向前依次推，如果上一次分配中獲得金幣的海盜本次分配中將不能獲得金幣。
using System;
class pirateAssignGold
{
public static void Main()
{
int pirates=5; //海盜總數(shù)
int gold=100; //金幣總數(shù)
int joinNum; //加入分配的海盜數(shù)
int[] poke=new int[pirates+1]; //每個(gè)海盜一個(gè)口袋
int ticket; //票數(shù)計(jì)數(shù)器
for(int i=pirates;i>=1;i--){
joinNum=pirates-i+1; //此次加入分配的海盜數(shù)
ticket=0;
for(int j=pirates;j>=i;j--)
{
if((pirates-j+1)==joinNum) //如果本海盜就是此次加入分配的最后一個(gè)海盜
{
poke[j]=gold; //利益最大化，把還剩的金幣全給他
gold=gold-poke[j];
ticket=ticket+1;
}
else
{
if(poke[j]>0) //此海盜已經(jīng)獲得了金幣
{
gold=gold+poke[j]; //推論中本次分配者會(huì)使上一次獲得金幣的海盜什么都沒(méi)有。
poke[j]=0;
}
else
{
poke[j]=1; //推論中上一次分配中沒(méi)有獲得金幣的海盜會(huì)在本次獲得金幣。
gold=gold-1;
ticket=ticket+1;
}
}
}
if((double)ticket/(double)joinNum<0.5){ break;} //總得票數(shù)/此次加入分配的海盜數(shù)>=50%則此次分配成立，否則失敗
}
for(int n=1;n<=5;n++){
Console.WriteLine("海盜{0}獲得金幣數(shù){1} ",n,poke[n]);
}
Console.ReadKey();
}
}
更多關(guān)于C#相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《C#數(shù)據(jù)結(jié)構(gòu)與算法教程》、《C#程序設(shè)計(jì)之線程使用技巧總結(jié)》、《C#常見(jiàn)控件用法教程》、《WinForm控件用法總結(jié)》、《C#數(shù)組操作技巧總結(jié)》及《C#面向?qū)ο蟪绦蛟O(shè)計(jì)入門(mén)教程》
希望本文所述對(duì)大家C#程序設(shè)計(jì)有所幫助。