代码编织梦想

海盗分金问题

有10个强盗A~J,得到100个金币,决定分掉,分法怪异:首先A提出分法,B~J表决,如果不过半数同意,就砍掉A的头。然后由B来分,C~J表决,如果不过半数同意,就砍掉B的头。依次类推,如果假设强盗都足够聪明,在不被砍掉头的同时获得最多的金币。问:最后结果如何(精确结果)。

分析与解答

所有的海盗都乐于看到他们的一位同伙被扔进海里,不过,如果让他们选择的话,他们还是宁可得到一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的,而且知道其他的海盗也是有理性的。此外,没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次,并且每个人都清楚自己和其他所有人的等级。这些金块不能再分,也不允许几名海盗共有金块,因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每个人都只为自己打算的海盗。最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢?

为方便起见,我们按照这些海盗的怯懦程度来给他们编号。最怯懦的海盗为1号海盗,次怯懦的海盗为2号海盗,依次类推。这样最厉害的海盗就应当得到最大的编号,而方案的提出就将倒过来从上至下地进行。

分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时,你容易知道何种决策有利而何种决策不利。确定了这一点后,你就可以把它用到倒数第2次决策上,依次类推。如果从游戏的开头出发进行分析,那是走不了多远的。其原因在于,所有的战略决策都是要确定:“如果我这样做,那么下一个人会怎样做?”

因此,在你以下海盗所做的决定对你来说是重要的,而在你之前的海盗所做的决定并不重要,因为你反正对这些决定也无能为力了。

记住了这一点,就可以知道我们的出发点应当是游戏进行到只剩两名海盗,即1号和2号的时候。这时最厉害的海盗是2号,而他的最佳分配方案是一目了然的:100块金子全归他一人所有,1号海盗什么也得不到。由于他自己肯定为这个方案投赞成票,这样就占了总数的50,因此方案获得通过。

现在加上3号海盗。1号海盗知道,如果3号的方案被否决,那么最后将只剩2个海盗,而1号将肯定一无所获。此外,3号也明白1号了解这一形势。因此,只要3号的分配方案给1号一点甜头使他不至于空手而归,那么不论3号提出什么样的分配方案,1号都将投赞成票。因此,3号需要分出尽可能少的一点金子来贿赂1号海盗,这样就有了下面的分配方案:3号海盗分得99块金子,2号海盗一无所获,1号海盗得1块金子。

4号海盗的策略也差不多。他需要有50的支持票,因此同3号一样也需再找一人做同党。他可以给同党的最低贿赂是1块金子,而他可以用这块金子来收买2号海盗。因为如果4号被否决而3号得以通过,则2号将一块也得不到。因此,4号的分配方案应是:99块金子归自己,3号一块也得不到,2号得1块金子,1号也是一块也得不到。

5号海盗的策略稍有不同。他需要收买另两名海盗,因此至少得用2块金子来贿赂,才能使自己的方案得到采纳。他的分配方案应该是:98块金子归自己,1块金子给3号,1块金子给1号。

这一分析过程可以照着上述思路继续进行下去。每个分配方案都是惟一确定的,它可以使提出该方案的海盗获得尽可能多的金子,同时又保证该方案肯定能通过。照这一模式进行下去,10号海盗提出的方案将是96块金子归他所有,其他编号为偶数的海盗各得1块金子,而编号为奇数的海盗则什么也得不到。这就解决了10名海盗的分配难题。

试想一下500名海盗分金会是怎样的结果呢?


个人简介


我是一名测试兼开发工程师,目前25K,目前做的是无人驾驶,欢迎和大家一起交流测试技术,一起高薪就业,我们还有一起打妖怪的群哦,还有面试题小程序哦

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/stetstet/article/details/124707598

测试工程师常见面试题-爱代码爱编程

目录 测试 一,测试了解 二,bug缺陷管理 三,接口测试Jmeter,Fiddler 四,接口测试用例的设计: 五,单元测试  六,弱网测试 七,web测试和app测试的异同  八,APP性能测试指标 九,APP相关问题-java/android开发 十,请说明Android手机和IOS手机,系统有什么区别? 十一,IE空白页面原

2021年软件测试面试题大全-爱代码爱编程

目录   一、面试基础题 简述测试流程: 什么是软件测试?软件测试的目的与原则 问:软件生存周期及其模型是什么? 什么是软件质量? 自动化测试脚本开发的主要步骤: 目前主要的测试用例设计方法是什么? 常见的测试用例设计方法都有哪些?请分别以具体的例子来说明这些方法在测试用例设计工作中的应用 测试的策略有哪些? 单元测试的策略有哪些?

软件测试面试题汇总(一)-爱代码爱编程

目录   一、面试基础题 简述测试流程: 什么是软件测试?软件测试的目的与原则 问:软件生存周期及其模型是什么? 什么是软件质量? 自动化测试脚本开发的主要步骤: 目前主要的测试用例设计方法是什么? 常见的测试用例设计方法都有哪些?请分别以具体的例子来说明这些方法在测试用例设计工作中的应用 测试的策略有哪些? 单元测试的策略有哪些?

软件测试面试之智力题-爱代码爱编程

● 5只猫 五分钟捉5只老鼠 请问100分钟捉100只老鼠需要多少只猫? 参考回答: 5X5M=5Y KX100M=100Y K=5 需要5只猫 ● 圆桌,两个人,轮流放硬币,不能重叠,半径为1,某一方不能放下去,则为输。问先手赢 后手赢。 参考回答: 先手赢。圆桌对称,先手放一个,后手都能找到对称的位置放,但是除了圆心。 ● 逻辑题:3升的杯

测试面试题(六)-爱代码爱编程

1.osi七层模型 七层模型,亦称OSI(Open System Interconnection)。参考模型是国际标准化组织(ISO)制定的一个用于计算机或通信系统间互联的标准体系,一般称为OSI参考模型或七层模型。 它是一个七层的、抽象的模型体,不仅包括一系列抽象的术语或概念,也包括具体的协议。 2.公司的测试流程 1、测试需求分析阶段:阅读需求,理解

测试面试题 七-爱代码爱编程

1、webdriver模块不可以完成哪件事? 控制浏览器前进 2、driver.find_element_by_id(“kw”).send_keys(Keys.CONTROL,‘a’)这段代码什么意思 找到id为kw的,输入a 3、通过哪种方式获取appPackage和appActivity? aapt dump badging + apk

2021...我肝了2万字最全软件测试面试题!附答案(必须收藏起来!)-爱代码爱编程

目录 一、面试基础题 二、性能测试 三、安全性测试 四、智力题 五、简历模板 一、面试基础题 简述测试流程: 1、阅读相关技术文档(如产品PRD、UI设计、产品流程图等)。 2、参加需求评审会议。 3、根据最终确定的需求文档编写测试计划。 4、编写测试用例(等价类划分法、边界值分析法等)。 5、用例评审(主要参与人员:开发、测试、产

测试实战面试题-爱代码爱编程

二、测试实战面试题 1. 我现在有个程序,发现在Windows上运行的很慢,怎么判别是程序存在问题还是软硬件系统存在问题 1、检查系统是否有中毒的特征 2、检查软件/硬件的配置是否符合软件的推荐标准 3、确认当前的系统是否独立,即没有对外提供什么消耗CPU资源的服务 4、如果是C/S或者B/S结构的软件,需要检查是不是因为与服务器的连接有问题,或

内容较长:软件测试面试题汇总-爱代码爱编程

一、面试基础题 简述测试流程: 1、阅读相关技术文档(如产品PRD、UI设计、产品流程图等)。 2、参加需求评审会议。 3、根据最终确定的需求文档编写测试计划。 4、编写测试用例(等价类划分法、边界值分析法等)。 5、用例评审(主要参与人员:开发、测试、产品、测试leader)。 6、开发提交代码至SVN或者GIT ,配管搭建测试环境。

软件测试面试题大全-爱代码爱编程

目录 一、面试基础题 简述测试流程: 什么是软件测试?软件测试的目的与原则 问:软件生存周期及其模型是什么? 什么是软件质量? 自动化测试脚本开发的主要步骤: 目前主要的测试用例设计方法是什么? 常见的测试用例设计方法都有哪些?请分别以具体的例子来说明这些方法在测试用例设计工作中的应用 测试的策略有哪些? 单元测试的策略有哪些? 正交

软件测试面试题汇总-爱代码爱编程

一、面试基础题 简述测试流程: 1、阅读相关技术文档(如产品PRD、UI设计、产品流程图等)。 2、参加需求评审会议。 3、根据最终确定的需求文档编写测试计划。 4、编写测试用例(等价类划分法、边界值分析法等)。 5、用例评审(主要参与人员:开发、测试、产品、测试leader)。 6、开发提交代码至SVN或者GIT ,配管搭建测试环境。 7

软件测试面试题:Activity生命周期?-爱代码爱编程

Activity生命周期? 周期即活动从开始到结束所经历的各种状态。生命周期即活动从开始到结束所经历的各个状态。从一个状态到另一个状态的转变,从无到有再到无,这样一个过程中所经历的状态就叫做生命周期。 Activity本质上有四种状态: 1.运行(Active\/Running):Activity处于活动状态,此时Activity处于栈顶

软件测试面试题:http和https区别?-爱代码爱编程

http和https区别? HTTP协议传输的数据都是未加密的,也就是明文的,因此使用HTTP协议传输隐私信息非常不安全,为了保证这些隐私数据能加密传输,于是网景公司设计了SSL(Secure Sockets Layer)协议用于对HTTP协议传输的数据进行加密,从而就诞生了HTTPS。简单来说,HTTPS协议是由SSL和HTTP协议

2022年测试工程师面试题大合集「 功能测试,自动化测试等」300道题_mysql 数据库有一张成绩表,表里面包含name, lesson, score,三个字段,分别表示_雁卿雁卿呀的博客-爱代码爱编程

测试面试 1 测试理论, 13道题2 工作中的测试思维, 56道题3 工作中的测试思维,进阶, 39道题定位问题用例设计 4 自动化, 53道题UI自动化接口自动化fixture 5