在120枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币,最坏情况下,能不能只比较5次就检测出这枚假币?

本文主要是介绍在120枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币,最坏情况下,能不能只比较5次就检测出这枚假币?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题目我想先通过另外一道题目引入我的方法:

13枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币,最坏情况下,能不能只比较3次就检测出这枚假币?

将13枚硬币分为三组

ABCD  EFGH  IJKLM

这里引入一个概念,每次天平倾斜方向称之为X方向、Y方向、和平衡

X方向不一定就是向左倾斜,只不过和Y方向是相对的。我们可以定义任意一种倾斜方向为X方向

(注:当文中所说M和N进行比较时,默认前一个放X位,后一个放在Y位,即M在X位,N在Y位)

将ABCD和EFGH进行比较:

得到三种情况:L位倾斜、R位倾斜和平衡

假设平衡,则比较IA和JK,如果还是平衡则比较L和A可以得到是L还是M的问题,如果不平衡则记录倾斜方向,假设为X方向倾斜,最后比较J和K,如果第三次和第二次一样位X方向倾斜,则假币没有变换方向为K反之为J,平衡则为I

但是最坏情况下应该是第一次使用天平就发生倾斜,假设为X位倾斜则第二次比较ABE和CDF,如果平衡则在GH中,略。如果不平衡,则要则要看第二次使用天平是否和第一次一样是X方向倾斜,如果还是X方向倾斜则假币没有变换方向,假币在ABF中,反之在CDE中,假设第一次第二次都是X方向倾斜,则假币没有变换方向那么假币一定在ABE中,如果变换方向为Y方向倾斜则假币在过程中调换方向假币在CDE中。

假设假币在ABF中,那么第三次我们比较A和B,还是X方向倾斜则假币三次都没有变换方向所以假币为A,反之假币为B,平衡则为F,同理。

通过这道题,我思考了一个概念,N次使用天平最多能找到多少个硬币中的假币呢?

每一次进行比较我们都有三中状态,X方向倾斜、Y方向倾斜、和平衡

那上题中3次使用天平我们就可以得到 3^{3} =27种不同的结果,这时我想到XYX和YXY方向倾斜其实本质上是一样的,因为我们由于假币重量是重还是轻是未知的,所以只能判断第一次使用天平和第二次方向是相同还是相反的,所以这个结果需要除以2,但是有一种情况例外:即三次都为平衡状态,所以我们要先在总的情况下-1

所以,我们最终会得到 (3^{3}-1)/2 = 13 种情况,也就是说最终我们会获得13种不同的情况,也就是在13个硬币下使用三次天平找到假币。

同理5次使用天平最多在(3^{5}-1)/2 = 121种情况,也就是最多在121枚硬币中使用五次天平找到假币

推广到N次,则N次最多在(3^{N}-1)/2 个硬币中找到假币

对于本题具体的实践过程比较复杂,将三维推广到五维更加难写,欢迎大家能够整理出具体过程并在评论区附上链接。


2022.10.18于山东工商学院西校区5257

这篇关于在120枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币,最坏情况下,能不能只比较5次就检测出这枚假币?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/801235

相关文章

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

浅析CSS 中z - index属性的作用及在什么情况下会失效

《浅析CSS中z-index属性的作用及在什么情况下会失效》z-index属性用于控制元素的堆叠顺序,值越大,元素越显示在上层,它需要元素具有定位属性(如relative、absolute、fi... 目录1. z-index 属性的作用2. z-index 失效的情况2.1 元素没有定位属性2.2 元素处

查看Oracle数据库中UNDO表空间的使用情况(最新推荐)

《查看Oracle数据库中UNDO表空间的使用情况(最新推荐)》Oracle数据库中查看UNDO表空间使用情况的4种方法:DBA_TABLESPACES和DBA_DATA_FILES提供基本信息,V$... 目录1. 通过 DBjavascriptA_TABLESPACES 和 DBA_DATA_FILES

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手:启用 pprof3. CPU Profiling:分析 C

MySQL进阶之路索引失效的11种情况详析

《MySQL进阶之路索引失效的11种情况详析》:本文主要介绍MySQL查询优化中的11种常见情况,包括索引的使用和优化策略,通过这些策略,开发者可以显著提升查询性能,需要的朋友可以参考下... 目录前言图示1. 使用不等式操作符(!=, <, >)2. 使用 OR 连接多个条件3. 对索引字段进行计算操作4

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今,数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

在不同系统间迁移Python程序的方法与教程

《在不同系统间迁移Python程序的方法与教程》本文介绍了几种将Windows上编写的Python程序迁移到Linux服务器上的方法,包括使用虚拟环境和依赖冻结、容器化技术(如Docker)、使用An... 目录使用虚拟环境和依赖冻结1. 创建虚拟环境2. 冻结依赖使用容器化技术(如 docker)1. 创

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.