查看: 289|回复: 0

[ASP.NET教程] C#实现的海盗分金算法实例

发表于 2018-2-10 08:00:07

本文实例讲述了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枚金币。

从上面的推论可以看出,从后向前依次推,如果上一次分配中获得金币的海盗本次分配中将不能获得金币。

  1. using System;
  2. class pirateAssignGold
  3. {
  4. public static void Main()
  5. {
  6. int pirates=5; //海盗总数
  7. int gold=100; //金币总数
  8. int joinNum; //加入分配的海盗数
  9. int[] poke=new int[pirates+1]; //每个海盗一个口袋
  10. int ticket; //票数计数器
  11. for(int i=pirates;i>=1;i--){
  12. joinNum=pirates-i+1; //此次加入分配的海盗数
  13. ticket=0;
  14. for(int j=pirates;j>=i;j--)
  15. {
  16. if((pirates-j+1)==joinNum) //如果本海盗就是此次加入分配的最后一个海盗
  17. {
  18. poke[j]=gold; //利益最大化,把还剩的金币全给他
  19. gold=gold-poke[j];
  20. ticket=ticket+1;
  21. }
  22. else
  23. {
  24. if(poke[j]>0) //此海盗已经获得了金币
  25. {
  26. gold=gold+poke[j]; //推论中本次分配者会使上一次获得金币的海盗什么都没有。
  27. poke[j]=0;
  28. }
  29. else
  30. {
  31. poke[j]=1; //推论中上一次分配中没有获得金币的海盗会在本次获得金币。
  32. gold=gold-1;
  33. ticket=ticket+1;
  34. }
  35. }
  36. }
  37. if((double)ticket/(double)joinNum<0.5){ break;} //总得票数/此次加入分配的海盗数>=50%则此次分配成立,否则失败
  38. }
  39. for(int n=1;n<=5;n++){
  40. Console.WriteLine("海盗{0}获得金币数小贝 ",n,poke[n]);
  41. }
  42. Console.ReadKey();
  43. }
  44. }
复制代码

更多关于C#相关内容感兴趣的读者可查看本站专题:《C#数据结构与算法教程》、《C#程序设计之线程使用技巧总结》、《C#常见控件用法教程》、《WinForm控件用法总结》、《C#数组操作技巧总结》及《C#面向对象程序设计入门教程》

希望本文所述对大家C#程序设计有所帮助。

您可能感兴趣的文章:

  • asp.net(c#)两种随机数的算法,可用抽考题
  • C# 生成高质量缩略图程序—终极算法
  • C#数据结构与算法揭秘五 栈和队列
  • c# 实现MD5,SHA1,SHA256,SHA512等常用加密算法源代码
  • c#汉诺塔的递归算法与解析
  • .net C# 实现任意List的笛卡尔乘积算法代码
  • C#加密算法汇总(推荐)
  • C#的3DES加密解密算法实例代码
  • c#哈希算法的实现方法及思路
  • 基于私钥加密公钥解密的RSA算法C#实现方法
  • C#常见算法面试题小结
  • 基于C#代码实现九宫格算法横竖都等于4


回复

使用道具 举报