汉诺塔:汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘

在进行转移操作时,都必须确保大盘在小盘下面,且每次只能移动一个圆盘,最终c柱上有所有的盘子且也是从上到下按从小到大的顺序。

scratch图解汉诺塔问题

当a柱子上只有一个盘子时只要把那个盘子直接移到c就行了,

有两个盘子的话把1号盘先移到b柱,在把2号盘移到c柱,最后把b柱上的1号盘移到c柱就行了,

那么如果有n个盘子呢?

这里我们先把上方的n-1个盘子看成整体,这下就等于只有两个盘子,自然很容易了,我们只要完成两个盘子的转移就行了,再把前n-2个盘子看作一个整体,就这样一步步向前找到可以直接移动的盘子,n-3......,2,1,最终,最上方的盘子是可以直接移动到c柱的。

scratch图解汉诺塔问题

看到这里其实就已经有了程序的设计思路,那就是递归,这个时候只要理解递归最终的解决的问题是什么就行了,中间的事交给程序,递归可以很绕也可以很直接,我们按照最直接的理解就行了。

如果你想想清楚每一步执行过程,那么你可以继续往下看,确实有点乱,切记别把自己绕晕了。

举个例子: 当n=7时,前6个要想办法成功移动到b柱上,7号是Boss,他不管上面的6个小弟用什么办法,我可以先等着,于是7号在等着上面6个完成移到b柱,现在6是临时老大,他也想去c柱,于是他命令前5个移到b柱,他等着,5号也采取之前两个的做法,于是这个命令一直往前传,没办法,上面被压着自己也没法动啊。

终于到了1号,他是现在唯一能动的,于是1号移动到了b柱,好了,2号可以到c柱。不过a柱上还有3号,于是让1号移到c柱,3号可以到b柱了,之后1号和2号在想办法到b柱,于是1,2,3号在b柱,4号也要得到b柱啊,1,2,3号你们按照刚才的办法到c柱,空出b柱给4号。后面的5号、6号都重复这样的操作,终于前6号移动到b柱,7号直接跑到了c柱,于是剩下在b柱的6个小弟还要再干一遍他们在a柱上干的事。

程序源码下载:scratch解决汉诺塔问题

程序截图:

scratch图解汉诺塔问题

scratch图解汉诺塔问题


本站内容未经许可,禁止任何网站及个人进行转载。

   少儿编程网scratch中文素材在线生成