汉诺塔问题

描述

给定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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

10 + 20 =