李永乐老师:用递归拆解,汉诺塔游戏怎么玩?李永乐

作者: admin 分类: 科学 发布时间: 2021-08-30 10:07

        汉诺塔的问题其实可以进行拆解。在数学上呢我们称之为递归啊递归这个步骤的计算机上也会经常使用。什么意思呢?就是我希望啊把这64个金片都从A柱挪到C柱,但是我不知道怎么挪,对吧?没有关系,你可以这样干,你先把前面这63个金片通过某种方法,这63个金片你把它挪到B柱上来,这就是第一个步骤。啊,挪过来,然后你挪过来了之后,这个就变成啥样了呢?哎,这这就变成这样了啊,咱们看这个是A柱,这是B柱,这是C柱啊。有的时候三个金片。

        已经被你挪到了B柱上了,还有一个最大的金片是在A柱上,对吧?好,第二个步骤呢,你就是把最大的这个镜片再从A柱挪到C柱上,这就是第二个步骤。然后呢,第三个步骤第三个步骤怎么样啊,很简单,你只需要啊现在最大的镜片已经在右边了,对吧?中间还有63个小一点的金片。你把这就是三个金片,再通过某种方法哎,再挪到C柱上,这个步骤我们就完成了。所以我们就把一个复杂的步骤啊拆成了三个步骤。这三个步骤里面把63个金片如何挪到B上去,这又是一个比较复杂的问题,不过没有关系。假如你能完成这个步骤的话,你就可以按照这样的规矩,把64个镜片挪过去,对吧?那具体你怎么把这是三个金片融到B柱上,你可以这样先把62个镜片挪到C柱上,然后把第63个5到B柱上,再把这62个挪回来,对不对?你又可以把移动就是三个镜片的问题,主要成移动62个镜片的问题。那一栋62个金票怎么挪啊,你还可以按照这样的规律去讨论如何移动61个镜片。

        如此这般你就可以一直讨论到移动一个镜片这种最简单的问题了。房间说,假如把64个金片从A挪到C那么这个世界就毁灭了。那么到底需要移动多少次才能把这些芯片从未得到C呢?我们要计算一下,他一共需要。多少个步骤啊,一共需要多少个步骤?这个步骤怎么算啊?首先呢我们把N藏金片的步骤记作FN咱们想一想,fn应该有。多少,你看啊,如果你移动安防镜片的话,它包含两个移动N减一层镜片,还有一个是移动D原厂镜片,移动电源层镜片就是一部。这个呢这两个步骤呢他是FN减一步是不是啊,所以他等于两倍的FN减1,就是你需要移动两次N减一个镜片,然后还要加上。

        移动一个镜片对不对?所以这个式子我们就称之为递推式啊,有了递推式之后呢,我们就可以计算了。那比如说吧呃移动一个镜片需要多少步,那这个很简单。移动一个镜片就需要一步呗,对吧?移动两个镜片需要多少步?按照这个公式,2乘以1加1需要三步,对吧?移动三个金片需要多少步?2乘以3加1需要七步对吧?啊,就是这样我们来找一下规律啊,一等于什么,一等于2的1次方减13等于什么?三等于2的2次方减1 4减1对吧?七等于什么?等于2的3次方减一就是8减1。其实我们可以证明啊移动的这个步骤的个数可以计算最后的结果是移动N个镜片需要二的。N次方减一步,这是可以证明的啊,虽然我们找规律也找得到啊,但实际上我们是可以证明这个结论的。好,如果按照这个结论的话,我们这个汉诺塔玩具有十个有十层,那你要把它从A走到C需要多少步?至少需要1023部,非常多。那那么如果说你有64层,64层需要。多少部呢?按照这个来算有多少啊,2的64次方减一这么多步,这个步骤我们算出来是1.8乘10的19次方部。

        啊,这么多部,那应该是多少?那应该是1800亿亿部这么多步骤,对吧?1800亿亿部是什么概念呢?我们知道啊一年有365天,对吧?天24小时,每小时,那是3600秒。如果啊你一秒钟就移动一次,大概要把这64个金片全都移动完,需要多少年,需要5800亿年。5800亿年才能把它挪完,对吧?宇宙形成到现在也只有138亿年,对吧?太阳的寿命还剩50亿年。所以我们其实并不需要为这个凡天把世界毁灭这件事担忧,因为那应该是在宇宙毁灭之后的事儿。

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