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#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25