C语言使用循环与数组替代递归实现汉诺塔

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

void towers(int n, char from, char to, char aux);
int main() {
	towers(3, 'A', 'C', 'B');
	return 0;
}

void showMove (int order, char from, char to) {
	printf("move disk %d from %c to %c\n", order, from, to);
}

void towers(int n, char from, char to, char aux) {
	if (n==1) {
		showMove(n, from, to);
		return;
	}
	towers(n-1, from, aux, to);
	    showMove(n, from, to);
	towers(n-1, aux, to, from);
}

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

// 定义移动动作结构体
typedef struct {
    int order;
    char from;
    char to;
} MoveAction;

// 更新动作数组中的某一项
void setMoveAction(MoveAction *p, int order, char from, char to) {
    p->order = order;
    p->from = from;
    p->to = to;
}

// 辅助函数：根据当前柱子角色转换源/目标字符
char compare_map(char c, char left, char right) {
    if (c == left) return right;
    else if (c == right) return left;
    return c;
}

void towers(int n, char from, char to, char aux) {
    MoveAction *actions, action;
    int i, k, size;
    char f, t;

    // 计算理论上的总步数上限并分配内存
    // 注意：实际有效步数为 2^n - 1，此处分配稍作调整以适配索引
    actions = (MoveAction *)calloc(pow(2, n), sizeof(MoveAction));
    
    // 初始化第1个盘子（i=1）的移动动作
    setMoveAction(&actions[0], 1, from, to);
    size = 1; // 当前已记录的步数对应 2^1 - 1 = 1

    // 迭代处理每一个盘子的加入
    for (i = 2; i <= n; i++) {
        /*
         * 循环逻辑说明：
         * 现有 size 步记录了移动 i-1 个盘子的过程。
         * 新的序列由三部分组成：
         * 1. 原序列经过变换后，表示将 i-1 个盘从 From 移到 Aux。
         * 2. 新增一步：将第 i 号盘从 From 移到 To。
         * 3. 原序列经过变换后，表示将 i-1 个盘从 Aux 移到 To。
         */

        // 第一部分：倒序处理或变换原序列前半部分，映射到 Aux 场景
        // 这里为了填充数组后半段，先准备中间的大盘位置，再填充尾部
        
        // 求解集合 {actions[x] | size + 1 <= x <= 2*size }
        // 这部分对应：将 i-1 个盘从 Aux 移动到 To (即最终的第三步)
        for (k = 0; k < size; k++) {
            action = actions[k];
            // 变换坐标系：原(from, to) 变为 (aux, to)
            f = compare_map(action.from, from, aux);
            t = compare_map(action.to, from, aux);
            setMoveAction(&actions[k + size + 1], action.order, f, t);
        }

        // 第二部分：记录第 i 个盘子的移动
        setMoveAction(&actions[size], i, from, to);

        // 第三部分：求解集合 {actions[x] | 0 <= x <= size -1 }
        // 这部分对应：将 i-1 个盘从 From 移动到 Aux (即第一步)
        // 需要原地覆盖原数组内容，或者重新映射。由于后续不再需要旧数据，可直接覆盖
        for (k = 0; k < size; k++) {
            action = actions[k];
            // 变换坐标系：原(from, to) 变为 (from, aux)
            f = compare_map(action.from, to, aux);
            t = compare_map(action.to, to, aux);
            setMoveAction(&actions[k], action.order, f, t);
        }

        // 更新当前步数规模：size_new = size_old * 2 + 1
        size = size * 2 + 1;
    }

    // 输出所有生成的动作
    for (i = 0; i < size; i++) {
        showMove(actions[i].order, actions[i].from, actions[i].to);
    }
    
    free(actions); // 释放内存
}

int main() {
    towers(3, 'A', 'C', 'B');
    return 0;
}

void showMove(int order, char from, char to) {
    printf("move disk %d from %c to %c\n", order, from, to);
}