c语言 汉诺塔算法代码

汉诺塔算法代码攻略

什么是汉诺塔游戏？

汉诺塔是一种数学智力题，也是一个益智游戏。游戏中有三根柱子，中间的一根柱子固定不动，左边的柱子上有64枚盘子，呈金字塔形摆放，盘子大小不同，大的在下，小的在上。现在的任务是，将这64个盘子慢慢从左边的柱子上移到右边的柱子上。

算法实现思路

汉诺塔游戏大致思路为：将n-1个盘子从左边的柱子经由中间的柱子移到右边的柱子上，再将底部的最后一个盘子从左边的柱子移到右边的柱子上，最后将n-1个盘子从中间的柱子移到左边的柱子上。

我们可以利用递归算法来实现汉诺塔游戏。递归算法通常需要满足以下三个条件：

1. 基准情况：这是递归调用结束的条件。
2. 需要使用递归调用自身的情况。
3. 每次递归需要移动步骤相同，但是盘子编号不同的三个柱子。

在实现过程中，我们可以使用C语言来编写代码。

代码示例1

下面是使用C语言编写的汉诺塔游戏示例代码：

#include <stdio.h>

void move(int n, char a, char b, char c)
{
    if (n == 1)
    {
        printf("Move disk 1 from %c to %c\n", a, c);
    }
    else
    {
        move(n-1, a, c, b);
        printf("Move disk %d from %c to %c\n", n, a, c);
        move(n-1, b, a, c);
    }
}

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

代码中包含了递归函数move和主函数main。其中move函数用来完成移动盘子的操作，main函数则用来启动汉诺塔游戏，并获取游戏的盘子数量输入。

代码示例2

我们还可以使用非递归算法，通过栈的数据结构来实现汉诺塔游戏。下面是使用C语言编写的汉诺塔游戏示例代码：

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

typedef struct{
    int plate;
    char from;
    char to;
    char via;
}Step;

typedef struct{
    Step * content;
    int top;
    int max;
}Stack;

Stack * MakeStack(int max){
    Stack * s = (Stack *)malloc(sizeof(Stack));
    s->content = (Step *)malloc(sizeof(Step)*max);
    s->max = max;
    s->top = -1;
    return s;
}

void Push(Stack * s, Step c){
    if(s->top < s->max){
       s->top ++;
       s->content[s->top] = c;
    }
}

Step Pop(Stack * s){
    if(s->top >= 0){
        Step c = s->content[s->top];
        s->top--;
        return c;
    }
}

void Hanoi(int n){
    Stack * S = MakeStack(100);
    Push(S, (Step){n, 'A', 'C', 'B'});
    while(S->top >= 0){
        Step s = Pop(S);
        n = s.plate;
        if(n == 1) printf("Move disk 1 from %c to %c\n", s.from, s.to);
        else{
            Push(S, (Step){n-1, s.from, s.via, s.to});
            Push(S, (Step){1, s.from, s.to, s.via});
            Push(S, (Step){n-1, s.via, s.to, s.from});
        }
    }
}

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

代码中使用了两个结构体，一个是Step结构体用来保存移动盘子的起始位置，目标位置和缓冲位置，另一个是Stack结构体用来实现栈的数据结构，以完成非递归的汉诺塔游戏。