复工复产找工作?先来看看这道面试题:双蛋问题(上)

作者: admin 分类: 科学 发布时间: 2021-09-13 17:11

        各位同学大家好,我是李永乐老师,有一个小朋友跟我说呀,他年底的时候刚刚把工作辞了,准备过完年找工作,结果就在在疫情。那现在呢复工复产的节奏越来越近了。就开始着手准备找工作的事儿了。他最近呢发现了一个面试题,据说呢是微软还是google的一个面试题,挺有意思的。想让我讲一讲。

        那今天呢咱们就一起来讨论一下这个面试题。我们称之为双旦问题。鸡蛋的蛋。双档问题呢实际上是一个计算机的问题啊,这个问题是这样描述的。说有一个大楼,这个大楼呢非常高,这大楼一共有100层那么高啊。这100层楼啊,1234一直到100层,然后有一个鸡蛋,这个鸡蛋特别神勇啊,他在第一楼层往下扔的时候,到地上都不会碎在高楼层往上往下扔的时候到地面上才会碎。而中间有一个临界的楼层,这个临界的楼层以下,不管你在临近楼层以下扔多少次,鸡蛋都是不碎的啊,都是不碎的。

        然后呢如果你超过了这个临界楼层往下扔,哎,这回鸡蛋才岁。废了之后呢,就不能再反复用了。现在我就问你啊,这个人啊,如果要是一共有N个蛋,可以用来做检测啊。注意如果这个但没有岁就还可以接着扔啊。如果这个蛋碎了,就不能再用。了啊,如果有N个赞的话,那么他最少要扔多少次啊扔多少次啊,这个次数叫M。

        才能找出这个临界的楼层啊,找出这个临界的楼层,就是这个楼层以上啊就都会碎,这个楼层以下就都不睡。这个呢就是扔鸡蛋的问题。那么这个扔鸡蛋的问题,你有多少个鸡蛋会影响到这个问题的答案,对吧?首先呢我们先来分析最简单的情况。如果这个人呢他只有一个代。啊,如果只有一个,但也就是N等于一。那我就问你最少得扔多少次才能确定出临界楼层。大家注意这个确定出临界楼层的意思是你即使是最坏的情况下,也能够通过扔这么多。吃鸡蛋就确定出这个楼层,对吧?啊,比如说吧你只有一个鸡蛋的话,你不可能上来就从50层开始挣。

        那一旦要是岁了,你只能知道这个临界楼层在1到50之间,但是你却不知道是哪一个。对吧,所以如果你只有一个阶段的话,没有别的办法,你只能是先在第一层中啊,如果碎了,那就是一层。如果不碎,就从第二层上,第二层岁呢就是二层不遂,他就再同第三层中。一个一个的往上市,这样一来你没有别的好方法了,对吧?所以一层一层去试,最差的情况是到100层碎了,或者到100层也不碎。因此你。

        啊,最差的情况下要扔100次啊,那这个就是用的次数比较多的,因为它鸡蛋太少了啊,他只有一个蛋好了。那么假如说这个人的但比较多啊,他有无限多个蛋。他有无限的,但那这回需要扔多少次呢?这时候啊我们就要采用计算机里边一种常用的方法了,那就是二分法是吧?二分法呢也是牛顿最早提出来的。但当时啊。是用来去找一个方程的根的啊,这个研究型来也很容易啊,就是说我们把1到100是吧?1到100层,我们画在一个数轴上。然后呢我们第一个阶段啊,我在50层的地方,让我在50层的地方上。

        如果这个鸡蛋要是岁了,那就说明你你一定是在啊临界楼层,一定是在1到50之间,对吧?如果50层这个鸡蛋他不睡,那就说明啊临界楼层应该是在50到100层之间,这就是第一个阶段的扔法。那么如果说你确定了他在1到50之间岁的那于是呢我们可以第二个阶段在。25层的地方扔,如果碎了,说明啊临界楼层在这儿,如果不碎,说明临界楼层在这儿。这样一来我每扔一个鸡蛋都可以把这个间隔除以2,对不对啊,所以叫二分法嘛。那我们知道啊,你除了几次二之后呢,最后如果间隔小于一了,就不用再去世了,对不对?因此啊如果我们想把它确定出来是哪一个的话,我们就需要扔的次数二的M次方。得大于等于100,最后呢M就大于等于啊log以2为底,100的对数,我们试一试也能试出来啊,这个数应该是6.64啊。

        6.64呢我们就娶妻好了。所以呢这个时候你。需要扔。其次啊,在最坏的情况下,你也需要扔。其次啊,好,这是这个人有无限子弹的时候是这个样子的。那么这个面试题一般是这么问的,如果这个人有两个大的话,那么他要扔多少次才能保证一定。把这个临界楼层找出来,所以就叫双断问题是吧?所以他如果有两个蛋啊,那么这个时候怎么样呢?叫N等于二啊,我们来看一下。

        这个情况我们先想这样一个方法啊,如果第一个在某些原因下他碎了,那我就只剩下一个大了。剩下一个蛋之后,我只能一个尝一尝一场一场,这样往上试了就回到第一种情况了,对吧?啊,所以我第一个段的作用应该是用来把这个范围尽量的缩小。然后用第二个蛋呢去一个一个的去试,只能是这样吧。好,那我们还是把这个图啊。出来啊,说有这个1到100层对不对?然后我有两个大A和B啊,我们向ra这个鸡蛋呢怎么做呢?我先让A这个鸡蛋呢第一次扔,我让他在十层楼往下扔。他如果要是碎了,就说明啊临界楼层在1到10之间,对吧?如果不睡,我就让他在20层的地方上啊,如果碎了在这儿,如果不碎,就在30层的地方上。也就是说呀,我可以让A这个蛋,他在12时30一直到100啊,这些个楼层上,A呢最多可以扔十次。好,如果我把A这个确定了,比如说啊在十层的时候没遂,在二层的时候碎了,那就说明您这楼层在这儿。然后我用第二个鸡蛋再去试11、12、13、14、15、16一直到19,对不对?所以B这个鸡蛋他仍的楼层就是X1X2X3一直到X9。好,通过这样的方法,我就一定能够把这个楼层给试出来,对吧?临界楼层给试出来,咱们想一想啊。

        最多会扔多少次呢?假如说A在第十层老的地方就碎了,那么B最多是九次,总共呢就是扔十次就能试出来了,对吧?好,如果A呀在100层的时候才遂了。那么A怎么了十次,然后我必再去试,结果事到最后一个财税,那就说明你在99层或者100层岁了,此时我们就要扔19次,对不对?所以最坏的情况下我们需要扔。19次好,69次,咱们思考一下啊,还有没有一种方法能够比这个方法更好呢?这个方法啊它有的时候是十次,有的时候是19次。在10到19之间,他不平均原因是什么呢?原因是因为吧ae他确定的间隔是等间隔的啊,等间隔的就造成了B这个鸡蛋去世的时候,每一次用的次数最多都是一样的,对吧?但是呢如果这个临界楼层靠后的话,A人的次数就多了,是不是?所以我们在思考啊,能不能让这个间隔变得不等我们让间隔变得不等啊。就是说让A美多扔一次B的这个间隔就缩小一点,A扔一次,壁纸间隔缩小一点。这样一来让他总次数能够平均一下。哎,也许这种情况会更好,对不对?好,咱们再来看一个方法啊。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!