※ 引述《Domos (没事发发废文)》之铭言：
: ※ 引述《bleed1979 (十三)》之铭言：
: : 作者: bleed1979 (十三) 看板: Soft_Job
: : 标题: [讨论] Google面试问题
: : 时间: Sat Apr 12 02:07:46 2014
: : 问题：
: : 假设你有两颗蛋，然后有一栋100层楼高的大楼。
: : 而蛋的特性有的可能很坚固，坚固到从一百层楼跌下都没事，
: : 有的可能很脆弱，一楼就可以摔破。
: : 现在你只知道这这两颗蛋是完全相同的，
: : 你想要知道蛋最高从哪一层楼摔下来不会摔破。
: : 问题是：你要摔几次才能计算出来？
: : （如果你低于高度摔下蛋，蛋就没事，如果高于那个楼层，蛋就完蛋）
: : 在这过程你可以摔破蛋。
: 先假设蛋的硬度是uniform distribution
: 以100层来说，我们分成1~101级
: 1级表示1楼摔下来就破
: 100级表示100楼摔下来破
: 101级表示100楼摔下来也不破
: 所以我们有101个级距，uniform distributed
: 你可以挑战这个假设，例如使用normal distribution
: 或是增加级数，例如200个级距，但101级后就只能确定属于100层
: 但我们先讨论最简单的case
: 1. 在此假设下，我们从n楼丢下，蛋破的机率是 n/101
: 延伸此假设，在最高m楼的情况下，从n楼将蛋丢下
: 蛋破的机率是 n/(m+1)
: 2. 假设蛋在x楼破了，我们就被迫从1楼开始丢起
: 此时的期望值为 g(x) = (x*x + x - 2)/ 2x
: 我们先假设x是6 (从第6层丢下结果破了)
: 可能的情况有
: 1破 => 1次
: 2破 => 2次
: 3破 => 3次
: 4破 => 4次
: 5破 => 5次
: 5不破6破 => 5次
: 每种情况的机率是 1/6
: (1+2+3+4+5+5)/6 = 20/6 = g(6)
: 3. 假设蛋在x楼丢下不破
: 问题可以转化成 x+1楼 ~ m楼的问题
: 总共 m - x + 1 个级距 (包括m楼不破)
: 3. 综合(1) (2) (3)
: 在最高m楼的情况下，将二颗蛋从n楼丢下次数的问题
: 可以看成是 蛋破的机率 * 一颗蛋在最高n楼丢下次数的问题
: + 蛋不破的机率 * 二颗蛋从n+1楼~m楼丢下次数的问题
: f(n, m) = n/(m+1) * g(n) + (1-n/(m+1)) * f(m-n+1, k) + 1
: (记得加一，已经丢一次了)
: 新变量k表示第二次从k楼丢下
: f(n, 100) = n/(101) * g(n) + (1-n/101) * f(101-n, k) + 1
: 4. f'(m)表示f(n, m)值域的min (我们要求的)
: f'(1) = 1
: f'(2) = 5/3
: 照这样一路求到f'(100)
我的看法答案是:破掉的楼层/2 小数点有.5的话进位+1次
我的测试方法会是将第一颗蛋以双数位楼层来丢
当丢到破掉时候已另一颗蛋回推一楼层丢确定前一楼层的但是破还是不会破
举例:假设九楼破 2.4.6.8.1O十楼破的时候我就拿第二颗蛋在九楼丢
如果没破就是十楼,如果破了就是九楼
现在假设九楼有破
这样丢了六次就知道答案了:9/2=4.5进位+1=6
只要十楼有破就要回推一层楼验证所以要有两颗蛋
相对的是十楼破,只丢2.4.6.8.10楼拿第二颗蛋测试9楼是否会破
答案就是10/2+1次=6次
我的想法是比较保守因为是两颗蛋
如果有三颗蛋的话可以以三的倍数去测试
答案是以蛋颗数决定

题目蛋坚硬是无上限,所以没有一定的数字我才有这种想发

既然无上限,1~100楼大家各拿一颗不同时间往下丢。阿一次就知道了阿

人家有100楼 你只有10楼 应该会被淘汰

他只是举立鸡蛋的硬度可能很硬或很脆弱

没有说鸡蛋一定是一楼或一百楼会破掉吧!!

回2F我的无上限说硬度!!但他说鸡蛋只有两颗

三层一级距dominate 两层一级距, 三层 vs 四层则不一定

2科但也可以做三层一级距 四层一级距 仔细想一下吧