一个有趣的问题

前言

  这个问题来自于看到的一个面试题,其中的解题过程比较有趣,有很多值得借鉴的地方,这里写出来作为记录。

题目

假设一栋100层的楼,两个完全一样的鸡蛋。存在某一层N,当鸡蛋从大于或等于N的楼层落下时会碎掉,当鸡蛋从小于N层落下时不会碎。问用两个鸡蛋找到N的最佳方案,以及此时最坏情况下需要实验几次。

  非完美的5分解决方案:

    解决方案一的灵感来自于已知两数的和,求两数的平方和的最小值。即假设两数和为25,求两数的平方和的最小值和最大值。

  这个解法比较简单,直接设一个数位x,则另一个数为(25-x),两数的平方和为 x2 + (x-25)2 = 2x2 - 50x + 625 = 2(x - 12.5)2 + n 可以只当x为12.5的时候取得最小值。当x为25的时候取得最大值。由此可以猜想是否可将100分成10等份,每一等份的层数正好为10层(跟前面的题目没有任何关联,只是一种第六感)。此时方案就是分别从第10层,20层,30层.. 丢第一个鸡蛋,直到第一个鸡蛋碎掉。然后从碎之前的一次丢位子的后面一层开始一直往上一层丢,直到找到刚好第二个蛋碎的位置。此时最坏情况下需要试18次。

  完美的解决方案:

  我们可以假设最坏的情况下需要丢x次鸡蛋。假设刚开始应该在第y层开始丢。此时第一次如果鸡蛋碎了,那么最坏的情况下找到N还需要丢y-1次。所以此时有 1 + y - 1 = x; 可以得到开始应该在第x层丢。假设第一次丢蛋没碎,那么第二次丢肯定要在x层之上丢,假设第二次丢的层数比第一次丢的高z层,同第一次一样假设第二次丢鸡蛋碎了, 那么最坏的情况下找到N需要的次数应该是: 1 + 1 + z - 1 =x;  可以得到 z = x - 1;也就是第二次应该比第一次丢的楼层高x-1层。依此类推知道最后一次就能断定是否是N。所以有下面等式:

  x + (x-1) + ... + 1 >= 100   

  解上面的不等式得 x = 14. 所以完美的解决方案丢的层数应该依次是: 14, 27, 39, 50, 59, 67, 84, 90, 95, 99, 100. 最坏的情况下需要测试14次。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程之美】最短路径

最短路径 任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次...

3466
来自专栏数据结构与算法

斯坦纳树小结

1060
来自专栏数据结构与算法

P3818 小A和uim之大逃离 II

题目背景 话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧 小a和uim再次来到雨林中探险。突然...

2867
来自专栏数据结构与算法

P1093 奖学金

题目描述 某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序...

2605
来自专栏小樱的经验随笔

hihoCoder #1142 : 三分求极值

#1142 : 三分·三分求极值 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 这一次我们就简单一点了,题目在此: ? 在直...

3319
来自专栏kalifaの日々

POJ3684(弹性碰撞)各种wrong answer踩坑

我踩过的坑全部都写在注释里面了,供大家参考。 #include <stdio.h> #include <algorithm> #include <math.h>...

2625
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

4119
来自专栏懒人开发

(4.7)James Stewart Calculus 5th Edition:Optimization Problems

根据下图,可以得到大体表达式: 已知 2x + y = 2400 求 A = xy = ? 的最大值

543
来自专栏机器人网

机器人A*寻路算法详解

A*(A-star)算法是一种静态网路中求解最短路径最有效的直接搜索算法。在电子游戏中最主要的应用是寻找地图上两点间的最佳路线。在机器人领域中,A*算法...

2544
来自专栏算法channel

除自身累乘算法题,又有创意解法了

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1)...

850

扫描关注云+社区