两个玻璃球问题

问题:假设玻璃球在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次。

blob.png


首页 我的博客
粤ICP备17103704号