汉诺塔之三

coding>C++
829 词

题目描述

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆环，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 

  1. 每次只能移动一个圆盘；
  2. 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。 

问：怎么移？最少要移动多少次？ 

输入

一个整数 n ，代表汉诺塔层数 （n<=10）

输出

移动的方式和最少需要的步数

样例输入

1
3

样例输出

1
2
3
4
5
6
7
8
移动圆盘:1从盘a到盘c
移动圆盘:2从盘a到盘b
移动圆盘:1从盘c到盘b
移动圆盘:3从盘a到盘c
移动圆盘:1从盘b到盘a
移动圆盘:2从盘b到盘c
移动圆盘:1从盘a到盘c
7

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<stdlib.h>
void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        printf("移动圆盘:%d从盘%c到盘%c\n", n, A, C);
    }
    else {
        hanoi(n - 1, A, C, B);
        printf("移动圆盘:%d从盘%c到盘%c\n", n, A, C);
        hanoi(n - 1, B, A, C);
    }
}
int pow(int n, int a) {
    int sum = 1;
    for (int i = 1; i <= a; i++) {
        sum *= n;
    }
    return sum;
}
int main() {
    int n;
    scanf("%d", & n);
    hanoi(n, 'a', 'b', 'c');
    printf("%d\n", pow(2, n) - 1);
    return 0;
}