設(shè)A,B,C是3個(gè)塔座漱凝。開(kāi)始時(shí)，在塔座A上有一疊共n個(gè)圓盤(pán)惰瓜，這些圓盤(pán)自下而上否副，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座A上的這一疊圓盤(pán)移到塔座C上崎坊，并仍按同樣順序疊置副编。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：
規(guī)則1：每次只能移動(dòng)1個(gè)圓盤(pán)；
規(guī)則2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上流强；
規(guī)則3：在滿(mǎn)足規(guī)則1和2的前提下痹届，可將圓盤(pán)移至A,B,C中任一塔座上。
主要思路：
1打月、將A上的n-1個(gè)盤(pán)子借助C移到B上
2队腐、將A上的第n個(gè)盤(pán)子移到C上
3、再將B上的全部盤(pán)子移到C上
ps：顯然奏篙，這是一個(gè)遞歸的過(guò)程柴淘。
算法思路
1、構(gòu)造一個(gè)顯示盤(pán)子移動(dòng)路徑的函數(shù)
void move (char a, char b) {
cout << a << "->" << c;
}
2秘通、構(gòu)造一個(gè)遞歸函數(shù)
void hanoi (int n, char a, char b, char c) {
//將A上的n個(gè)盤(pán)子借助B全部移到C上
if (n == 1) move(a, c);//如果A上只有一個(gè)盤(pán)子为严，將A上最后一個(gè)盤(pán)子移到C上，結(jié)束本層遞歸
else {
hanoi (n-1, a, c, b);//將A上n-1個(gè)盤(pán)子全部移到B上
move (a, c);//顯示路徑
hanoi (n-1, b, a, c);//將B上的n-1個(gè)盤(pán)子移到C上
}
}
完整代碼
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
void move (char a, char b) {
cout << a << "->" << c;
}
void hanoi (int n, char a, char b, char c) {
if (n == 1) move(a, c);
else {
hanoi (n-1, a, c, b);
move (a, c);
hanoi (n-1, b, a, c);
}
}
int main ()
{
char a = 'A', b = 'B', c = 'C';
int n;
cin >> n;
hanoi (n, a, b, c)
return 0;
}
Example
4 enter
輸出結(jié)果：
4
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
