c语音递归函数汉诺塔

以下是C语言递归函数实现汉诺塔的代码示例：

#include <stdio.h>

void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        printf("%c -> %c\n", A, C);
    } else {
        hanoi(n - 1, A, C, B);
        printf("%c -> %c\n", A, C);
        hanoi(n - 1, B, A, C);
    }
}

int main() {
    int n = 3; // 汉诺塔的层数
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

相关问题

C语言非递归解决汉诺塔问题

以下是C语言非递归解决汉诺塔问题的代码示例：

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

// 定义栈的结构
typedef struct {
    int *arr;
    int top;
    int capacity;
} Stack;

// 初始化栈
Stack* initStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->arr = (int*)malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈
void push(Stack *stack, int data) {
    if (isFull(stack)) {
        printf("Stack is full.\n");
        return;
    }
    stack->arr[++stack->top] = data;
}

// 出栈
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty.\n");
        return -1;
    }
    return stack->arr[stack->top--];
}

// 非递归解决汉诺塔问题
void hanoiNonRecursive(int n, Stack *src, Stack *aux, Stack *dest) {
    int totalMoves = (1 << n) - 1; // 总共需要移动的次数

    // 根据奇偶性确定第一个辅助塔
    Stack *temp;
    if (n % 2 == 0) {
        temp = aux;
        aux = dest;
        dest = temp;
    }

    for (int i = n; i >= 1; i--) {
        push(src, i); // 将盘子依次入栈
    }

    for (int i = 1; i <= totalMoves; i++) {
        if (i % 3 == 1) {
            if (isEmpty(src)) {
                push(src, pop(aux));
            } else if (isEmpty(aux)) {
                push(aux, pop(src));
            } else if (src->arr[src->top] > aux->arr[aux->top]) {
                push(src, pop(aux));
            } else {
                push(aux, pop(src));
            }
        } else if (i % 3 == 2) {
            if (isEmpty(src)) {
                push(src, pop(dest));
            } else if (isEmpty(dest)) {
                push(dest, pop(src));
            } else if (src->arr[src->top] > dest->arr[dest->top]) {
                push(src, pop(dest));
            } else {
                push(dest, pop(src));
            }
        } else if (i % 3 == 0) {
            if (isEmpty(aux)) {
                push(aux, pop(dest));
            } else if (isEmpty(dest)) {
                push(dest, pop(aux));
            } else if (aux->arr[aux->top] > dest->arr[dest->top]) {
                push(aux, pop(dest));
            } else {
                push(dest, pop(aux));
            }
        }
    }
}

int main() {
    int n = 3; // 汉诺塔的盘子数量

    Stack *src = initStack(n);
    Stack *aux = initStack(n);
    Stack *dest = initStack(n);

    hanoiNonRecursive(n, src, aux, dest);

    printf("Move the disks from source to destination:\n");
    for (int i = n - 1; i >= 0; i--) {
        printf("%d -> %d\n", src->arr[i], dest->arr[i]);
    }

    free(src->arr);
    free(aux->arr);
    free(dest->arr);
    free(src);
    free(aux);
    free(dest);

    return 0;
}

利用C语言非递归解决汉诺塔问题代码

请看以下代码：

#include <stdio.h>

void move(int n, char A, char B, char C) {
    if (n == 1) {
        printf("%c -> %c\n", A, C);
        return;
    }
    move(n - 1, A, C, B);
    printf("%c -> %c\n", A, C);
    move(n - 1, B, A, C);
}

int main() {
    int n;
    printf("请输入汉诺塔的层数：");
    scanf("%d", &n);
    move(n, 'A', 'B', 'C');
    return 0;
}

注意，这是使用递归来解决汉诺塔问题的代码，如果你希望使用非递归解决汉诺塔问题，可以参考以下原理：

使用非递归方法解决汉诺塔问题可以使用栈来模拟递归过程。首先，建立一个栈，不断将问题压入栈中，直到问题被解决。具体步骤如下：

1.定义一个结构体，包含三个成员，分别代表盘子的大小、起始柱子和目标柱子。

2.按照递归的思路，将问题划分为多个子问题，并分别压入栈中，直到问题被分解到只有一个盘子时停止。

3.不断从栈中弹出问题，并依次解决它们，直到栈为空。对于每个问题，首先判断是否已经无法再分解，如果是，则直接移动盘子；如果不是，则先将子问题按照从小到大的顺序依次压入栈中。

下面是使用非递归方法解决汉诺塔问题的代码：

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

struct StackNode {
    int n;          // 盘子的大小
    char from, to;  // 起始柱子和目标柱子
    int step;       // 步数
};

struct Stack {
    struct StackNode *data; // 栈中存储的数据
    int max_size;           // 栈的大小
    int top;                // 栈顶位置
};

void init_stack(struct Stack *s, int max_size) {
    s->data = (struct StackNode *) malloc(max_size * sizeof(struct StackNode));
    s->max_size = max_size;
    s->top = -1;
}

void push(struct Stack *s, struct StackNode *x) {
    if (s->top == s->max_size - 1) {
        printf("Stack is full!\n");
        return;
    }
    s->top++;
    s->data[s->top] = *x;
}

void pop(struct Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty!\n");
        return;
    }
    s->top--;
}

struct StackNode *top(struct Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty!\n");
        return NULL;
    }
    return &(s->data[s->top]);
}

int is_stack_empty(struct Stack *s) {
    return s->top == -1;
}

void move(int n, char from, char to, int step) {
    printf("%c -> %c, Step %d\n", from, to, step);
}

void hanoi(int n, char from, char to) {
    struct Stack s;
    init_stack(&s, 100);
    struct StackNode node;
    node.n = n;
    node.from = from;
    node.to = to;
    node.step = 0;
    push(&s, &node);
    while (!is_stack_empty(&s)) {
        struct StackNode *cur = top(&s);
        if (cur->n == 1) {
            move(1, cur->from, cur->to, cur->step + 1);
            pop(&s);
        } else if (cur->n > 1) {
            if (is_stack_empty(&s)) {
                printf("Stack is empty!\n");
                break;
            }
            struct StackNode *next = top(&s);
            if (next->n != cur->n - 1) {
                node.n = cur->n - 1;
                node.from = cur->from;
                node.to = get_other_peg(cur->from, cur->to);
                node.step = cur->step;
                push(&s, &node);
            } else {
                move(1, cur->from, cur->to, cur->step + 1);
                pop(&s);
                if (!is_stack_empty(&s)) {
                    next = top(&s);
                    if (next->n != cur->n - 1) {
                        node.n = cur->n - 1;
                        node.from = get_other_peg(cur->from, cur->to);
                        node.to = cur->to;
                        node.step = cur->step + 1;
                        push(&s, &node);
                    } else {
                        move(1, cur->to, next->to, cur->step + 2);
                        pop(&s);
                    }
                } else break;
            }
        } else break;
    }
}

int main() {
    int n;
    printf("请输入汉诺塔的层数：");
    scanf("%d", &n);
    hanoi(n, 'A', 'C');
    return 0;
}

char get_other_peg(char a, char b) {
    switch (a) {
        case 'A':
            if (b == 'B') return 'C';
            if (b == 'C') return 'B';
        case 'B':
            if (b == 'A') return 'C';
            if (b == 'C') return 'A';
        case 'C':
            if (b == 'A') return 'B';
            if (b == 'B') return 'A';
    }
    return ' ';
}

这里使用了一个栈来模拟递归过程，具体实现可以参考代码注释。