Java汉诺塔
Demo龙 人气:01.汉诺塔介绍
汉诺塔规则
1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上
经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片: 如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C
2.解塔步骤
圆盘:12345 柱子:ABC
1→C,2→B,1→B,3→C,1→A,2→C,1→C,4→B; 1→B,2→A,1→A,3→B,1→C,2→B,1→B,5→C; 1→A,2→C,1→C,4→A,1→B,2→A,1→A,4→C; 1→C,2→B,1→B,3→C,1→A,2→C,1→C,完成!
3.C++实现(递归结果及显示步骤)
(1)递归结果
#include<iostream> using namespace std; int H_tower(int num); int main() { int num; cout<<"请输入需要移动的盘子数"<<endl; cin>>num; cout<<H_tower(num)<<endl; } int H_tower(int num) { if(num<1) { cout<<"请输入大于等于一的数"<<endl; exit(-1); //输入不合法,退出程序 } if(num==1) { return 1; } return (2*H_tower(num-1)+1);//规律递归 }
(2)显示步骤
#include<iostream> using namespace std; void hannuo(int num); void Move(int &sum,int num,char A,char B,char C); int main() { int num; cout<<"请输入需要移动的盘子数"<<endl; cin>>num; hannuo(3); } void hannuo(int num) { if(num<1) { cout<<"请输入大于等于一的数"<<endl; exit(-1); //输入不合法,退出程序 } int sum=0; Move(sum,num,'A','B','C'); } void Move(int &sum,int num,char A,char B,char C) { if(num==1) { sum++; //圆盘只有一个时,只需将其从A塔移到C塔 cout << "第 "<<sum<<" 次move " << num << " from " << A << " to " << C << endl; } else { Move(sum,num - 1, A, C, B);//递归,把A塔上编号1~n-1的圆盘移到B上,以C为辅助塔 sum++; cout << "第 "<<sum<<" 次move " << num << " from " << A << " to " << C << endl;//把A塔上编号为n的圆盘移到C上 Move(sum,num - 1, B, A, C);//递归,把B塔上编号1~n-1的圆盘移到C上,以A为辅助塔 } }
4.Java实现(递归结果及显示步骤)
(1)递归结果
hannuo.java
import java.util.Scanner; public class hannuo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num; System.out.println("请输入需要移动的盘子数"); num= sc.nextInt(); tower t=new tower(); System.out.println("需要移动的次数 = "+t.H_tower(num)); } }
tower.java
public class tower { public int H_tower(int num) { if (num < 1) { System.out.println("请输入大于等于一的数" ); } if (num == 1) { return 1; } return (2 * H_tower(num - 1) + 1);//规律递归 } }
(2)显示步骤
hannuo.java
import java.util.Scanner; public class hannuo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num; System.out.println("请输入需要移动的盘子数"); num= sc.nextInt(); tower t=new tower(); t.hannuo(num); } }
tower.java
public class tower { public void hannuo(int num) { if(num<1) { System.out.println("请输入大于等于一的数"); } int sum[]={0}; Move(num,'A','B','C'); } public void Move(int num,char A,char B,char C) { if(num==1) { //圆盘只有一个时,只需将其从A塔移到C塔 System.out.println(" move " + num + " from " + A + " to " + C ); } else { Move(num - 1, A, C, B);//递归,把A塔上编号1~n-1的圆盘移到B上,以C为辅助塔 System.out.println(" move " + num + " from " + A + " to " + C );//把A塔上编号为n的圆盘移到C上 Move(num - 1, B, A, C);//递归,把B塔上编号1~n-1的圆盘移到C上,以A为辅助塔 } } }
加载全部内容