[游戏开发]Hanoi塔两种方法实现

传送门

递归实现

void hanoi(int n, char from, char to, char via)	// from -> to,中间为via
{
	if (n == 1) printf("%c -> %c\n", from, to);
	else
	{
		hanoi(n - 1, from, via, to);
		hanoi(1, from, to, via);
		hanoi(n - 1, via, to, from);
	}
}

非递归实现

注意：以下代码不可直接食用！

关于此种方法，jyy老师的视频中涉及过多汇编语言，我现在不能理解，以下代码我试过后发现不能直接引用实现，但是基本思想可以看懂。

typedef struct
{
    int pc, n;
    char from, to, via;
}Frame;

#define call(...) ({ *(++ top) = (Frame) { .pc = 0, _VA_ARGS_ };})
#define ret() ({ top --;})
#define goto(loc) ({ f -> pc = (loc) - 1; })

void hanoi(int n, char from, char to, char via)
{
    Frame stk[64], *top = stk - 1;
    call(n, from, to, via);
    for (Frame *f; (f = top) >= stk; f -> pc ++)
    {
        switch(f -> pc)
        {
            case 0: 
                if (f -> n == 1) 
                {
                    printf("%c -> %c\n", f -> from, f -> to); 
                    goto(4);
                }
                break;
            case 1: call (f -> n - 1, f -> from, f -> via, f -> to);
            case 2: call (         1, f -> from, f -> to,  f -> via);
            case 3: call (f -> n - 1, f -> via,  f -> to,  f -> from);
            case 4: ret();
            default: assert(0);
        }
    }
}