题目:
现代工程师为了测试出:人从几楼掉下去(楼层为n层),就会摔死。然后现在给出两个试用品(代替人), |
摔死之后的试用品将失效。 |
问题:
最少需要测试几次,才能得到摔碎鸡蛋的楼层?方案是什么?? |
思路分析:
对于这个问题,如果从编程的角度而言,最简单的思路就是用动态规划的思路来解决。但是我们这次将是从数学角度对问题进行分析。
------------------------------------------
对于这个问题,原始问题---【例如楼层数为100(假设n=100),最少需要几次(假设为K次)测试,才能得到摔鸡蛋的楼层】,直接考虑不容易想到,但是如果我们将这个问题进行一种等价的转换,这个问题将会变的非常容易。
这个转换是解决这个问题的核心,这个转换是:
转换问题——【1.两个测试品,进行k次测试,最多可以测试几层楼?2.如何发挥这两个鸡蛋的最大效用性】
现在我们以“转换问题”为模板进行考虑,我们假设两个测试品为鸡蛋,(最基本思想1图)第一个鸡蛋如果破碎,第二个鸡蛋就必须只能一层一层的测试了,而且,我们要求进行k次测试就将摔碎鸡蛋的楼层必须找到。
--------------------------------------------
第一次测试:
①第一个鸡蛋不能放置的楼层太高了,否则,如果第一个鸡蛋破碎(只剩下一个鸡蛋),那么第二个鸡蛋只能从最底层一层层的向上测试,这样才能保证第二个鸡蛋一定会找到这个临界楼层(但是效用性太低了),同时这样可能导致第二个鸡蛋可能不再k次测试后得到结果。
②但是也不能放置的楼层太矮了,因为太矮了,如果第一个鸡蛋碎了那还好说;
如果没有破,我们浪费了一次测试机会(虽然还可以继续使用),也不是浪费了就是效用性降低了,没有达到最大化效用性。所以第一次鸡蛋最好放置在不高不低的位置。
那么不高不低,到底是多高?
高到如果第一个鸡蛋破碎之后第二个鸡蛋刚好能完成第K次测试得到结果这个目标。
由此可知,第一次测试所在的楼层高度为K:
①如果第一次测试第一枚鸡蛋破碎,则剩下K-1层楼,那么从第一层楼逐一尝试,一定可以完成目标。
②如果第一次测试第一枚鸡蛋没有破碎,那么我们现在只有K-1次测试机会了,而且直到了k楼及其以下都是安全的了。我们消耗了一次测试机会。但是一次测试了K层楼。
然后只有k-1次机会了,第二测试,我们可以在K层的基础上再增加K-1层,注意这个时候由于我们只有K-1次机会,所以这次只能增加K-1,以保证测试的时候第一枚鸡蛋破碎的情况下仍然能完成任务。
于是,重复上述过程,知道最后一次机会,我们总共测试的楼层数为:
K + (K - 1) + (K - 2 ) + ..............+1 = K( K + 1 )/2
然后我们再回到原始问题,100层楼,如果需要K次测试才能测试完成,则必须有
K( K + 1)/2 >= 100
于是我们可以得到,K >= 14,也就是需要14次测试才能得到结果,而且这个过程也将测试方案一并给出了,就是第一次在14楼测试,如果第一枚鸡蛋碎了,那么剩余13次机会,13层楼未知楼层,恰好,第二次在14 + 13 = 27 楼测试。
那么我们回到我们原来的问题了
如果不是100层而是N层,需要测试的测试为K!
同上面的数学公式可知:
更多推荐
C++ ——趣味代码 三
发布评论