Solution in C

#include <stdio.h>
#include <assert.h>

/* To debug, define
   SIMULATE DEBUG
   or
   SIMULATE DEBUG ASSERT
 */

#define PILLAR_SIZE 10
#define PILLAR_NUM 3
#define PLATE_NUM 5

typedef struct hanoi_tower
{
    int pillars[PILLAR_NUM][PILLAR_SIZE + 1]; /* position 0 will not be used*/
    int offsets[PILLAR_NUM];
} hanoi_tower;

typedef enum pillar {x, y, z} pillar;
char pillar_names[PLATE_NUM] = {'x', 'y', 'z'};
typedef int counter;

void status(hanoi_tower *ht)
{
    for (pillar i = x; i <= z; i++)
    {
        printf("Pillar %c: ", pillar_names[i]);
        for (int j = 1; j <= ht->offsets[i]; j++)
            printf("%d ", ht->pillars[i][j]);
        printf("\n");
    }
}

/* "to" is final destination, "from" is original source */
void move(hanoi_tower *ht, counter *cnt, int n, pillar from, pillar to, pillar buffer)
{
    if (n == 0)
        return;

    /* Step 1: use "to" as temporay buffer, move n - 1 plates from "from" to "buffer" */
    move(ht, cnt, n - 1, from, buffer, to);

#ifdef DEBUG
    printf("n = %d, precondition: \n", n);
    status(ht);
#endif

    /* Step 2: move only one plate from "from" to "to" */
    ht->offsets[to]++;
    int to_offset = ht->offsets[to];
    int from_offset = ht->offsets[from];
    printf("move %d from Pillar %c to %c\n", n, pillar_names[from], pillar_names[to]);

#ifdef ASSERT
    /* if pillar has at least one plate on it */
    if (to_offset > 1)
        assert(ht->pillars[to][to_offset - 1] > ht->pillars[from][from_offset]);
    assert(ht->pillars[from][from_offset] == n);
#endif

    ht->pillars[to][to_offset] = ht->pillars[from][from_offset];
    ht->offsets[from]--;
    (*cnt)++;
    /* Step 2 end */

#ifdef DEBUG
    printf("n = %d, postcondition: \n", n);
    status(ht);
    printf("\n");
#endif

    /* Step 3: use "from" as temporay buffer, move n - 1 plates from "buffer" to "to" */
    move(ht, cnt, n - 1, buffer, to, from);
}

void mock_move(int n, counter *cnt, pillar from, pillar to, pillar buffer)
{
    if (n == 0)
        return;
    mock_move(n - 1, cnt, from, buffer, to);
    printf("move %d from Pillar %c to %c\n", n, pillar_names[from], pillar_names[to]);
    (*cnt)++;
    mock_move(n - 1, cnt, buffer, to, from);
}

void init(hanoi_tower *ht)
{
    for (int i = 1, j = PLATE_NUM; j > 0; i++, j--)
        ht->pillars[x][i] = j;

    ht->offsets[x] = PLATE_NUM;
    ht->offsets[y] = 0;
    ht->offsets[z] = 0;
}

int main(void)
{
    counter cnt = 0;
#ifdef SIMULATE
    hanoi_tower ht;
    init(&ht);
    printf("Initialized: \n");
    status(&ht);
    move(&ht, &cnt, PLATE_NUM, x, z, y);
    printf("Done: \n");
    status(&ht);
#else
    mock_move(PLATE_NUM, &cnt, x, z, y);
#endif
    printf("Total movements: %d\n", cnt);

    return 0;
}

Analysis

对于移动次数 $M(n)$ 有下列递推等式：

$$ M(n) = M(n -1) + 1 + M(n - 1) $$

且

$$ M(1) = 1 $$

下面使用反向替换法来解递推式：

$$
\begin{aligned} M(n) &= 2 M(n - 1) + 1 \newline &= 2 [2M(n - 2) + 1] + 1 = 2^2 M(n - 2) + 2 + 1 \newline &= 2^2 [M(n - 3) + 1] + 2 + 1 = 2^3 M(n - 3) + 2^2 + 2 + 1 \end{aligned} $$

做 $i$ 次替换后：

$$ \begin{aligned} M(n) &= 2^i M(n - i) + 2^{i - 1} + 2^{i - 2} + \cdots + 2 + 1 \newline &= 2^i M(n - i) + 2^i - 1 \end{aligned} $$

因为初始条件在 $n = 1$ 的情况下确立，所以令 $i = n - 1$

$$ \begin{aligned} M(n) &= 2^{n - 1} M(n - (n - 1)) + 2^{n - 1} - 1 \newline &= 2^{n - 1} M(1) + 2^{n - 1} - 1 \newline &= 2^n - 1 \end{aligned} $$

即 Tower of Hanoi 的移动次数和层数的关系是

$$ M(n) = 2^n - 1 $$

algorithm

CC BY 4.0

Tower of Hanoi problem

Solution in C

Analysis