C语言编程题汉诺塔问题

1、递归解法

递归是最常见和经典的解决方法，通过递归调用函数来实现移动。

#include <stdio.h>

// 函数声明
void hanoi_recursive(int n, char from, char to, char aux);

// 主函数
int main() {
    int n = 3; // 设置盘子数
    hanoi_recursive(n, 'A', 'C', 'B');
    return 0;
}

// 递归函数实现
void hanoi_recursive(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", from, to);
        return;
    }
    hanoi_recursive(n - 1, from, aux, to);
    printf("Move disk %d from rod %c to rod %c\n", n, from, to);
    hanoi_recursive(n - 1, aux, to, from);
}

2、非递归解法（使用栈）

使用栈来模拟递归的过程，实现非递归的解法。

#include <stdio.h>

// 结构体定义栈元素
struct StackItem {
    int n;
    char from, to, aux;
};

// 定义栈结构体
struct Stack {
    int capacity;
    int top;
    struct StackItem *array;
};

// 函数声明
struct Stack *createStack(int capacity);
void push(struct Stack *stack, struct StackItem item);
struct StackItem pop(struct Stack *stack);
void hanoi_iterative(int n);

// 主函数
int main() {
    int n = 3; // 设置盘子数
    hanoi_iterative(n);
    return 0;
}

// 创建栈
struct Stack *createStack(int capacity) {
    struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (struct StackItem *)malloc(capacity * sizeof(struct StackItem));
    return stack;
}

// 入栈
void push(struct Stack *stack, struct StackItem item) {
    stack->array[++stack->top] = item;
}

// 出栈
struct StackItem pop(struct Stack *stack) {
    return stack->array[stack->top--];
}

// 非递归解法
void hanoi_iterative(int n) {
    struct Stack *stack = createStack(n);
    struct StackItem initial = {n, 'A', 'C', 'B'};
    push(stack, initial);
    
    while (stack->top >= 0) {
        struct StackItem item = pop(stack);
        int m = item.n;
        char from = item.from, to = item.to, aux = item.aux;
        
        if (m == 1) {
            printf("Move disk 1 from rod %c to rod %c\n", from, to);
        } else {
            struct StackItem temp1 = {m - 1, aux, to, from};
            struct StackItem temp2 = {1, from, to, aux};
            struct StackItem temp3 = {m - 1, from, aux, to};
            push(stack, temp3);
            push(stack, temp2);
            push(stack, temp1);
        }
    }
}

3、迭代解法（使用移位运算）

使用移位运算实现汉诺塔问题的解法。

#include <stdio.h>

void hanoi_iterative_shift(int n, char from, char to, char aux) {
    int moves = (1 << n) - 1;
    for (int i = 1; i <= moves; ++i) {
        char source_peg = (i & i - 1) % 3;
        char dest_peg = ((i | i - 1) + 1) % 3;
        printf("Move disk from peg %c to peg %c\n", source_peg + 'A', dest_peg + 'A');
    }
}

int main() {
    int n = 3; // 设置盘子数
    hanoi_iterative_shift(n, 'A', 'C', 'B');
    return 0;
}

4、递归解法（动态规划）

使用动态规划算法解决汉诺塔问题。

#include <stdio.h>

void hanoi_recursive_dp(int n, char from, char to, char aux) {
    if (n > 0) {
        hanoi_recursive_dp(n - 1, from, aux, to);
        printf("Move disk from peg %c to peg %c\n", from, to);
        hanoi_recursive_dp(n - 1, aux, to, from);
    }
}

int main() {
    int n = 3; // 设置盘子数
    hanoi_recursive_dp(n, 'A', 'C', 'B');
    return 0;
}

5、递归解法（使用位运算）

使用位运算解决汉诺塔问题的递归解法。

#include <stdio.h>

void hanoi_recursive_bit(int n, char from, char to, char aux) {
    if (n > 0) {
        hanoi_recursive_bit(n - 1, from, aux, to);
        printf("Move disk from peg %c to peg %c\n", from, to);
        hanoi_recursive_bit(n - 1, aux, to, from);
    }
}

int main() {
    int n = 3; // 设置盘子数
    hanoi_recursive_bit(n, 'A', 'C', 'B');
    return 0;
}