本文實(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)行分配，否則將被扔入大海喂鯊魚。
3。如果1號(hào)死后，再由2號(hào)提出分配方案，然后大家4人進(jìn)行表決，當(dāng)且僅當(dāng)半數(shù)和超過(guò)半數(shù)的人同意時(shí)，按照他的提案進(jìn)行分配，否則將被扔入大海喂鯊魚。
4。依次類推......

問(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)容感興趣的讀者可查看本站專題：《C#數(shù)據(jù)結(jié)構(gòu)與算法教程》、《C#程序設(shè)計(jì)之線程使用技巧總結(jié)》、《C#常見(jiàn)控件用法教程》、《WinForm控件用法總結(jié)》、《C#數(shù)組操作技巧總結(jié)》及《C#面向?qū)ο蟪绦蛟O(shè)計(jì)入門教程》

希望本文所述對(duì)大家C#程序設(shè)計(jì)有所幫助。

最新評(píng)論