有一幢100层高的大楼,给你两个完全相同的玻璃围棋子。
假设从某一层开始,丢下玻璃棋子就会破碎。那么怎么利用手中的两颗棋子,
用一种什么样的最优策略,知道这个临界的层高呢?
今天偶尔看到这道题目,花了点时间想了想,现在我把题目的100改为未知,为变量H,再求最优化。我的思路是每n层扔一次,这样情况就是 (H+n-1)/n+(n-1)次数
设H无穷大 变化 H/n+n
极限可求n的平方为H时候 最优化。
代码很简单,就不贴了。
但是当H有指定值的时候,比如100,这个算法可能就不是最优化的。
但是这个算法比较均匀。
当H给定时候有个更优算法:
假设第一次扔n楼,第二次扔n-1,n-2,n-3,……3,2,1
次数为n次
这个是暂时的最优算法
Trackback: http://tb.donews.net/TrackBack.aspx?PostId=1230092