1.漢諾塔介紹
漢諾塔規(guī)則
1.有三根桿子A,B,C。A桿上有若干碟子
2.每次移動(dòng)一塊碟子,小的只能疊在大的上面
3.把所有碟子從A桿全部移到C桿上
經(jīng)過(guò)研究發(fā)現(xiàn),漢諾塔的破解很簡(jiǎn)單,就是按照移動(dòng)規(guī)則向一個(gè)方向移動(dòng)金片: 如3階漢諾塔的移動(dòng):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++實(shí)現(xiàn)(遞歸結(jié)果及顯示步驟)
(1)遞歸結(jié)果
#include<iostream>
using namespace std;
int H_tower(int num);
int main()
{
int num;
cout<<"請(qǐng)輸入需要移動(dòng)的盤子數(shù)"<<endl;
cin>>num;
cout<<H_tower(num)<<endl;
}
int H_tower(int num)
{
if(num<1)
{
cout<<"請(qǐng)輸入大于等于一的數(shù)"<<endl;
exit(-1); //輸入不合法,退出程序
}
if(num==1)
{
return 1;
}
return (2*H_tower(num-1)+1);//規(guī)律遞歸
}
(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<<"請(qǐng)輸入需要移動(dòng)的盤子數(shù)"<<endl;
cin>>num;
hannuo(3);
}
void hannuo(int num)
{
if(num<1)
{
cout<<"請(qǐng)輸入大于等于一的數(shù)"<<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++;
//圓盤只有一個(gè)時(shí),只需將其從A塔移到C塔
cout << "第 "<<sum<<" 次move " << num << " from " << A << " to " << C << endl;
}
else
{
Move(sum,num - 1, A, C, B);//遞歸,把A塔上編號(hào)1~n-1的圓盤移到B上,以C為輔助塔
sum++;
cout << "第 "<<sum<<" 次move " << num << " from " << A << " to " << C << endl;//把A塔上編號(hào)為n的圓盤移到C上
Move(sum,num - 1, B, A, C);//遞歸,把B塔上編號(hào)1~n-1的圓盤移到C上,以A為輔助塔
}
}
4.Java實(shí)現(xiàn)(遞歸結(jié)果及顯示步驟)
(1)遞歸結(jié)果
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("請(qǐng)輸入需要移動(dòng)的盤子數(shù)");
num= sc.nextInt();
tower t=new tower();
System.out.println("需要移動(dòng)的次數(shù) = "+t.H_tower(num));
}
}
tower.java
public class tower {
public int H_tower(int num) {
if (num < 1) {
System.out.println("請(qǐng)輸入大于等于一的數(shù)" );
}
if (num == 1) {
return 1;
}
return (2 * H_tower(num - 1) + 1);//規(guī)律遞歸
}
}
(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("請(qǐng)輸入需要移動(dòng)的盤子數(shù)");
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("請(qǐng)輸入大于等于一的數(shù)");
}
int sum[]={0};
Move(num,'A','B','C');
}
public void Move(int num,char A,char B,char C)
{
if(num==1)
{
//圓盤只有一個(gè)時(shí),只需將其從A塔移到C塔
System.out.println(" move " + num + " from " + A + " to " + C );
}
else
{
Move(num - 1, A, C, B);//遞歸,把A塔上編號(hào)1~n-1的圓盤移到B上,以C為輔助塔
System.out.println(" move " + num + " from " + A + " to " + C );//把A塔上編號(hào)為n的圓盤移到C上
Move(num - 1, B, A, C);//遞歸,把B塔上編號(hào)1~n-1的圓盤移到C上,以A為輔助塔
}
}
}
到此這篇關(guān)于Java與C++分別用遞歸實(shí)現(xiàn)漢諾塔詳解的文章就介紹到這了,更多相關(guān)Java漢諾塔內(nèi)容請(qǐng)搜索html5模板網(wǎng)以前的文章希望大家以后多多支持html5模板網(wǎng)!
【網(wǎng)站聲明】本站部分內(nèi)容來(lái)源于互聯(lián)網(wǎng),旨在幫助大家更快的解決問(wèn)題,如果有圖片或者內(nèi)容侵犯了您的權(quán)益,請(qǐng)聯(lián)系我們刪除處理,感謝您的支持!