一个有趣的问题

前言

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

题目

假设一栋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 条评论
登录 后参与评论

相关文章

来自专栏AIUAI

Caffe2 - (三十三) Detectron 之 roi_data - data loader

3814
来自专栏社区的朋友们

深度学习入门实战(二):用TensorFlow训练线性回归

上一篇文章我们介绍了 MxNet 的安装,但 MxNet 有个缺点,那就是文档不太全,用起来可能是要看源代码才能理解某个方法的含义,所以今天我们就介绍一下 Te...

6.1K1
来自专栏简书专栏

基于tensorflow+RNN的MNIST数据集手写数字分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 RNN是recurrent neural network的简...

1243
来自专栏大数据挖掘DT机器学习

Tensorflow深度学习LSTM实现的小说撰写预测damo

最近,在研究深度学习方面的知识,结合Tensorflow,完成了基于lstm的小说预测程序demo。 lstm是改进的RNN,具有长期记忆功能,相对于RNN,增...

3985
来自专栏IT派

【深度学习入门系列】TensorFlow训练线性回归

作者:董超 来源:腾讯云技术社区「腾云阁」 上一篇文章我们介绍了 MxNet 的安装,但 MxNet 有个缺点,那就是文档不太全,用起来可能是要看源代码才能理...

3283
来自专栏racaljk

Leetcode 931. Minimum falling path sum 最小下降路径和(动态规划)

所谓下降路径是指,从一行到下一行,只能选择间距不超过1的列(也就是说第一行的第一列,只能选择第二行的第一列和第二列;第二行的第二列,只能选择第三行的第一列第二列...

843
来自专栏Deep Learning 笔记

CNN+MNIST+INPUT_DATA数字识别

TALK IS CHEAP,SHOW ME THE CODE,先从MNIST数据集下载脚本Input_data开始

2863
来自专栏Jack-Cui

Caffe学习笔记(四):使用pycaffe生成train.prototxt、test.prototxt文件

Python版本: Python2.7 运行平台: Ubuntu14.04 一、前言     了解到上一篇笔记的内容,就可以尝试自己编写python程序生...

7426
来自专栏MelonTeam专栏

深度学习入门实战(二)

导语:上一篇文章我们介绍了MxNet的安装,但MxNet有个缺点,那就是文档不太全,用起来可能是要看源代码才能理解某个方法的含义,所以今天我们就介绍一下Te...

23410
来自专栏简书专栏

基于tensorflow的MNIST数据集手写数字分类预测

MNIST是Mixed National Institue of Standards and Technology database的简称,中文叫做美国国家标准...

1633

扫码关注云+社区