汉诺塔问题

时间限制: 1 Sec  内存限制: 128 MB

题目描述

汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有n个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这n个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。

输入

输入盘子个数n

输出

输出盘子最少移动的步骤

样例输入

3

样例输出

1:A->C2:A->B3:C->B4:A->C5:B->A6:B->C7:A->C

1 #include 
     
       2  3 using namespace std; 4 int count = 1; 5 void Hanoi(int n, char a, char b, char c) 6 { 7     if(n == 1) 8         cout << count++ << ":" << a << "->" << c << endl; 9     else {10         Hanoi(n-1,a,c,b);11         cout << count++ << ":" << a << "->" << c << endl;12         Hanoi(n-1,b,a,c);13     }14 }15 16 int main()17 {18     int n;19     char a = 'A', b = 'B', c = 'C';20     while(cin >> n)21     {22         Hanoi(n,a,b,c);23     }24     return 0;25 }