用c语言写一个汉诺塔的递归

函数。

好的，以下是 C 语言实现汉诺塔的递归函数：

#include <stdio.h>

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

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

以上代码中，Hanoi 函数接收 4 个参数：n 表示当前层数，A、B、C 分别表示 3 个柱子的编号。当 n 等于 1 时，直接将 A 柱子上的最后一个盘子移动到 C 柱子上。移动 n 层时，先将上面 n-1 层从 A 柱子移动到 B 柱子上，在将 A 柱子上的最后一层移动到 C 柱子上，最后再将 B 柱子上的 n-1 层移动到 C 柱子上。

相关问题

用c语言写一个汉诺塔

汉诺塔是一个经典的递归问题，通常用三个柱子和一堆盘子来描述，目标是将所有的盘子从第一个柱子移动到第三个柱子，但任何时候都只能移动一个盘子，并且大盘子不能放在小盘子上面。以下是使用 C 语言实现汉诺塔算法的一个简单版本：

#include <stdio.h>

// 定义函数，表示移动n个盘子
void hanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n > 0) { // 递归的基本条件
        // 移动前n-1个盘子到辅助杆
        hanoi(n - 1, from_rod, aux_rod, to_rod);
        
        // 将最大的盘子移到目标杆
        printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
        
        // 最后将n-1个盘子从辅助杆移动到目标杆
        hanoi(n - 1, aux_rod, to_rod, from_rod);
    }
}

int main() {
    int num_disks; // 盘子的数量
    printf("Enter the number of disks: ");
    scanf("%d", &num_disks);

    // 开始游戏
    hanoi(num_disks, 'A', 'C', 'B'); // A代表源，C代表目标，B代表辅助

    return 0;
}

当你运行这个程序并输入盘子的数量时，它会按照汉诺塔规则依次打印出移动每个盘子的步骤。

用C语言写一个非递归汉诺塔

下面是使用 C 语言编写的非递归汉诺塔的代码：

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

// 定义一个栈结构体
typedef struct {
    int *data;  // 栈的数据存储区
    int top;    // 栈顶指针
    int size;   // 栈的容量
} Stack;

// 初始化栈
void initStack(Stack *stack, int size) {
    stack->data = (int *) malloc(sizeof(int) * size);
    stack->top = -1;
    stack->size = size;
}

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

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

// 入栈操作
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("Stack overflow!\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 出栈操作
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack->data[stack->top--];
}

// 非递归实现汉诺塔移动操作
void hanoi(int n) {
    Stack s1, s2, s3;       // 定义三个栈
    initStack(&s1, n);      // 初始化第一个栈
    initStack(&s2, n);      // 初始化第二个栈
    initStack(&s3, n);      // 初始化第三个栈
    int i, x, from, to, tmp;    // 定义临时变量
    for (i = n; i >= 1; i--) {
        push(&s1, i);       // 初始化第一个栈
    }
    if (n % 2 == 0) {       // 判断奇偶性
        tmp = s2.top;
        s2.top = s3.top;
        s3.top = tmp;
        from = 1;
        to = 2;
    } else {
        tmp = s1.top;
        s1.top = s3.top;
        s3.top = tmp;
        from = 1;
        to = 3;
    }
    int step = 0;
    while (s3.top != n - 1) {
        switch (step % 3) {
            case 0:     // 第一步
                if (!isEmpty(&s1)) {
                    x = pop(&s1);
                    push(&s2, x);
                    printf("%d -> %d\n", from, to);
                } else {
                    x = pop(&s2);
                    push(&s1, x);
                    printf("%d -> %d\n", to, from);
                }
                if (x % 2 == 0) {
                    if (from == 1) {
                        to = 3;
                    } else {
                        to = 1;
                    }
                } else {
                    if (from == 1) {
                        to = 2;
                    } else {
                        to = 1;
                    }
                }
                from = 3 - from - to;
                break;
            case 1:     // 第二步
                if (!isEmpty(&s1) && (isEmpty(&s2) || s1.data[s1.top] < s2.data[s2.top])) {
                    x = pop(&s1);
                    push(&s2, x);
                    printf("%d -> %d\n", from, to);
                } else {
                    x = pop(&s2);
                    push(&s1, x);
                    printf("%d -> %d\n", to, from);
                }
                if (x % 2 == 0) {
                    if (from == 1) {
                        to = 3;
                    } else {
                        to = 1;
                    }
                } else {
                    if (from == 1) {
                        to = 2;
                    } else {
                        to = 1;
                    }
                }
                from = 3 - from - to;
                break;
            case 2:     // 第三步
                if (!isEmpty(&s1)) {
                    x = pop(&s1);
                    push(&s3, x);
                    printf("%d -> %d\n", from, to);
                } else {
                    x = pop(&s3);
                    push(&s1, x);
                    printf("%d -> %d\n", to, from);
                }
                if (x % 2 == 0) {
                    if (from == 1) {
                        to = 3;
                    } else {
                        to = 1;
                    }
                } else {
                    if (from == 1) {
                        to = 2;
                    } else {
                        to = 1;
                    }
                }
                from = 3 - from - to;
                break;
        }
        step++;
    }
}

int main() {
    int n;
    printf("Enter the number of disks: ");
    scanf("%d", &n);
    hanoi(n);
    return 0;
}

这个非递归算法模拟了汉诺塔的移动过程，使用了三个栈来模拟三个柱子，通过不断出栈和入栈操作，实现了汉诺塔的移动。