制作网站代码大全,免费红色ppt模板下载,网页界面设计和网页设计的差异表现在哪些方面,织梦网站换空间转载自#xff1a;http://blog.sina.com.cn/s/blog_6c813dbd0101bh98.html 两个软硬程度一样但未知的鸡蛋#xff0c;它们有可能都在一楼就摔碎#xff0c;也可能从一百层楼摔下来没事。 有座100层的建筑#xff0c;要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置…转载自http://blog.sina.com.cn/s/blog_6c813dbd0101bh98.html 两个软硬程度一样但未知的鸡蛋它们有可能都在一楼就摔碎也可能从一百层楼摔下来没事。 有座100层的建筑要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。 最少需要几次测试才能得到摔碎鸡蛋的楼层方案如何 对于这个问题如果从编程角度而言最简单的思路是用动态规划的思想来解决不过本文不将其从编程角度分析而是从数学角度对问题进行论述。 对这个问题 原始问题——【100层楼最少需要几次测试才能得到摔碎鸡蛋的楼层】 直接考虑不容易考虑但是如果将这个问题进行一种等价的转换这个问题将会变得非常容易解答。个人认为这个转换是解决这个问题的核心这个转换是 转换问题——【两个鸡蛋进行k次测试最多可以测试几层楼】 如果大家能想到将“原始问题”变为“转换问题”这个问题个人认为已经解决一半了转换后这个问题豁然开朗思路全开。 现在我们以“转换问题”为模板进行考虑有两个鸡蛋第一个鸡蛋如果破碎第二个鸡蛋就必须只能一层一层的测试了而且我们要求进行k次测试就将摔碎鸡蛋的楼层必须找到. 考虑第一次测试。第一次测试的时候第一个鸡蛋不能放置的楼层太高了否则如果第一个鸡蛋破碎第二个鸡蛋可能不能在k次测试后得到结果。但是也不能放置的矮了因为如果放置的矮了第一个鸡蛋破碎了还好说如果没破我们浪费了一次测试机会也不能说是完全浪费了不过至少是让效用没有最大化。所以第一次测试的时候必须让第一个鸡蛋放置的不高不矮。 不高不矮是多高高到如果第一个鸡蛋破碎后第二个鸡蛋刚好能完成k次测试得到结果这个目标。由此可知第一次测试所在的楼层高度为k如果第一次测试第一枚鸡蛋破碎则剩下k-1层楼一层一层的试k次一定能完成目标。 如果第一次测试第一枚鸡蛋没有破碎则我们现在只有k-1次测试机会了而且直到了k楼及其以下都是安全的了。我们消耗了一次测试机会但是一次就测试了k层楼。 然后只有k-1次机会了第二次测试我们可以在k层的基础上再增加k-1层了注意这个时候由于我们只有k-1次机会所以这次只能再增加k-1层以保证测试的时候第一枚鸡蛋破碎的情况下仍然能完成任务。 于是重复上述过程直到最后一次机会我们总共测试的楼层数为 然后再回到“原始问题”100层楼如果需要k次测试才能测试完成则必须有 则可以得到k≥14 也就是需要14次测试才能得到结果而且这个过程也将测试方案一并得出来就是第一次在14楼测试如果第一枚蛋碎则剩余13次机会13层未知楼层恰好第二次在141327楼测试如此。 如果不是100层而是N层需要的测试次数为k则有 然后这个问题这个时候还可以扩展了如果我们有三个鸡蛋有k次机会我们最大可以测试多少层楼 思路同前面一样第一次测试不能太高也能太矮必须恰到好处也就是第一枚鸡蛋如果破碎剩余k-1次机会能将剩余楼层给测试完。 由上面结论k-1次机会最多可以测试k(k-1)/2层楼所以第一次在k(k-1)/21层楼第一次如果第一枚鸡蛋不碎第二次在此基础上增加(k-1)(k-2)/21层楼于是三个鸡蛋k次机会总共测试楼层数为 至于四个鸡蛋五个鸡蛋以至于M个鸡蛋可以以此类推方法同上。此处原理讲通就不推导了。 题目变形 链接https://www.nowcoder.com/questionTerminal/287575fa30804a8b9085ca1747a69b6e来源牛客网 由于诺基亚手机不止可以当作手机使用还可以作为砖头防身人人的员工小丁想测一测它从多高才能摔破。借助人人公司所在的静安中心大楼共 27 层小丁准备从 1 层开始一层一层的将诺基亚手机扔下去直到摔破为止显而易见在最坏的情况下需要扔 27 次才能测出这个临界值假定顶层的高度一定可以摔破这部诺基亚手机小丁跟同事小李说了这个想法小李说他这也有一部同型号的诺基亚手机正好不用了给了小丁现在小丁手中有两部诺基亚手机。 1 请你帮忙计算一下在最坏情况下小丁最少需要扔几次才能测出这个临界值并且给出具体策略 PS 两部手机第一步手机选择第 k 层扔下去若是没有摔坏我们可以继续拿来往楼下摔若是摔坏了只有一部手机了还得按照之前一部手机的策略 2 现在我们发散一下假设给你 m 部诺基亚手机 n 层的高楼假定顶层的高度一定可以摔碎在最坏情况下至少需要扔多少次才能测出临界高度程序实现最好给出算法思想假定输入若干组 m 和 n 你的程序需要对每组 m 、 n 给出响应结果。其中 m 属于 [1,50] n 属于 [1,1000] 转载于:https://www.cnblogs.com/macyzhang/p/9829974.html
