百层高塔扔鸡蛋问题新思路

2024-03-12 17:30

本文主要是介绍百层高塔扔鸡蛋问题新思路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

百层高塔扔鸡蛋问题新思路

题目

两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。 最少需要几次测试,才能得到摔碎鸡蛋的楼层?方案如何?

原文链接:http://blog.sina.com.cn/s/blog_6c813dbd0101bh98.html

本文的思路为原创,思路与原文思路完全不同,如有发现讲解有问题,请留言指出,谢谢~

问题解析

这是一个不确定问题的分析,既然是不确定,那么我们只能考虑最差的情况,只要保障证最差情况下能完成任务,那么问题就得到了解决。我说这句话什么意思呢?举个例子:

假如我们第一次测试把鸡蛋在50层扔下时鸡蛋破了;那么此时我们只剩下一个鸡蛋,这个时候,为了保证我们一定能够测出鸡蛋刚好在哪一层能破,我们只能从第一层,一层一层网上尝试。最坏的情况就是鸡蛋刚刚好在49层摔破,这时候我们一共尝试了50次。这就是这种情况下最坏的情况了。假如没有破,那么问题就 转化成了重新尝试100-50层的问题了。依次类推。

所以我们假设在最少需要测试的次数时,第一次选的楼层是k(1<=k<=100)层,那么此时有两种结果:

1:鸡蛋没破碎

2:鸡蛋碎了

此时我们可以用如下图表示:

在这里插入图片描述

假如鸡蛋破了,我们需要一层一层的尝试,总共需要尝试k次:

在这里插入图片描述

假如鸡蛋没破,问题就转换成了最初的问题了,只不过楼层由100层减少到了100-k层,递归进行下去:

在这里插入图片描述

一次递归下去,知道还剩下1层楼:

在这里插入图片描述

我们可以看出,这是一颗二叉树,每一个节点就是我们尝试扔的楼层,树的深度,就是我们需要尝试的次数,而这颗树的总节点数,就是最大楼层数。

观察这棵树的特点,每一层的节点数都比上一层的节点数多一个,并且这一层的节点数和当前层数相等。所以为什么保证在任何最坏的情况下,我们都能在比较少的次数中尝试出最佳扔鸡蛋的楼层,我们要保证树的每一个分支的深度都尽可能的浅,也就是让这棵树的深度尽可能的浅。我们设当前树的最大深度为n,所以可以得出:1+2+3+...+n>=100,即(1+n)*n/2>=100。得到n的最小值为14。

所以我们至少需要尝试14次。

这篇关于百层高塔扔鸡蛋问题新思路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

linux生产者,消费者问题

pthread_cond_wait() :用于阻塞当前线程,等待别的线程使用pthread_cond_signal()或pthread_cond_broadcast来唤醒它。 pthread_cond_wait() 必须与pthread_mutex 配套使用。pthread_cond_wait()函数一进入wait状态就会自动release mutex。当其他线程通过pthread

问题:第一次世界大战的起止时间是 #其他#学习方法#微信

问题:第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示

2024.6.24 IDEA中文乱码问题(服务器 控制台 TOMcat)实测已解决

1.问题产生原因: 1.文件编码不一致:如果文件的编码方式与IDEA设置的编码方式不一致,就会产生乱码。确保文件和IDEA使用相同的编码,通常是UTF-8。2.IDEA设置问题:检查IDEA的全局编码设置和项目编码设置是否正确。3.终端或控制台编码问题:如果你在终端或控制台看到乱码,可能是终端的编码设置问题。确保终端使用的是支持你的文件的编码方式。 2.解决方案: 1.File -> S

vcpkg安装opencv中的特殊问题记录(无法找到opencv_corexd.dll)

我是按照网上的vcpkg安装opencv方法进行的(比如这篇:从0开始在visual studio上安装opencv(超详细,针对小白)),但是中间出现了一些别人没有遇到的问题,虽然原因没有找到,但是本人给出一些暂时的解决办法: 问题1: 我在安装库命令行使用的是 .\vcpkg.exe install opencv 我的电脑是x64,vcpkg在这条命令后默认下载的也是opencv2:x6

问题-windows-VPN不正确关闭导致网页打不开

为什么会发生这类事情呢? 主要原因是关机之前vpn没有关掉导致的。 至于为什么没关掉vpn会导致网页打不开,我猜测是因为vpn建立的链接没被更改。 正确关掉vpn的时候,会把ip链接断掉,如果你不正确关掉,ip链接没有断掉,此时你vpn又是没启动的,没有域名解析,所以就打不开网站。 你可以在打不开网页的时候,把vpn打开,你会发现网络又可以登录了。 方法一 注意:方法一虽然方便,但是可能会有

vue同页面多路由懒加载-及可能存在问题的解决方式

先上图,再解释 图一是多路由页面,图二是路由文件。从图一可以看出每个router-view对应的name都不一样。从图二可以看出层路由对应的组件加载方式要跟图一中的name相对应,并且图二的路由层在跟图一对应的页面中要加上components层,多一个s结尾,里面的的方法名就是图一路由的name值,里面还可以照样用懒加载的方式。 页面上其他的路由在路由文件中也跟图二是一样的写法。 附送可能存在

vue+elementui--$message提示框被dialog遮罩层挡住问题解决

最近碰到一个先执行this.$message提示内容,然后接着弹出dialog带遮罩层弹框。那么问题来了,message提示框会默认被dialog遮罩层挡住,现在就是要解决这个问题。 由于都是弹框,问题肯定是出在z-index比重问题。由于用$message方式是写在js中而不是写在html中所以不是很好直接去改样式。 不过好在message组件中提供了customClass 属性,我们可以利用

Visual Studio中,MSBUild版本问题

假如项目规定了MSBUild版本,那么在安装完Visual Studio后,假如带的MSBUild版本与项目要求的版本不符合要求,那么可以把需要的MSBUild添加到系统中,然后即可使用。步骤如下:            假如项目需要使用V12的MSBUild,而安装的Visual Studio带的MSBUild版本为V14。 ①到MSDN下载V12 MSBUild包,把V12包解压到目录(

YOLO v3 训练速度慢的问题

一天一夜出了两个模型,仅仅迭代了200次   原因:编译之前没有将Makefile 文件里的GPU设置为1,编译的是CPU版本,必须训练慢   解决方案: make clean  vim Makefile make   再次训练 速度快了,5分钟迭代了500次

Pycharm配置conda环境(解决新版本无法识别可执行文件问题)

引言: 很多小伙伴在下载最新版本的pycharm或者更新到最新版本后为项目配置conda环境的时候,发现文件夹目录中无法显示可执行文件(一般为python.exe),以下就是本人遇到该问题后试验和解决该问题的一些方法和思路。 一般遇到该问题的人群有两种,一种是刚入门对pycharm进行conda环境配置的小白(例如我),不熟悉相关环境配置的操作和过程,还有一种是入坑pycharm有段时间的老手