热门标签 | HotTags
当前位置:  开发笔记 > 程序员 > 正文

两个孩子分蛋糕问题

题目描述:假如有两个孩子--Tom和Marry,两个人都特别喜欢吃蛋糕(A和B),现在有两块相同大小的蛋糕。两

题目描述:假如有两个孩子--Tom和Marry,两个人都特别喜欢吃蛋糕(A和B),现在有两块相同大小的蛋糕。两个人都想吃到尽可能多的蛋糕(即比对方吃的蛋糕多),那么两个人就想做一个游戏:如果由Tom来切蛋糕,首先Tom将第一块蛋糕切成两份(两份可能大小相同,可能不同),那么Marry来指定两个人的选择顺序,规则如下:如果第一次Marry先选,那么,第二次就一定是Tom先选;同理如果第一次Tom先选,第二次就一定是Marry先选,如果两人先选,肯定选择最大的那块。

问题:Tom第一次如何切分蛋糕使得自己能吃到的蛋糕最多?

问题分析:由于每次都是Tom来切分蛋糕,所以Tom可以根据Marry指定的选择顺序进行下一次切分。不失一般性,我们假设每块蛋糕大小都为1,假设第一次Tom将蛋糕A切分为大小两块,假设,那么先选的人肯定选择。首先我们假设Marry先选,那么她第一次选择,而Tom只能选择,第二次肯定是Tom先选,Tom为了获取更多的蛋糕,那么在第二次切的时候就可以分成两份:一份为整个蛋糕B,另一份为大小为0,即两次Marry可以得到蛋糕,Tom可以得到蛋糕。其次我们假设Marry让Tom先选,那么Tom第一次肯定能够得到,而Marry第一次得到,这样第二次就自动是Marry先选,Tom为了获得的蛋糕最多,那么在第二次切分的时候只能是均分,这样Tom和Marry各得到一半,这样Tom得到的总的蛋糕为,而Marry获得的蛋糕为,两次为了都能使Tom获得最多的蛋糕,我们可以令Marryl两次获得的蛋糕量相等,即:,这样我们就可以求解,即Tom在第一次将蛋糕切成3/4和1/4两份,这样Tom两次能获得最多5/4的蛋糕,而Marry只获得的蛋糕为3/4。


通过上面的分析我们知道在这个规则下切两块蛋糕时Tom能获得的最大蛋糕量,那么问题来了,如果给定3块同样大小的蛋糕,每次都是Tom来切,Marry指定先选的人,3次必须有一次是Tom先选。

问题:Tom第一次如何切分蛋糕使得自己能吃到最多的蛋糕?

问题分析:首先蛋糕的大小还是假设为1,Tom第一次将蛋糕切分为:,其中。下面直接讨论选择方式:

1). 如果第一次Marry先选:第一次Marry获得,Tom获得,那么还剩两次,而且Tom有一次先选的机会,根据上面分析的两块蛋糕的情况,后面两次Tom最多可以5/4,Marry获得3/4。则第一次Marry先选可以获得蛋糕量为:,而Tom可获得的蛋糕量为

2). 如果第一次Tom先选:第一次Marry获得,Tom获得,那么后面两次都是Marry先选,Tom为了获得更多的蛋糕必定均匀切分剩余的两块蛋糕,即后面两块蛋糕两人均可以获得1。则第一次Tom先选可以获得的蛋糕量为:,而Marry可获得的蛋糕量为:

为了使得Tom获得的蛋糕最多,那么我们令Marry两种情况下获得的蛋糕量相同,即,求解可得:。即Tom第一次将蛋糕切分为5/8和3/8两块,这样Tom最多可以获得3块蛋糕中的13/8,而Marry可以获得11/8。


写到这里,可能很多人会想:在游戏规则不变的情况下,这个还能不能继续扩展呢?答案是肯定的。


扩展:假如现在有块大小完全相同的蛋糕,每次还是由Tom来进行切分,而Marry来决定两人的先后选择顺序,其中Tom必定有一次先选的机会,那么Tom第一次如何切分蛋糕能使得自己吃到最多的蛋糕呢,获得的蛋糕量为多少?

问题分析:首先初始假设不变:蛋糕的大小还是1,Tom第一次将蛋糕切分为:,其中。假设Tom能获得的蛋糕量为

1). 如果第一次Marry先选:第一次Marry获得,Tom获得,那么还剩次,而且Tom有一次先选的机会,根据上面分析易知此时,后面次Tom最多可以,Marry获得。则第一次Marry先选可以获得蛋糕量为:,而Tom可获得的蛋糕量为

2). 如果第一次Tom先选:第一次Marry获得,Tom获得,那么后面都是Marry先选,Tom为了获得更多的蛋糕必定均匀切分剩余的两块蛋糕,即后面两块蛋糕两人均可以获得。则第一次Tom先选可以获得的蛋糕量为:,而Marry可获得的蛋糕量为:

为了使得Tom获得的蛋糕最多,那么我们可以令Marry两种情况下获得的蛋糕量相同,即


求解可得:

那么Tom获得的蛋糕量为:



这样便可以求解的递推公式:

很显然我们构造了一个等比数列:公比为1/2,首项为,这样我们便可以得到:

那么根据,可以求解


即Tom第一次将蛋糕切成两块,Tom可获得的最大蛋糕量为


上面我们分析的都是Tom有且只有一次先选机会的结果,如果Tom有多次先选结果会怎么样呢?其实分析方法和上面是一样的,只不过假如指定Tom有次先选时,需要求解出Tom有次先选时能获得最大蛋糕量的结果。这里就不详细分析了。



推荐阅读
  • 本文详细探讨了Java中的24种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • PHP 5.2.5 安装与配置指南
    本文详细介绍了 PHP 5.2.5 的安装和配置步骤,帮助开发者解决常见的环境配置问题,特别是上传图片时遇到的错误。通过本教程,您可以顺利搭建并优化 PHP 运行环境。 ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • Python自动化处理:从Word文档提取内容并生成带水印的PDF
    本文介绍如何利用Python实现从特定网站下载Word文档,去除水印并添加自定义水印,最终将文档转换为PDF格式。该方法适用于批量处理和自动化需求。 ... [详细]
  • 尽管某些细分市场如WAN优化表现不佳,但全球运营商路由器和交换机市场持续增长。根据最新研究,该市场预计在2023年达到202亿美元的规模。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 本文探讨了如何在编程中正确处理包含空数组的 JSON 对象,提供了详细的代码示例和解决方案。 ... [详细]
  • Ralph的Kubernetes进阶之旅:集群架构与对象解析
    本文深入探讨了Kubernetes集群的架构和核心对象,详细介绍了Pod、Service、Volume等基本组件,以及更高层次的抽象如Deployment、StatefulSet等,帮助读者全面理解Kubernetes的工作原理。 ... [详细]
  • 本文详细介绍了美国最具影响力的十大财团,包括洛克菲勒、摩根、花旗银行等。这些财团在历史发展过程中逐渐形成,并对美国的经济、政治和社会产生深远影响。 ... [详细]
  • andr ... [详细]
  • Hadoop入门与核心组件详解
    本文详细介绍了Hadoop的基础知识及其核心组件,包括HDFS、MapReduce和YARN。通过本文,读者可以全面了解Hadoop的生态系统及应用场景。 ... [详细]
  • Win11扩展卷无法使用?解决扩展卷灰色问题的指南
    本文详细介绍了在Windows 11中遇到扩展卷灰色无法使用时的解决方案,帮助用户快速恢复磁盘扩展功能。 ... [详细]
  • 武汉大学计算机学院研究生入学考试科目及专业方向
    武汉大学计算机学院为考生提供了多个硕士点,涵盖计算机科学与技术、软件工程、信息安全等多个领域。考研科目包括思想政治理论、英语一或二、数学一或二以及专业基础课程。具体的专业方向和考试科目详见正文。 ... [详细]
  • 本文介绍了如何通过扩展 UnityGUI 创建自定义和复合控件,以满足特定的用户界面需求。内容涵盖简单和静态复合控件的实现,并展示了如何创建复杂的 RGB 滑块。 ... [详细]
author-avatar
AT
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有