Re: [討論] Google面試問題
看了大家腦力激盪
我也來拋磚引玉，來將先前的結果證明看看是不是唯一解。
首先，先定義幾件東西。
Define 2ggs test success means we find the smallest
floor make egg broken
Otherwise, failure if there are floors which are not
being tested when two eggs are broken.
Let n be a positive integer.
Define f(n) = the smallest positive number such that
2 eggs test success without fail for all k without more restriction , k <= n.
for each n , define C_n := the smallest integer
1 + 2 + 3 + ... + C_n >= n
and let k be the smallest positive integer such that
C_n + (C_n-1) + ... + (k+1) + k <= n and
g = n - C_n + (C_n-1) + ... + (k+1) + k
for each n , we can define a partition P_n for {1,2,3,....,n}
P_n = { {1 ,2 , ... , C_n} , { C_n + 1 , ... , 2* C_n -1 },
.... , { n-g-k+1 ,..,n-g} { n-g-1 .. ,n-1, n } }
where |{n-g , ... , n-1, n}| <= k-1
Follow P_n , we can define f2(n) = the smallest positive number
such that 2 eggs test success without fail for all k under the partition
P_n;
Then we can prove
f2(k) = C_k , for each k <= n;
Now we want prove f(n) = f2(n) for each n , a postive integer
we know
1. f and f2 are increasing.
2. f(k) <= f2(k) , for each k.
(since f2(k) just a special case for f , maybe a better partition to get
a more minimum value)
let n_0 be the smallest positive number such
that f(n_0) != f2(n_0);
C_(n_0-1) = f2(n_0-1) = f(n_0 - 1)
< f(n_0) <= f2(n_0) = C_(n_0)
C_(n_0-1) < f(n_0) <= C_(n_0) => f(n_0) == C_(n_0)
f(k)=f2(k) for all k.
Done
※ 引述《leoace (leoace)》之銘言：
: ※ 引述《changyuheng (張昱珩)》之銘言：
: : 解不等式可知 n >= 14 皆成立，故最佳解為 14。
: 補充說明:
: 從14樓開始測試，每次加14樓，如果有蛋破掉的話，則再以區間中的最低偶數樓層開始丟
: ，如果偶數n樓層爆掉，就是n-1層
: 例如:
: --(蛋爆)->
: 1) 14 ---------> 2, 4, 6, 8, 10, 12 -->最差7次
: 2) 28 --------->16, 18, 20, 22, 24, 26 -->最差8次
: 3) 42 --------->30, 32, 34, 36, 38, 40 -->最差9次
: 4) 56 --------->44, 46, 48, 50, 52, 54 -->最差10次
: 5) 70 --------->58, 60, 62, 64, 66, 68 -->最差11次
: 6) 84 --------->72, 74, 76, 78, 80, 82 -->最差12次
: 7) 98 --------->86, 88, 90, 92, 94, 96 -->最差13次
: 8) 100---------->最差14次
: 假如第9樓會爆，順序為: 14, 2, 4, 6, 8, 10(爆)-->9樓
: 假如第23樓會爆，順序為: 14, 28, 16, 18, 20, 22, 24(爆)-->23樓
: 以此類推
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.98.238
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397925072.A.CDD.html
推
04/20 08:52, , 1F
04/20 08:52, 1F
→
04/20 18:20, , 2F
04/20 18:20, 2F
→
04/20 18:21, , 3F
04/20 18:21, 3F
→
04/20 18:21, , 4F
04/20 18:21, 4F
→
04/20 18:24, , 5F
04/20 18:24, 5F
推
04/20 18:41, , 6F
04/20 18:41, 6F
→
04/20 18:42, , 7F
04/20 18:42, 7F
→
04/20 18:43, , 8F
04/20 18:43, 8F
→
04/20 19:06, , 9F
04/20 19:06, 9F
→
04/20 19:08, , 10F
04/20 19:08, 10F
→
04/23 02:28, , 11F
04/23 02:28, 11F
討論串 (同標題文章)