对100层楼两个玻璃球测试问题的理解

对100层楼两个玻璃球测试问题的理解问题 有一座 100 层高的大楼和两个玻璃球 小球 A 和小球 B 现在我们要通过在楼上扔玻璃球的方式来测试玻璃球的坚硬程度 已知从这座楼的某一层开始 往下扔玻璃球 玻璃球会碎 问最少需要多少次尝试 才能找到最低在哪层会摔碎 分析题干 问的是

大家好,我是讯享网,很高兴认识大家。

        问题:有一座100层高的大楼和两个玻璃球(小球A和小球B),现在我们要通过在楼上扔玻璃球的方式来测试玻璃球的坚硬程度,已知从这座楼的某一层开始,往下扔玻璃球,玻璃球会碎,问最少需要多少次尝试,才能找到最低在哪层会摔碎?

        分析题干:问的是 最少需要多少次尝试。设需要x次,最低层为m层,即给我 x 次扔玻璃球的机会,我就能找到 m的值。 在下述的方案中,我们只考虑最坏情况,只要我们在最坏的情况下,使用 x 次的机会,找到了m的值,那么在其他的情况下找到m值所需要的次数肯定小于等于 x 。

        方案1:从低到高一层一层试,最坏情况(第100层碎了):试100次。 答案是 100次。

        方案2:二分法,最坏的情况(50层碎了1个,然后从低到高的测试,49没碎,):试50次,答案是50次。

        方案3:等距间隔法,设最低层为m层,设等距间隔为k 层,设第一个球在第n层测试时碎了,设测试了 y 次才得到了m的值。从低到高每隔k层,扔一下第一个小球,直到碎了为止,该层为第 n 层,由于在在n-k层时没碎,那么我们可以推测出① n-k+1<=m<=n ;②之前测试了n/k次。然后我们拿第二个小球从n-k+1层开始试,最坏的情况是再尝试 k-1 次(n-(n-k)-1)(即第二个小球测试了k-1次也没有碎,这意味着 n=m),加上之前测试的n/k次,总共是n/k+k-1次。由此,我们可以得到一个函数 y=n/k+k-1, 在一座100层的大楼里, 1<=n<=100,2<=k<=49。此时,测试次数取决于n和k,显然 n 与 y是成正比的,所以最坏的情况是当n=100时,所以 y=100/k +k-1,其函数图如下,所以当k=10时,y最小,只需要19次,就能找到m的值。


讯享网

        方案4:最优间隔法,思路:我们用小球A来初步确定最低楼层的取值范围,然后用小球B来确定最低楼层的具体值。

        设最低楼层为m层,设A球第一次在k层尝试。

        小球A的第一次在k层尝试,如果碎了那么小球B最多尝试k-1次,就能知道m的值(最多尝试了k次);小球A:1次,小球B:最多k-1次。我们总共测试了 k 层;

        如果第一次没碎,小球A第二次在k+k-1(2k-1)层测试,如果碎了,那么小球B最多尝试k-2次(依次在k+1,k+2,k+3,...,2k-2层测试),就能知道m的值(最多尝试了k次)。小球A:2次,小球B:最多k-2次,我们总共测试了2k-1层(k+k-1);

        如果第二次没碎,小球A第三次在k+k-1+k-2(3k-3)层测试,如果碎了,那么小球B最多尝试k-3次(依次在2k,2k+1,2k+2,...,3k-4层测试),就能知道m的值(最多尝试了k次)。小球A:3次,小球B:最多k-3次,我们总共测试了3k-3层(k+k-1+k-2);

        依次类推 x<=k,小球A:x次,小球B:最多k-x次,我们总共测试了(k+k-1+k-2+...+k-x+1)层;

        最后一次,小球A:k次,小球B:0次;我们总共测试了(k+k-1+k-2+k-3+...+1)=k*(k+1)/2层楼。

        综上所述,在方案4里,我只需要k次机会和两个小球就能知道k*(k+1)/2层高的大楼里从每层楼里扔 小球的测试结果。

        现在是已知100 层的高楼里,从某一层开始扔小球,一定会碎,所以我们只需要1-99层的测试结果即可,所以最终的 方程式是:99<=k*(k+1)/2, 求出  14<=k。

        答:至少需要14次尝试,才能找到最低在哪层会摔碎。

小讯
上一篇 2025-02-06 12:33
下一篇 2025-01-07 09:59

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/132172.html