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