文档章节

动态规划--100层楼和两个玻璃球

H
 Henrykin
发布于 2017/03/28 09:46
字数 437
阅读 97
收藏 0

作者:bh lin
链接:https://www.zhihu.com/question/31855632/answer/54367825
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
 

这个题目首先是关于“最优”的定义。
考虑best-worse case最坏情况下最优。也就是说假如你的算法是从第一楼逐楼往上试,那么相应最坏的情况是在100楼破,相应的是一百次。

这种情况下最优策略也就是匿名用户提到的从14楼开始递减间隔的办法,worst case 需要14次。

解法:
记n层s球的问题为Q(n,s),对应的最坏情况最优解为ba(n,s);

一些简单的结果:
(0) ba(m,2)>=ba(n,2) 如果m>n,trivial.
(1) ba(n,1)=n
当你只剩下一个球,为了能够检验出临界点,你只能逐层检验,最坏情况下所需的检验次数为n;
(2)ba(1,2)=1
(3)iterative: 假设你从k层扔球,有两种情形:

  1. 球破。那么临界层必然在1层到k-1层之间,剩下一球,由(1)得出,最坏情况最优所需的步数为: 1 + ba(k-1,1)=k;
  2. 球不破。问题变成n-k层两球的问题Q(n-k,2), 所以最坏情况最优所需步数是:1+ba(n-k,2);

综合1,2,最坏情况所需步数:ba(n,2) = max{k,1+ba(n-k,2)}
当k=1+ba(n-k,2)的时候,
ba(n,2)=ba(n-k,2)+1
结合(2),(3),由(2)迭代得知:
当n = 1+2+3+...+k
ba(n,2)=k
当k=13时, n=91;
ba(100,2)=max(9,1+ba(91,2))=14

所以100层,最坏情况最优策略的步数是14.

本文转载自:https://www.zhihu.com/question/31855632/answer/53640475

H
粉丝 4
博文 102
码字总数 12788
作品 0
广州
私信 提问
前端面试 - 算法篇(二分法)

前段时间换了份工作,也经历了很多面试,最终通常都会扑在算法上 虽说前端是所有程序员中,对于算法的要求最低的一个岗位,但算法依旧是进阶的必修课 于是决定记录一下与算法相关的面试题,以...

WiseWrong
2018/08/15
0
0
google经典算法面试题-鸡蛋问题

最近在 leetcode 上看到了一道题 Super Egg Drop, 刚好之前看到过一到很类似的题,就是 google 的一道经典的面试题。这里记录一下自己整个的解题思路。 google 原题 给你两个鸡蛋,它们有可能...

SHISME
02/03
0
0
两个玻璃球 测试极限高度

一道有趣的智力题目: 已知,玻璃球从某高楼落到地面会摔碎,楼的最大高度为100层,给你两个玻璃球,请你最快的测出,能使玻璃球摔碎的最低楼层... 两个玻璃球 思路1:蛮力法 如果用蛮力法, 从1楼,...

木子昭
2018/01/10
0
0
2018 年力扣高频算法面试题汇总-难题记录-鸡蛋掉落

题目描述: 你将获得 个鸡蛋,并可以使用一栋从 到 共有 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 ,满足 任何从高于 的楼层落下的鸡蛋...

chenjx85
03/13
0
0
动态规划法(六)鸡蛋掉落问题(一)(egg dropping problem)

  继续讲故事~~   这天,丁丁正走在路上,欣赏着路边迷人的城市风景,突然发现前面的大楼前围了一波吃瓜群众。他好奇地凑上前去,想一探究竟,看看到底发生了什么事情。   原来本市的一...

jclian91
2018/06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

NIO基于长度域的报文在Netty下的解码

1, 先复习一下粘包/拆包 1.1, 粘包/拆包的含义 TCP是个“流”协议, 并不了解上层业务数据的具体含义, 它会根据TCP缓冲区的实际情况进行包的划分,所以在业务上认为,一个完整的包可能会被TCP...

老菜鸟0217
今天
8
0
从零开始搭建spring-cloud(2) ----ribbon

在微服务架构中,业务都会被拆分成一个独立的服务,服务与服务的通讯是基于http restful的。Spring cloud有两种服务调用方式,一种是ribbon+restTemplate,另一种是feign。 其实我们已经在上...

Vincent-Duan
今天
17
0
get和post的区别?

doGet:路径传参。效率高,安全性差(get的传送数据量有限制,不能大于2Kb) doPOST:实体传参。效率低,安全性好 建议: 1、get方式的安全性较Post方式要差些,包含机密信息的话,建议用Pos...

花无谢
昨天
4
0
当谈论迭代器时,我谈些什么?

当谈论迭代器时,我谈些什么? 花下猫语:之前说过,我对于编程语言跟其它学科的融合非常感兴趣,但我还说漏了一点,就是我对于 Python 跟其它编程语言的对比学习,也很感兴趣。所以,我一直...

豌豆花下猫
昨天
14
0
10天学Python直接做项目,我做了这5件事

初学者如何尽快上手python? 市面上关于如何学python的资料很多,但是讲的都太复杂。 我就是很简单的几句话,从小白到开发工程师,我只做了五件事。 我觉得任何商业计划书如果不能用几句话讲...

Python派森
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部