汉诺塔问题

描述

给定A、B、C三根足够长的细柱，在A柱上放有n个中间有孔的圆盘，共有n个不同的尺寸，现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：
（1）每次只能移动一个圆盘；
（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务：设An为n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An以及移动过程

输入盘子的个数输出移动的移动的路径和次数

样例输入

3

 

样例输出

move A->C
move A->B
move C->B
move A->C
move B->A
move B->C
move A->C
7

 

AC代码：

#include <iostream>
using namespace std;
int sum = 0;
void printPath(char a,char b)
{
  printf("move %c->%c\n", a, b);
  sum++;
}
void hanni(int x,char a,char b,char c)
{
  if (x == 1) 
  {
    printPath(a, c);
    return;
  }
  else
  {
    hanni(x - 1, a, c, b);
    printPath(a, c);
    hanni(x - 1, b, a, c);
  }
}
int main()
{
  int n = 0;
  sum = 0;
  cin >> n;
  hanni(n,'A','B','C');
  cout << sum << endl;
}