作者bleed1979 (十三)
看板Prob_Solve
标题Fw: [讨论] Google面试问题
时间Sat Apr 12 02:08:15 2014
※ [本文转录自 Soft_Job 看板 #1JI2zrVk ]
作者: bleed1979 (十三) 看板: Soft_Job
标题: [讨论] Google面试问题
时间: Sat Apr 12 02:07:46 2014
问题：
假设你有两颗蛋，然後有一栋100层楼高的大楼。
而蛋的特性有的可能很坚固，坚固到从一百层楼跌下都没事，
有的可能很脆弱，一楼就可以摔破。
现在你只知道这这两颗蛋是完全相同的，
你想要知道蛋最高从哪一层楼摔下来不会摔破。
问题是：你要摔几次才能计算出来？
（如果你低於高度摔下蛋，蛋就没事，如果高於那个楼层，蛋就完蛋）
在这过程你可以摔破蛋。
--- 以下是完全不经大脑思考的 rough 策略，有雷 ---
http://ideone.com/B7E85H
策略是：
当我还有两次机会时，我使用二分法。
当我只剩一次机会时，选择已经安全的楼层 + 1。
附上此策略的解答 楼层 => 次数
1=>3
2=>4
3=>5
4=>6
5=>7
6=>8
7=>9
8=>10
9=>11
10=>12
11=>13
12=>14
13=>15
14=>16
15=>17
16=>18
17=>19
18=>20
19=>21
20=>22
21=>23
22=>24
23=>25
24=>26
25=>27
26=>28
27=>29
28=>30
29=>31
30=>32
31=>33
32=>34
33=>35
34=>36
35=>37
36=>38
37=>39
38=>40
39=>41
40=>42
41=>43
42=>44
43=>45
44=>46
45=>47
46=>48
47=>49
48=>50
49=>50
50=>3
51=>4
52=>5
53=>6
54=>7
55=>8
56=>9
57=>10
58=>11
59=>12
60=>13
61=>14
62=>15
63=>16
64=>17
65=>18
66=>19
67=>20
68=>21
69=>22
70=>23
71=>24
72=>25
73=>26
74=>26
75=>4
76=>5
77=>6
78=>7
79=>8
80=>9
81=>10
82=>11
83=>12
84=>13
85=>14
86=>15
87=>15
88=>5
89=>6
90=>7
91=>8
92=>9
93=>9
94=>6
95=>7
96=>7
97=>7
98=>7
99=>7
100=>7
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.135.203.156
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1397239669.A.7EE.html
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: bleed1979 (220.135.203.156), 04/12/2014 02:08:15
1F：推 LPH66:其实有比二分法更好的答案...提示: 那个 50 其实很容易变小 04/12 06:33
2F：→ LPH66:沿着这个变小的思路就会得到最佳解了 04/12 06:35
3F：→ testPtt:期望值应该都是51次 04/12 09:22
4F：→ testPtt:想想开方根好像比较正确:19次 04/12 09:44
5F：→ tjjh89017:我的策略跟楼上一样@@ 但是听说有更小的@_@ 04/12 12:27
6F：推 dozyclover:14次 f(0)=0 f(n)=max(j-1,f(i-j))+1, 1<=j<=n 04/12 14:36
7F：推 dozyclover:f(n)=min(max(j-1,f(i-j))+1), 1<=j<=n 这样才对QQ 04/12 15:27
8F：→ dozyclover: n 一直打错 04/12 19:04
9F：推 guest2:10次 04/13 00:16
10F：推 guest2:破1颗後step可以是2 04/13 00:22
11F：推 guest2:不对 我错了= = 04/13 00:31
12F：推 FRAXIS:看wikipedia的dynamic programming里面就有解答了.. 04/13 07:41
13F：推 DJWS:想请教有没有O(n)的方法，甚至是低於O(n)的方法？ 04/20 18:12