#include <stdio.h>

//--------------------------------------------------------
// 打印搬運動作
//--------------------------------------------------------
int MoveIt(int x,int Source,int Target)
{
    printf("Move %d From %d to %d\n",x,Source,Target);
    return 0;
}

//--------------------------------------------------------
// 用 4 根柱子移動盤子
// n 是盤子個數，編號從1 到 n
// First 是源柱子號
// Second Third 是兩根過渡柱
// Fourth 是目標柱
//--------------------------------------------------------
int MoveHanoi(int n,int First,int Second,int Third,int Fourth)
{
    if (n<1) return 0;                  // 如果沒有盤子就返回
    if (n==1)                            // 如果只有一個盤子
    {
        MoveIt(n,First,Fourth);          // 就直接從源柱子移到目標柱子上
        return 0;
    }
    if (n==2)                            // 如果有兩個盤子
    {
        MoveIt(n-1,First,Second);        // 把上面的那片移到一個過渡柱上
        MoveIt(n,First,Fourth);          // 把下面的那片移到目標柱上
        MoveIt(n-1,Second,Fourth);      // 再把第 1 片從過渡柱移到目標柱上
return 0;
    }
    if (n==3)                            // 如果有 3 片盤子
    {
        MoveIt(n-2,First,Second);        // 把最小的盤子移到一個過渡柱上
        MoveIt(n-1,First,Third);        // 把中間盤子移到另一過渡柱上
        MoveIt(n,First,Fourth);          // 把最大的盤子移到目標柱上
        MoveIt(n-1,Third,Fourth);        // 把中間盤子移到目標柱上
        MoveIt(n-2,Second,Fourth);      // 把最小的盤子移到目標柱上
        return 0;
    }
                                        // 遞歸地把上面 n-2 盤子移到一個過渡柱上
                                        // 留下最大的兩個盤子
    MoveHanoi(n-2,First,Third,Fourth,Second);
    MoveIt(n-1,First,Third);            // 把倒數第 2 個盤子移到另一個過渡柱上
    MoveIt(n,First,Fourth);              // 把最底下的盤子移到目標柱上
    MoveIt(n-1,Third,Fourth);            // 把倒數第 2 個盤子移到目標柱上
                                        // 遞歸地把 n-2 個盤子從過渡柱上移到目標柱上
    MoveHanoi(n-2,Second,First,Third,Fourth);
    return 0;
}

int main()
{
    MoveHanoi(4,1,2,3,4);
    return 0;
}