【NC201605】Bits

题目

Bits

模拟，递归

思路

汉诺塔相信大家都很熟悉，在高中时的数列递推部分就曾接触过。并且在编程入门时可能会做关于汉诺塔的这么一道题：

给你一个数 $n$ 表示盘子数，请你输出将所有盘子从柱子 $A$ 移动到柱子 $C$ 的步骤
比如 $n=2$，则应该输出：
$$\begin{gathered} A\to B \\ A\to C \\ B\to C \end{gathered}$$

这道题很适合用递归的思路来解决：

首先有三个柱子，一个是最左边初始时放盘子的柱子（记为 $from$），一个是中间用来中转的柱子（记为 $tmp$），一个是最右边盘子最终要放置的柱子（记为 $to$）。我们知道，要将 $from$ 上的所有 $n$ 个盘子都放到 $to$ 上，就需要先将 $n-1$ 个盘子放到 $tmp$ 上，再将 $1$ 个盘子（最大的那个）放到 $to$ 上，然后再将 $tmp$ 上的 $n-1$ 个盘子放到 $to$ 上。
那么怎么将 $tmp$ 上的 $n-1$ 个盘子放到 $to$ 上呢？递归地进行上面的步骤即可，直到边界 $n=1$。

使用伪代码描述上面的递归过程：

# 定义递归函数 move
def move(from, to, tmp, n):
	if n == 1:
		# 递归边界，输出移动过程后返回
		print(from -> to)
		return
	# 否则先将 n - 1 个盘子放到 tmp 上，此时将 to 看作 "tmp"
	move(from, tmp, to, n - 1)
	# 再将 1 个最大的盘子移到 to 上
	# 输出移动过程
	print(from -> to)
	# 再将 n - 1 个盘子从 tmp 上移动到 to 上，此时将 from 看作 "tmp"
	move(tmp, to, from, n - 1)

回到这道题，思路上和上面的思路一摸一样，只是需要做“数据的可视化”，我们将每一副输出的图像看作是对某些数据的展示，变化的永远是数据。

进一步模拟：将 $from,tmp,to$ 三个柱子上的盘子看作是三个数组，这三个数组的元素都是从大到小排列的。输出的图像就是对这三个数组的可视化描述。

怎么表示“移动”步骤呢？

比如将 $from$ 上的一个盘子移动到 $to$ 上，则只需要将 $from$ 数组的最后一个元素放到 $to$ 数组的末尾即可，然后将 $from$ 数组的最后一个元素去掉（类似于出栈入栈）

基本的思路已经理清了，现在的伪代码应该这样写，在 $move$ 函数中只改变了输出动作：

# 定义三个数组表示三个柱子上的盘子
from = [n,n-1,...,1] # 初始时盘子都在 from 上
tmp = []
to = []
# 定义递归函数 move
def move(from, to, tmp, n):
	if n == 1:
		# 递归边界，移动后返回
		put from.last to to.last
		return
	# 否则先将 n - 1 个盘子放到 tmp 上，此时将 to 看作 "tmp"
	move(from, tmp, to, n - 1)
	# 再将 1 个最大的盘子移到 to 上
	put from.last to to.last
	# 再将 n - 1 个盘子从 tmp 上移动到 to 上，此时将 from 看作 "tmp"
	move(tmp, to, from, n - 1)

现在每一步的移动过程已经清楚了（如果你在移动一步之后输出三个数组的值，就会看得更清楚），那么怎么展示呢？

现在的任务就变成了根据三个数据数组来进行可视化，我们只需在 $move$ 函数的移动过程之后加一个 $draw$ 函数即可：

# 定义三个数组表示三个柱子上的盘子
from = [n,n-1,...,1] # 初始时盘子都在 from 上
tmp = []
to = []
# 定义递归函数 move
def move(from, to, tmp, n):
	if n == 1:
		# 递归边界，移动后返回
		put from.last to to.last
		draw()
		return
	# 否则先将 n - 1 个盘子放到 tmp 上，此时将 to 看作 "tmp"
	move(from, tmp, to, n - 1)
	# 再将 1 个最大的盘子移到 to 上
	put from.last to to.last
	draw()
	# 再将 n - 1 个盘子从 tmp 上移动到 to 上，此时将 from 看作 "tmp"
	move(tmp, to, from, n - 1)

到这里代码框架已经搭建完毕，就只剩实现了，主要是实现 $draw$ 函数，怎么根据三个数据数组来展示题目要求输出的图像呢？

我们将这个图像当作字符数组来处理。经过观察，当输入为 $n$ 时，输出的字符数组的行数为 $r=n+2$，列数为 $c=3(2n+1)+4=6n+7$。并且在列下标为 $n+1、n+1+2(n+1)、n+1+4(n+1)$ 处，从行下标为 $1$ 到 $n+1$ 处初始时为 $|$，比如 $n=2$，则应该先生成这样一副初始图像：

...................
...|.....|.....|...
...|.....|.....|...
...|.....|.....|...

然后再去上面画 $\ast$。遍历三个数组，我们发现将三个数组看作一个整体（即一个 $3$ 行的二维数组比较方便，为什么呢？

假设将三个数组按柱子的顺序看作一个二维数组 $dishes$，则遍历这个二维数组时，设当前坐标为 $(i,j)$（表示第 $i$ 行第 $j$ 列），则有下面的规律：

1. 应该画 $\ast$ 的行号：$r=n+1-j$
2. 应该画 $\ast$ 的中间列号（因为图像中的 $\ast$ 是以初始时 $|$ 的列为轴对称的）：$c=n+1+2i(n+1)$
3. 应该在画 $\ast$ 的中间列号两侧画的 $\ast$ 的个数：$cnt=dishes[i][j]$

问题到此解决，具体见代码。

为了让代码更加结构化，这里给出的代码将各个部分都尽可能进行了封装，如果只是为了做题则大可不必这样（也不用在堆上开辟内存）。并且需要注意的是，题目还对 $n$ 的奇偶性给出了限制。

代码

#include <stdio.h>
#include <stdlib.h>

#define N 11

// A B C三个桩上的盘子数组
// dishes[i][N] 为盘子数量
int dishes[3][N + 1];
// 盘子的数量副本 nn，这个变量不会被递归所污染
// 图像数组的长度 snapshoot_n
int nn, snapshoot_n;

// 获取并初始化步骤图像数组
char*** init_snapshoot(int n) {
    // 行/列/页
    int r = n + 2, c = 6 * n + 7, p = 1 << n;
    int i = 0, j = 0, k = 0;
    char*** snapshoot = (char***)malloc(p * sizeof(char**));
    for (i = 0; i < p; i++) {
        snapshoot[i] = (char**)malloc(r * sizeof(char*));
        for (j = 0; j < r; j++) {
            snapshoot[i][j] = (char*)malloc(c * sizeof(char));
            for (k = 0; k < c; k++) {
                snapshoot[i][j][k] = '.';
            }
        }
        for (j = 1; j < r; j++) {
            for (k = n + 1; k < c; k += (n + 1) << 1) {
                snapshoot[i][j][k] = '|';
            }
        }
    }
    return snapshoot;
}

// 画图像
void draw_snapshoot(char*** snapshoot, int snapshoot_idx, int n) {
    int i = 0, j = 0, k = 0, x = 0, y = 0;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < dishes[i][N]; j++) {
            x = n + 1 - j;
            y = n + 1 + 2 * i * (n + 1);
            for (k = -dishes[i][j]; k <= dishes[i][j]; k++) {
                snapshoot[snapshoot_idx][x][y + k] = '*';
            }
        }
    }
}

// 展示图像
void show_snapshoot(char*** snapshoot, int n) {
    // 行/列/页
    int r = n + 2, c = 6 * n + 7, p = 1 << n;
    int i = 0, j = 0, k = 0;
    for (i = 0; i < p; i++) {
        for (j = 0; j < r; j++) {
            for (k = 0; k < c; k++) {
                printf("%c", snapshoot[i][j][k]);
            }
            printf("\n");
        }
        if (i < p - 1) {
            for (j = 0; j < c; j++) {
                printf("-");
            }
            printf("\n");
        }
    }
}

// 释放内存
void destroy_snapshoot(char*** snapshoot, int n) {
    // 行/列/页
    int r = n + 2, c = 6 * n + 7, p = 1 << n;
    int i = 0, j = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            free(snapshoot[i][j]);
        }
        free(snapshoot[i]);
    }
    free(snapshoot);
}

// 移动盘子并记录每一步得到的图像
void hano(int n, int from_idx, int to_idx, int tmp_idx, char*** snapshoot) {
    if (n == 1) {
        dishes[to_idx][dishes[to_idx][N]++] =
            dishes[from_idx][--dishes[from_idx][N]];
        draw_snapshoot(snapshoot, snapshoot_n++, nn);
        return;
    }
    hano(n - 1, from_idx, tmp_idx, to_idx, snapshoot);
    dishes[to_idx][dishes[to_idx][N]++] =
        dishes[from_idx][--dishes[from_idx][N]];
    draw_snapshoot(snapshoot, snapshoot_n++, nn);
    hano(n - 1, tmp_idx, to_idx, from_idx, snapshoot);
}

int main(void) {
    int n = 0;
    scanf("%d", &n);
    nn = n;
    snapshoot_n = 0;
    // 初始化盘子
    while (n--) {
        dishes[0][dishes[0][N]++] = n + 1;
    }
    n = nn;  // 恢复回来
    // 初始化每幅图像
    char*** snapshoot = init_snapshoot(n);
    // 画第一张初始化的图像
    draw_snapshoot(snapshoot, snapshoot_n++, n);
    // 注意题目要求，n 的奇偶性不同，盘子放到的桩就不同
    if (n & 1) {
        hano(n, 0, 1, 2, snapshoot);
    } else {
        hano(n, 0, 2, 1, snapshoot);
    }
    // 打印出所有的图像
    show_snapshoot(snapshoot, n);
    // 销毁堆中分配的内存
    destroy_snapshoot(snapshoot, n);
    return 0;
}