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

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

        我们换一种方法啊,如果呀我让这个间隔还是啊1到100是吧?但是间隔不一样,我A阶段第一次扔的时候呢,我让他的间隔是N个。啊,然后如果他不碎,第二次扔的时候,我让这个间隔是N减一场,第三次扔的时候让这个间隔是N减2层,直到最后一次扔的时候呢,我让这个间隔是一层。也就是A美多扔一次,他的间隔就小了一点。这样一来呢,B所需要检验的次数就会少一A多,扔一次币就少了一次。这样一来总次数不就平均了一些吗?也许这种方法会更好啊,咱们思考一下,假如按照这种方法的话,我们算一算这个A应该得几,这个并不难,就是一加2加3一直加。

        加到N他的最后啊,我们都知道用高斯公式,它应该等于二分之N倍的N加一对吧。那么这个结果它必须要大于等于100啊。所以呢我们可以计算出这个n line,这个N呢要大于等于13.65啊,于是我们就取N等于14啊,N等于14,什么意思呢?就是说我们不考虑那种加一减一的临界情况来就是说。哎,一知道我们这么着,第一次啊,我让他跨越14个间隔,也就是在14层楼,学生14层楼如果碎了,就说明在1到14层之间。然后我用B级,但是1234一直到13,对吧?啊,如果第一个十四层没碎,我就让他加13层啊,要减一对吧。加时赛14加23 27层吧。如果27层5岁,我就再加12 39层。

        啊,不睡,我再加十一是五十层不遂,加16,十层不遂加9 69层,然后加8 77层,加7 84层。后加六是90层,加5 95层加4 99层啊,加1 100层,最后加不加不上翻了,为什么呢?因为我。这个实际上是4.65啊,你取了个14,自然而然最后呢他就会差了一点点。好,那么A呢他最多扔多少次?1 2 3 4 5 6 7 8 9 10 11 12。A最多是用12次。那如果第一次A就碎了,那我就需要用bg蛋去检验1到13层啊,他加上A中的一次,一共是剩了14次。

        如果A扔到27层的时候碎了,那我B就需要检验15层到26层。再加上A中的那两次,最后结果还是14次,对吧?那当然如果A扔到100层碎了,或者是100层还没碎的话,那你就不需要用,必须检验了。那最少的是12次。于是用这种方法呢,你仍巨大的次数是在12到14之间,最差的情况下是14次。所以这样一看哦,哎你看两个极端的情况下,就M不是19啊,最差的情况下我只需要扔14次。就能保证哎,你一定能够找到那个临界的楼层了,对吧?好,那这个面试题呢,其实我们就说完了。不过咱们想啊,如果仅仅是这样一个问题的话,其实意义并不大。你能够保证这种方法就是最好的吗?也不见得吧,而且这个人一定有两个大吗?不一定啊,他可能有三个段、四个段、五个段,六个蛋呢。

        那么如果我们的,但数量不是二的话,这个问题又该如何去解决呢?所以说啊这道题的精髓啊,其实在于其他的情况下,我们需要使用递归的思想来进行求解。其实递归思想我们在之前讲汉诺塔,还有拜占庭将军问题的时候都用到过。但是呢这个递归要比汉诺塔的那种递归啊稍微复杂一点啊,这个思想是这样的,我们把这个问题普遍化一点。就假如说这一层楼啊,他有T层,这个楼有梯子啊。然后我们呢一共有N个段,这个时候我们要找到在最不利的情况下,至少要扔多少次才能一定找到这个临界楼层。

        这个次数叫M那么M自然是T和N的一个函数。我就问这个函数值到底应该是多少,对吧?这个问题我们首先呢先从最简单的情况说起。啊,首先我们画一个表格,这个表格呢。啊,这个表格呢它的一列啊表示的是这个楼层竖T啊,tk是123或者一直到100是吧?然后呢淡的数目。啊,也可以是1234啊,或者是更多的更多的大,对吧?好了,现在呢有一些情况是比较好天的,比如说吧。如果你只有一个阶段的话,你有一层楼,你就至少得扔一次,对不对?你有两层楼,我们就得扔两次,有三层楼就得扔三次。

        所以这一列是非常好天的啊那么。如果是只有一层楼呢,只有一层楼的话,不管你有几个鸡蛋,都只需要扔一次,所以这一行也是很好填的。也就是说这两个边界其实都是非常非常好听的啊,当然后面还有啊,我就没有再往下写。啊,这两个边界很好听,关键是中间儿这一大堆,比如说有三层楼,两个鸡蛋,你至少要用几次,100层楼,两个鸡蛋,你要能几次5000层楼,三个子弹,你要扔几次。说这个问题就比较复杂,对吧?我们怎么去研究他呢?我们就要使用递归的思想了,这个思想是这样的,不管你有多少个鸡蛋啊,在扔的时候,你首先必须得选一层,然后扔第一个几代。对不对?好,那么第一个鸡蛋扔在哪儿呢?我们其实也并不清楚仍在哪儿。

        比如说这个楼层是一到T这么多层。第一个阶段你随便给我找个地方叫dk一层,你就扔吧。扔完了之后两种结果,一种是最一种是不遂。如果three就说明这个临界楼层一定的前面如果不碎,就说明临界楼层一定在后面,对不对?好,那么如果碎了,你还需要扔多少次鸡蛋才能确定这K个楼层里边哪一层是临界楼层呢?啊,我们可以说这个数啊其实就是M。没有K层楼N减一个单,为什么呢?因为你第一个阶段已经碎了,所以你的但只能变成N减一个了。而楼层呢原来是T层,现在你已经知道不在这后面只在前面。楼层变成K了,因此你会有这样的一个数据,对吧?好,这是你再往后还需要确定多少次再往下啊。

        如果他补税的话也是一样的。此时楼层啊就变成了这么多层。这个层数应该是T减配层,而淡的数目呢还是N个,对吧?于是我们可能还需要找这么多次才能确定具体是在哪一层。因为我们要找的是最不利的情况下需要蒸多少层?所以在这两种可能下,我们要把它取一个最大值取一个最大值。这两种可能中比较大的那个值就是我第一个阶段扔到K层的时候,我需要数的个数,对吧?最少需要数这么多次,但是同时你不要忘了,你开始还扔了一层,对不对?所以你还要把这个数字再加上一个一啊,就这两个数中较大那个数再加一。他就等于什么呢?它就等于当你第一个鸡蛋扔到第K层时,如果原来你有T层楼和N个鸡蛋,你需要扔寄到的歌手。但是你第一个这个看你怎么确定呢,对不对?我们。的一个方法就是隶属就是把K等12345677只刀T我全数一遍,我再画一个表格啊,这个表格是我们知道你这个K呀。他有很多种可能,你第一个阶段可以扔在第一层,你也可以用在第二层配上。第三层一直到你可以扔到最后一层,就是第七层。

        那么你在每扔一次,你都可以做这个运算,对不对?找到那种最不利的情况下你。需要扔鸡蛋的次数。mk对吧?mk啊,所以呢如果你第一个阶段扔到B一层了,就是M1,然后第二层就M2,然后第三层就是M3一直到如果第一个鸡蛋扔到。层了,那就是mt对不对?好,第一个阶段你是可以选的,你可以用在任何一层,所以我需要在这里面所有的值中,我选一个最什么的值。最小的值。所以最终的结果是M在T层楼N个鸡蛋的情况下,它等于最小值。M1M2一直到mta这样一来我们就把这个数据给确定了。有人说呢,那这个预算这么复杂,我到底怎么算,其实很简单啊。你看你在每一次计算的过程中啊。不管你从哪一层楼去争,你都要不然是把这个楼层数给减少了。

        T变成K了,或者TB或者T变成T减K了,要不然就是把鸡蛋的个数减少了或者没有减少,对不对?所以呢我们已经知道了楼层少和鸡蛋少的时候的情况,我们就可以一点一点算出楼层,多喝鸡蛋多的情况。也就是说我们可以先算啊两层楼。两个鸡蛋的时候,那三层楼两个鸡蛋的时候,把这一列都算完。然后呢利用这个数据我再去算。三个鸡蛋的时候,两层楼如何三层楼如何?我把这个呢也算完。然后再算四个阶段的时候,这个时候这个时候分别是多大,这样1.1点儿的递归,哎,就把这个东西给弄出来了,是吧?所以大家看这个思想其实还是挺复杂的,对吧?这是一个递归的这样的一个思想啊啊那么既然说到面试题了,咱们不妨出一个。简单一点的面试题给大家想一想啊,假如有一个圆形的小岛,然后呢有一条鳄鱼在圆形小岛周围呀,游艺鳄鱼的速度是人的四倍。而且鳄鱼那总是希望。找到一个离人最近的位置。而这个人呢最开始在这个小岛的正中心。

        那么我问啊这个人该如何运动才能够比鳄鱼先到达这个岛的边缘,从而逃离这个岛呢?如果有答案的话呢,不妨在下方留言啊。大家如果型号我的视频可以在youtube账号的老师订阅。我给你小铃铛。可以第一时间获得更新信息。

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