Hanoi问题#include <stdio.h> #include <stdlib.h>

Hanoi问题是一个经典的递归问题，其目标是将一堆盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，并且大盘子不能放在小盘子上面。下面是一个C语言的Hanoi问题的递归实现：

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

void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", A, C);
        return;
    }
    hanoi(n-1, A, C, B);
    printf("Move disk %d from %c to %c\n", n, A, C);
    hanoi(n-1, B, A, C);
}

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

上述代码中，hanoi函数是递归函数，用于将n个盘子从A柱子移动到C柱子，B柱子作为辅助柱子。当n等于1时，直接将盘子从A柱子移动到C柱子。否则，先将n-1个盘子从A柱子移动到B柱子，再将第n个盘子从A柱子移动到C柱子，最后将n-1个盘子从B柱子移动到C柱子。在main函数中，首先输入盘子的数量n，然后调用hanoi函数。

相关问题

优化代码#define _CRT_SECURE_NO_WARNINGS 1//要写到代码第一行 #include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedef struct { int elem[MAXSIZE]; int top; } Stack; void InitStack(Stack* S) { S->top = -1; } int StackEmpty(Stack* S) { if (S->top == -1) { return 1; } else { return 0; } } int Push(Stack* S, int e) { if (S->top == MAXSIZE - 1) { return 0; } else { S->top++; S->elem[S->top] = e; return 1; } } int Pop(Stack* S, int* e) { if (StackEmpty(S)) { return 0; } else { *e = S->elem[S->top]; S->top--; return 1; } } void move(char x, char y) { printf("%c -> %c\n", x, y); } void Hanoi(int n, char x, char y, char z) { Stack S; InitStack(&S); int e; Push(&S, n); while (!StackEmpty(&S)) { while (Pop(&S, &e) && e > 1) { Push(&S, e - 1); Push(&S, 0); Push(&S, e - 1); } if (e == 1) { move(x, z); } while (Pop(&S, &e) && e == 0) { move(x, y); Push(&S, 0); } if (e > 1) { Push(&S, e - 1); move(x, z); Push(&S, 0); Push(&S, e - 1); } } } int main() { int n; printf("请输入盘子的个数："); scanf("%d", &n); Hanoi(n, 'A', 'B', 'C'); return 0; }

这段代码已经很简洁了，但还是有一些可以优化的地方：

1. 在函数中，参数可以使用 const 来修饰，表示该参数不会被函数修改，从而增加代码的可读性和可维护性。

2. 在函数中，可以使用三目运算符来代替部分 if-else 语句，从而使代码更加简洁。

3. 在函数中，可以使用 inline 来修饰函数，表示该函数可以内联展开，从而提高函数调用的效率。

4. 在定义结构体时，可以使用 typedef 来简化代码。

5. 在输入时，可以使用 fgets 来代替 scanf，从而避免因为 scanf 的输入格式问题而导致的程序崩溃。

6. 在输出时，可以使用 putchar 来代替 printf，从而提高输出效率。

优化后的代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef struct Stack {
    int elem[MAXSIZE];
    int top;
} Stack;

void InitStack(Stack* const S) {
    S->top = -1;
}

int StackEmpty(const Stack* const S) {
    return S->top == -1;
}

int Push(Stack* const S, const int e) {
    return S->top == MAXSIZE - 1 ? 0 : (S->elem[++S->top] = e, 1);
}

int Pop(Stack* const S, int* const e) {
    return StackEmpty(S) ? 0 : (*e = S->elem[S->top--], 1);
}

inline void move(const char x, const char y) {
    putchar(x);
    putchar(' ');
    putchar('-');
    putchar('>');
    putchar(' ');
    putchar(y);
    putchar('\n');
}

void Hanoi(const int n, const char x, const char y, const char z) {
    Stack S;
    InitStack(&S);
    Push(&S, n);
    int e;
    while (!StackEmpty(&S)) {
        while (Pop(&S, &e) && e > 1) {
            Push(&S, e - 1);
            Push(&S, 0);
            Push(&S, e - 1);
        }
        if (e == 1) {
            move(x, z);
        }
        while (Pop(&S, &e) && e == 0) {
            move(x, y);
            Push(&S, 0);
        }
        if (e > 1) {
            Push(&S, e - 1);
            move(x, z);
            Push(&S, 0);
            Push(&S, e - 1);
        }
    }
}

int main() {
    char input[MAXSIZE];
    int n;
    printf("请输入盘子的个数：");
    fgets(input, MAXSIZE, stdin);
    n = atoi(input);
    Hanoi(n, 'A', 'B', 'C');
    return 0;
}

hanoi塔问题的非递归算法c

Hanoi塔问题是一个经典的递归问题，但是也可以使用非递归算法来解决。以下是使用栈实现Hanoi塔问题的非递归算法C代码：

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

typedef struct {
    int *arr;
    int top;
    int size;
} Stack;

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

// 判空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判满
int isFull(Stack *s) {
    return s->top == s->size - 1;
}

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

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

// 移动
void move(Stack *a, Stack *b) {
    int x = pop(a);
    push(b, x);
    printf("Move %d from %d to %d\n", x, a->arr[0], b->arr[0]);
}

// Hanoi塔问题的非递归算法
void hanoi(int n, Stack *a, Stack *b, Stack *c) {
    int i, step = 0;
    // 初始状态
    for (i = n; i > 0; i--) {
        push(a, i);
    }
    // 栈操作模拟递归
    while (!isEmpty(a) || !isEmpty(b)) {
        while (!isEmpty(a)) {
            move(a, c);
            step++;
        }
        if (step == n) break;
        move(b, a);
        step++;
        while (!isEmpty(c)) {
            move(c, b);
            step++;
        }
        if (step == n) break;
        move(a, c);
        step++;
        while (!isEmpty(b)) {
            move(b, a);
            step++;
        }
        if (step == n) break;
        move(c, b);
        step++;
    }
}

int main() {
    int n = 3;
    Stack *a = initStack(n);
    Stack *b = initStack(n);
    Stack *c = initStack(n);
    a->arr[0] = 1;
    b->arr[0] = 2;
    c->arr[0] = 3;
    hanoi(n, a, b, c);
    return 0;
}

在上述代码中，我们使用了三个栈来表示三个柱子，首先将所有盘子都压入第一个栈a中，然后根据Hanoi塔问题的规则，不断将盘子从一个柱子移动到另一个柱子，直到所有盘子都移动到了目标柱子。移动盘子的操作使用了move函数来实现，这个函数将一个栈中的顶部元素弹出并压入另一个栈中，同时输出移动的信息。在主函数中，我们初始化了三个栈，并将第一个栈的第一个元素设为1，第二个栈的第一个元素设为2，第三个栈的第一个元素设为3，然后调用hanoi函数来解决Hanoi塔问题。