石家庄网站制作建设,wordpress重定向插件,管理咨询师考试,撮合交易网站建设方案问题来源
大梵天创造世界的时候做了三根金刚石柱子#xff0c;在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
思路
汉诺塔问题实质是把移动n个盘子的问题转化为移动n-1个盘#xff0c;依据该原…问题来源
大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
思路
汉诺塔问题实质是把移动n个盘子的问题转化为移动n-1个盘依据该原理层层递推即可将原问题转化为解决移动n -2、n -3… … 3、2直到移动1个盘的操作而移动一个盘的操作是可以直接完成的。至此任务真正完成了。
当只有一个盘子时直接将盘子从A柱子移动到C柱子即可 当有多个盘子时可以将问题划分为三个步骤 将上面的n-1个盘子从A柱子移动到B柱子(借助C柱子) 将最底下的一个盘子从A柱子移动到C柱子 将B柱子上的n-1个盘子移动到C柱子(借助A柱子)
代码
package com.algorithm;public class Hanoi {public static void han(int n,char a,char b,char c) {if(n1) {System.out.println(将盘子从a移动到c);} else {//将上面的n-1个盘子从A柱子移动到B柱子借助C柱子han(n-1,a,c,b);//将最底下的一个盘子从A柱子移动到C柱子System.out.println(将盘子从a移动到c);//将上面的n-1个盘子从B柱子移动到C柱子借助A柱子han(n-1,b,a,c);}}public static void main(String[] args) {int n 4; //盘子数char a A;char b B;char c C;han(n,a,b,c);}
}
输出结果 将盘子从A移动到B 将盘子从A移动到C 将盘子从B移动到C 将盘子从A移动到B 将盘子从C移动到A 将盘子从C移动到B 将盘子从A移动到B 将盘子从A移动到C 将盘子从B移动到C 将盘子从B移动到A 将盘子从C移动到A 将盘子从B移动到C 将盘子从A移动到B 将盘子从A移动到C 将盘子从B移动到C
问移动次数的计算
n 个圆盘的移动次数等于 f(1)2f(n-1) f(1) 2[f(1) 2f(n-2)] f(1) 2{f(1) 2*[f(1) 2*f(n-3)]} 2^n - 1 其实这是一个 首项为 1公比为 2的等比数列之和 如果有 64 个圆盘要多少次? 需要移动 18446744073709551615 次如果一秒移动一次需要5千多亿年。
