本文主要是介绍C语言丢鸡蛋100层,100层楼扔两个鸡蛋的问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。
有座100层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。
思考:给了我们2个鸡蛋,意思就很明显,有1个鸡蛋起到关键作用,它可以被打破,以告诉我们临界楼层大致在什么位置。
初探:看到这个题,首先想到的是二分搜索法,先从50楼摔下,分两种情况:
1.如果没碎:再从75楼(就是50+25=75)再次摔下。
2.如果碎了:第二个鸡蛋从25楼摔下……
如此去找,但是我们可以发现里面的漏洞,如果第二个鸡蛋从25楼摔下也碎了怎么办?就找不到可以摔碎鸡蛋的最低楼层了!
二分搜索失败,但我们从中找到一点启示:就是当我们找到一个鸡蛋可以摔碎的楼层区间时,不能从中再截取一段楼层再去扔,必须用顺序轮询法从低层到高层一层一层去找出那个楼层。(就像上面说的,如果鸡蛋从50楼摔下,碎了,那么第二个鸡蛋必须从一楼开始扔:一楼、二楼、三楼。。。。。。直到找出可以摔碎鸡蛋的楼层)。
所以思路出来了:开始可以分段去找出可以摔碎鸡蛋的楼层段(我们称之“高楼层分段找的次数”),然后再去轮询这个分界点以下的楼层段的每一层楼,看是在哪一层楼可以把鸡蛋摔碎(我们称之“低楼层轮询的次数”)。
最少需要几次测试,才能得到摔碎鸡蛋的楼层?方案如何?
=================================================
对于这个问题,如果从编程角度而言,最简单的思路是用动态规划的思想来解决,不过本文不将其从编程角度分析,而是从数学角度对问题进行论述。
================================================
对这个问题,原始问题——【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层未知楼层,恰好,第二次在14+13=27楼测试,如此。
如果不是100层,而是N层,需要的测试次数为k,则有
=========================================================
然后,这个问题这个时候还可以扩展了,如果我们有三个鸡蛋,有k次机会,我们最大可以测试多少层楼?
思路同前面一样,第一次测试,不能太高也能太矮,必须恰到好处,也就是第一枚鸡蛋如果破碎,剩余k-1次机会能将剩余楼层给测试完。
由上面结论,k-1次机会最多可以测试k(k-1)/2层楼,所以第一次在k(k-1)/2+1层楼,第一次如果第一枚鸡蛋不碎,第二次在此基础上增加(k-1)(k-2)/2+1层楼,于是,三个鸡蛋k次机会总共测试楼层数为
至于四个鸡蛋,五个鸡蛋,以至于M个鸡蛋,可以以此类推,方法同上。此处原理讲通,就不推导了
http://blog.sina.com.cn/s/blog_3fe961ae0101llmf.html
这篇关于C语言丢鸡蛋100层,100层楼扔两个鸡蛋的问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!