7-17汉诺塔的非递归实现

题目描述

题目地址为:https://pintia.cn/problem-sets/15/problems/821

借助堆栈以非递归（循环）方式求解汉诺塔的问题（n, a, b, c），即将N个盘子从起始柱（标记为“a”）通过借助柱（标记为“b”）移动到目标柱（标记为“c”），并保证每个移动符合汉诺塔问题的要求。

输入格式:

输入为一个正整数N，即起始柱上的盘数。

输出格式:

每个操作（移动）占一行，按柱1 -> 柱2的格式输出。

输入样例:

1
3

输出样例:

1
2
3
4
5
6
7
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

思考

非递归方式换个思路就是将递归栈换为手工栈来处理。

具体代码

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
#include <stdio.h>

void hannoi(int n,char x,char y,char z) {
    int N[100],p = 1; 
	char X[100],Y[100],Z[100];
	N[1]=n;X[1]=x;Y[1]=y;Z[1]=z;
    do {
        n = N[p]; x = X[p] ; y = Y[p] ; z = Z[p];
        --p;
        if (n == 1) {
            printf("%c -> %c\n",x,z);
        } else {    //这里是个手动入栈顺序
            ++p; N[p]=n-1; X[p]=y;Y[p]=x;Z[p]=z;
            ++p; N[p]=1; X[p]=x;Y[p]=y;Z[p]=z;
		    ++p; N[p]=n-1; X[p]=x;Y[p]=z;Z[p]=y;
        }
    } while(p > 0);
}

int main(){
    int n;
	scanf("%d",&n);
	hannoi(n,'a','b','c');
    return 0;
}