1 + 2 + ... + N > 100
其实不是简单的一题 .. 我第一次被问30分钟内没解出来
金融业蛮常问这题的~
※ 引述《cdmdrdtw (昌仔)》之铭言：
: ※ 引述《Domos (没事发发废文)》之铭言：
: : 先假设蛋的硬度是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次
: 我的想法是比较保守因为是两颗蛋
: 如果有三颗蛋的话可以以三的倍数去测试
: 答案是以蛋颗数决定