Skip to content

Instantly share code, notes, and snippets.

View yanhsiah's full-sized avatar

Yan-Hsiang (Allen) Huang yanhsiah

View GitHub Profile
@yanhsiah
yanhsiah / gist:aa6664f8d0e2ad3b160725435b91c319
Created July 6, 2017 04:24 — forked from sing1ee/gist:5971946
Google面试题:扔鸡蛋问题

###Google面试题:扔鸡蛋问题

####原题描述 两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋

####方法分析 看到这个题目,最保险的方法就是一层一层试验,但这样只需要一个鸡蛋就可以了。我们现在有两个鸡蛋,完全可以用有更快的方法。

进一步呢?可能试验的方法是二分查找,例如,第一个鸡蛋再50层扔下,如果碎了,第二个鸡蛋从1-49逐层试验;如果没碎,第一个鸡蛋在75层扔下,如果碎了,第二个鸡蛋从51-74逐层试验…但是,这个方法,很容易悲剧,例如,当正好49层是可以安全落下的,需要尝试50次。比只有一个鸡蛋的情况,效果还要差。