C#实现的海盗分金算法实例

本文实例讲述了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#程序设计有所帮助。

# C# # 海盗分金 # 算法 # C# 生成高质量缩略图程序—终极算法 # C#的3DES加密解密算法实例代码 # C#常见算法面试题小结 # asp.net(c#)两种随机数的算法 # 可用抽考题 # c#汉诺塔的递归算法与解析 # C#加密算法汇总(推荐) # 基于C#代码实现九宫格算法横竖都等于4 # c# 实现MD5 # SHA1 # SHA256 # SHA512等常用加密算法源代码 # 基于私钥加密公钥解密的RSA算法C#实现方法 # c#哈希算法的实现方法及思路 # C#数据结构与算法揭秘五栈和队列 # .net C# 实现任意List的笛卡尔乘积算法代码 # 的人 # 自己的 # 一票 # 一枚 # 程序设计 # 分配方案 # 将被 # 都是 # 相关内容 # 第一个 # 给他 # 会在 # 价值连城 # 一颗 # 感兴趣 # 数据结构 # 给自己 # 给大家 # 只剩下 # 给他们

返回目录在线咨询

上一篇：Golang如何实现简单的Web缓存_Golang缓存策略与实现方法
下一篇：万网智能建站系统：一站式小程序全网营销解决方案

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

C#实现的海盗分金算法实例

您的项目需求