game面试题

You　have　been　given　2　special,　extremely　rugged　Xboxes.　You　are　in　an　office　building　that　is　100　stories　high.　Using　the　fewest　possible　number　of　drops　from　windows　in　your　office　building,　determine　the　highest　floor　you　can　drop　an　Xbox　from　and　have　it　survive:　for　example,　they　might　be　able　to　take　the　drop　from　the　30th　floor,　but　not　the　31st.　You　can　break　both　Xboxes　in　your　search.　State　the　worst　case　number　of　drops　needed　and　explain　how　you　arrived　at　that　answer.

你在一幢100层的办公楼里上班,现在给你两台xbox(已经特意捆绑包扎好),要求你用尽可能少的试摔次数来判断xbox摔不坏的最高楼层层数。比方说,从30层丢下来没问题,但从31层丢下来就不保了。在摸索过程中,允许把两台xbox都砸烂。

详细解释你的答案和思路

 

问题是这样的,当我们每隔一层楼摔一次的话,那么要摔100　/　1　=　100次
当我们每隔两层楼摔一次的话,需要摔100　/　2　=　50次
当我们每隔三层楼摔一次的话,则需要100　/　3　+　1　=　34次
当我们每隔四层楼摔一次的话,则需要100　/　4　+　2　=　27次
由此可以得出公式:当我们每隔N层摔一次的话,需要100　/　n　+　(n　-　2)
这样问题就简单多了,变成了求　(100　+　n　*　n　-　2　*　n)　/　n的最小值的问题。
得出n　=　10,答案就是每10层楼一摔,摔坏了以后从没坏的那一层开始一层层摔起。。
最坏的时间是要用到100　/　10　+　8　=　18次