问题:假设玻璃球在k层楼及以上扔下时就会碎,以下不会碎,一共n层楼,你有两个玻璃球,怎么确定这个k是多少且使可能的最大次数最小。
分析:玻璃球的个数有限,所以无法使用二分法。所以考虑还是范围性搜索,第一个玻璃球用来确定范围,第二个玻璃球来确定结果。主要的问题就演变为怎么划分这个范围来使这个最大次数最小。任何不稳定的因素可能会使确认次数减小,可能也会让最大次数增大,所以这个值应该是一个稳定的值,那么假设这个可能的最大次数最小值为m,一共n层,且怎么扔最大次数都是m次,则可以这样,第一次在m楼扔,第二次在m*2-1楼扔,第三次在m*3-2层扔,这样子无论确定在哪个范围,它的最多次数都是一样的。
计算:那么,n - 1 <= m + (m-1) + (m-2) + ... + 1,这里n-1是因为最后一楼不用试了,如果前面一楼都没碎(第m次),那么就是最后一层楼会碎了。
class Program { static void Main(string[] args) { //输入层数,限制两个玻璃球 while (true) { string num = Console.ReadLine(); int inum = Int32.Parse( num ); Cal(inum); } } static void Cal(int num) { int res = 0; //搜索一个能覆盖所有楼层的扔法 int temp = (int)Math.Sqrt(num); while (res == 0) { if ((temp + 1) * temp >= (num-1) * 2) { res = temp; } temp++; } Console.WriteLine("结果为:" + res); //分别在第几层楼扔 for (int i = 0; i < res; i++) { int stand = res * (i + 1); //偏移保证最大次数一样 int offset = (i + 1) * i / 2; int floot = stand - offset; Console.Write(floot + " "); } Console.WriteLine(); } }
100层的结果为14次。