汉诺塔的2个非递归解法

关于汉诺塔的非递归解法，如果使用堆栈模仿递归解法的入栈出栈操作，则因为编译器产生的汇编指令，对递归解法的出入栈操作优化的效果，非递归解法没有明显的性能提升。这里收录了另外2个非递归解法写法，对栈的使用进行了改进：

func hanoi(n, a, b, c)
{
        abc=a+b+c;

        next:
        while (n>1) {
                --n;
                a[top]=a;
                b[top]=b;
                s[top++]=n;
                x =c; c=b; b=x;
        }
        print "pole:", a, "to", c;
        if(top>0) {
                n= s[--top];
                a=a[top];
                b=b[top];
                c=abc-a-b;
                print "pole:", a, "to", c;
                x =a; a=b; b=x;
                goto next;
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func hanoi(n, a, b, c)
{
        abc=a+b+c;

        a[top]=a;
        b[top]=b;
        s[top++]=n;
        while(top>0) {
                n= s[--top];
                a=a[top];
                b=b[top];
                c=abc-a-b;

                if (n==1) print "pole:", a, "to", c;
                else {
                        a[top]=b;
                        b[top]=a;
                        s[top++] = n-1;
                        a[top] = a;
                        b[top] = b;
                        s[top++] = 1;
                        a[top]= a;
                        b[top]= c;
                        s[top++] = n-1;
                }
        }
}
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
27

第一个参考了2叉树的非递归中序遍历算法。第二个采用压栈生成子任务思路，注意子任务的压栈顺序和实际执行相反。至此，用堆栈改进递归算法的学习终于可以毕业了！