米游社 · 原神

求解汉诺塔通项公式

来自版块: 酒馆
5
30
0
文章发表:7小时前

由图可知,游戏通关的要求是将所有的齿轮从第一根柱子移动到第三根柱子,且上一层的齿轮必须比下一层的齿轮更小。

设移动的步数y=f(n)

当n=1时,只需要把齿轮从第一根柱子直接移动到第三根柱子即可,仅需1步,f(1)=1。

当n=2时,需要将第一个齿轮移动到第二根柱子上,再将第二个齿轮移动到第三根柱子,再将第一个齿轮从第二根柱子移动到第三根柱子,共需3步,f(2)=f(1)*2+1=3。

当n=3时,需要将第一个齿轮和第二个齿轮移动到第二根柱子上,再将第三个齿轮移动到第三个柱子上,最后将第一个和第二个齿轮移动到第三根柱子上,f(3)=f(2)*2+1=7。

……

不难得出,要想将n个齿轮全部从第一根齿轮移动到第三根齿轮上,需要先将前n-1个齿轮全部移动到第二根柱子上,再将第n个齿轮移动至第三根柱子上,最后再将第二根柱子上所有的n-1个齿轮全部移动到第三根柱子上,即f(n)=f(n-1)*2+1。

根据f(1)=1,可以求得最少移动次数的通项公式f(n)=2^n-1

最高难度下一共有七层齿轮,所以根据通项公式,f(7)=2^7-1=127步

证毕

了解了理论上的通项公式后,这里可以介绍一个便于记忆的实操方案——

所有的齿轮按从小到大标记为1234567号齿轮,先记住最初的15步(4层)

将前四层齿轮移动到第二根柱子上

将5号齿轮移动到第三根柱子

将前四层齿轮移动到5号齿轮上

将6号齿轮移动到第二根柱子上

将前四层齿轮移动到第一根柱子上

将5号齿轮移动到第二根柱子上

将前四层齿轮移动到第二根柱子上

将7号齿轮移动到第三根柱子上

将前四层齿轮移动到第三根柱子上

将5号齿轮移动到第一根柱子上

将前四层齿轮移动到第一根柱子上

将6号齿轮移动到第三根柱子上

将前四层齿轮移动到第二根柱子上

将5号齿轮移动到第三根柱子上

将前四层齿轮移动到第三根柱子上

30
0
看帖是喜欢,评论才是真爱:
0 / 1000
  • 全部评论
  • 只看楼主
排序:最早
5
0
30
扫码下载
米游社App