ハノイの塔(非再帰Ver)

元ネタは以下二つ

• 2005-10-08
• ハノイの塔を攻略せよ！【Windowsプログラミング研究所】

上リンクの仮想スタックを使った末尾再帰と非末尾再帰について
末尾再帰

void f(){
    if (e) return ;
    g();
    f();
}
↓
void f(){
    push();
    while(pop()){
        if (e) continue;
        g();
        push();
    }
}

非末尾再帰(分かりやすくするためにコードを修正)

void f(){
    if (e) return ;
    f();
    g();
}
↓
void f(){
    push();
    while(true){
        if (e) { pop(); break; }
        push();
    }
    while(pop()){
        g();
    }
}

この二つを併せて

void f(){
    if (e) return ;
    f();
    g();
    f();
}
↓
void f(){
    push();
    while(pop()){
        push();
        while(true){
            if (e) { pop(); break; }
            push();
        }
        if(pop()){
            if(e) continue;
            g();
            push();
        }
    }
}

下リンクのハノイの塔(再帰Ver)について

void Hanoi(int n,char *from,char *work,char *dest)
{
    if(n>=1){
        Hanoi(n-1,from,dest,work);

        printf("%d を %s から %s へ\n",n,from,dest);

        Hanoi(n-1,work,from,dest);
    }
}

を少し修正し

void hanoi(int n, char from, char work, char dest)
{
    if (n == 0) return;
    hanoi(n - 1, from, dest, work);

    printf("%d を %c から %c へ\n", n, from, dest);

    hanoi(n - 1, work, from, dest);
}

後はそれぞれの処理を機械的に置き換えてやれば完成


※(e) → (n == 0)、f() → push()、g() → printf()
Cの場合 gcc (GCC) 3.4.2 (mingw-special)

/*
  ハノイの塔(仮想スタックによる非再帰処理Ver)
*/
#include <stdio.h>
#include <assert.h>

void hanoi(int n_, char from_, char work_, char dest_);

/* スタック用--------------------------------- */
int n;
char from;
char work;
char dest;
int stack[65 * 4]; /* 世界滅亡枚数まで溜めちゃるけんね */
int stack_index = 0;
void push(int n_, int from_, int work_, int dest_);
int pop(void);
/* ------------------------------------------- */

int main(void)
{
    int n;

    printf("円盤の枚数: ");
    scanf("%d", &n);

    hanoi(n, 'A', 'B', 'C');

    return 0;
}

void hanoi(int n_, char from_, char work_, char dest_)
{
    push(n_, from_, work_, dest_);
    
    while (pop())
    {
        push(n, from, work, dest);
        while (1)
        {
            if (n == 0) { pop(); break; }
            push(n - 1, from, dest, work);
        }

        if (pop())
        {
            if (n == 0) continue;
            printf("%d を %c から %c へ\n", n, from, dest);
            push(n - 1, work, from, dest);
        }
    }
}

/* スタック用--------------------------------- */
void push(int n_, int from_, int work_, int dest_)
{
    assert(stack_index <= (65 - 1) * 4);

    n = stack[stack_index++] = n_;
    from = stack[stack_index++] = from_;
    work = stack[stack_index++] = work_;
    dest = stack[stack_index++] = dest_;
}
int pop()
{
    if (stack_index == 0) return 0;
    dest = stack[--stack_index];
    work = stack[--stack_index];
    from = stack[--stack_index];
    n = stack[--stack_index];
    return !0;
}
/* ------------------------------------------- */