首页 > 代码库 > 河内塔(hanoi)
河内塔(hanoi)
理论；
河内塔：
1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上
讲解：
设A上有n个盘子。
如果n=1，则将圆盘从A直接移动到C。
如果n=2，则：
1.将A上的n-1(等于1)个圆盘移到B上；
2.再将A上的一个圆盘移到C上；
3.最后将B上的n-1(等于1)个圆盘移到
如果n=3，则：
A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，步骤如下：
(1)将A上的n`-1(等于1)个圆盘移到C上。
(2)将A上的一个圆盘移到B。
(3)将C上的n`-1(等于1)个圆盘移到B。
B. 将A上的一个圆盘移到C。
C. 将B上的n-1(等于2，令其为n`)个圆盘移到C(借助A)，步骤如下：
(1)将B上的n`-1(等于1)个圆盘移到A。
(2)将B上的一个盘子移到C。
(3)将A上的n`-1(等于1)个圆盘移到C。
到此，完成了三个圆盘的移动过程。
从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：
第一步 把A上的n-1个圆盘移到B上；
第二步 把A上的一个圆盘移到C上；
第三步 把B上的n-1个圆盘移到C上；
显然这是一个递归过程，据此算法可编程如下：
package 经典;public class 河内塔 { // 2(a b c)-(a-c)// 1-b // 2-c// 1-c//// 3(a b c)-(a-c)//// 前两个盘 2(a b c)-(a-b)// 第三个盘(a b c)-(a-c)// 前两个盘(b a c)-(b-c) public static void hanoi(int n,char origin,char assist,char destination){ if(n==1) { move(origin,destination); } else{ hanoi(n-1,origin,destination,assist); move(origin,destination); hanoi(n-1,assist,origin,destination); } } public static void move(char origin,char destination){ System.out.println("move from "+origin+" to "+destination); } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub hanoi(3,‘A‘,‘B‘,‘C‘); }}
河内塔(hanoi)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。