汉诺塔问题 梦里梦外; 2021-09-28 17:06 471阅读 0赞 汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 若给汉诺塔传说中三根柱子分别用英文字母a,b,c命名,其中只有a柱子摆放n片圆盘(1<=n<=100000), 若要把a柱子上的所有圆盘转移到c柱子上,问最少需要移动多少次圆盘。 移动圆盘的规则如下: 1. 每次只能移动一片圆盘 2. 直径大的圆盘必须摆放在直径小的圆盘之上 问题:打印圆盘在每根柱子上的移动情况;计算圆盘移动的次数。 **递归思路:**我们的目标是在遵守规则的情况下把一根柱子上的盘子全部都移动到另一根柱子上,在三根柱子中假设其中一根为源柱,其中一根为目标柱,最后一根为辅助柱。源柱即所要移动圆盘的柱子,目标柱即圆盘所要移向的柱子,辅助柱即为了保持圆盘小的在上大的在下暂存盘子的柱子。递归是一种描述重复子问题的思想也是一种逆思想,在这里我们可以把1~(n-1)移动到辅助柱看作一步,然后把第n个盘子移动到目标柱,再然后把移动到辅助柱上的盘子也看作一个整体(此时源柱、目标柱、辅助柱已经改变:辅助柱已经变成源柱,目标柱仍是目标柱,源柱已变成辅助柱),再将辅助柱子的盘子挪到原空间上去。 **步骤:** 在这里,把A看作源柱(source)、B看作目标柱(goal)、C看作辅助柱(help),为了方便记忆下面代码直接写出各个英文单词。 1. 把1~(n-1)从A移动到C,把B作为辅助 2. 把n从A移动到B 3. 把1~(n-1)从C移动到B(柱的角色已经改变且把已经移动到C柱上的盘子看作一个子问题),把A作为辅助 **代码:** static void hanoiTower(int n,String source,String goal,String help) {//此为最终结果:我们要把n个盘子从源(柱1)移动到目标(柱2) if(n==1) {//出口 System.out.println("move " +n+ " from "+source + " to "+goal); return; } hanoiTower(n-1,source,help,goal);//第二步,将n-1个盘子从源柱挪到辅助柱子,此时以目标柱为辅助 System.out.println("move " +n+ " from "+source + " to "+goal); hanoiTower(n-1,help,goal,source);//第三步,此时辅助柱已经变成源柱,目标柱仍是目标柱,源柱已变成辅助柱,将辅助柱子的盘子挪到原空间上去 } 再计算所有盘子移动的次数时,将方法中所有的输出语句改成计数语句即可。
相关 汉诺塔问题 include <stdio.h> include <stdlib.h> int Move(int n,char x,char y,char z); 古城微笑少年丶/ 2022年12月12日 12:25/ 0 赞/ 21 阅读
相关 汉诺塔问题 import java.util.Scanner; / 汉诺塔问题 不考虑中转,只考虑起始柱子到目标柱子的移动 记住始终一点:中间一个不管是啥柱 素颜马尾好姑娘i/ 2022年09月30日 00:32/ 0 赞/ 165 阅读
相关 汉诺塔问题 / C为最终放置的柱子,A为起始柱子 / var times = 0; function hanoi(n, a, b, c) { if ( 一时失言乱红尘/ 2022年09月21日 01:37/ 0 赞/ 154 阅读
相关 汉诺塔问题 1.汉诺塔问题:如果将n个盘子(由小到大)从a通过b,搬到c,搬运过程中不能出现小盘子在大盘子下面的情况。 分析:这个一个递归问题。只要将n-1个盘子从a通过c(没有中间点肯 刺骨的言语ヽ痛彻心扉/ 2022年08月20日 10:14/ 0 赞/ 229 阅读
相关 汉诺塔问题 “汉诺塔问题”的Java重写思路:典型的递归问题。 “汉诺塔问题”的Java重写代码: public class Hanoi { 不念不忘少年蓝@/ 2022年07月21日 05:42/ 0 赞/ 159 阅读
相关 汉诺塔问题 汉诺塔 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵 爱被打了一巴掌/ 2022年05月18日 00:40/ 0 赞/ 264 阅读
相关 汉诺塔问题 问题描述: 相传在[古印度][Link 1]圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺 向右看齐/ 2022年04月17日 05:12/ 0 赞/ 294 阅读
相关 汉诺塔问题 汉诺塔问题是经典的递归问题,它的递归类型是:求解问题的方法是递归的。 解题思路: 1. 首先将n-1个盘子从X借助Z移动到Y。 2. 将第n个盘子从X移动到Z。 3. ゝ一世哀愁。/ 2022年03月15日 15:48/ 0 赞/ 231 阅读
相关 汉诺塔问题 汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新 梦里梦外;/ 2021年09月28日 17:06/ 0 赞/ 472 阅读
相关 汉诺塔问题 汉诺塔问题 -------------------- 文章目录 汉诺塔问题 1. 问题描述 2. 问题分析 3. 代 刺骨的言语ヽ痛彻心扉/ 2021年09月23日 23:26/ 0 赞/ 346 阅读
还没有评论,来说两句吧...