汉诺塔算法代码攻略
什么是汉诺塔游戏?
汉诺塔是一种数学智力题,也是一个益智游戏。游戏中有三根柱子,中间的一根柱子固定不动,左边的柱子上有64枚盘子,呈金字塔形摆放,盘子大小不同,大的在下,小的在上。现在的任务是,将这64个盘子慢慢从左边的柱子上移到右边的柱子上。
算法实现思路
汉诺塔游戏大致思路为:将n-1个盘子从左边的柱子经由中间的柱子移到右边的柱子上,再将底部的最后一个盘子从左边的柱子移到右边的柱子上,最后将n-1个盘子从中间的柱子移到左边的柱子上。
我们可以利用递归算法来实现汉诺塔游戏。递归算法通常需要满足以下三个条件:
- 基准情况:这是递归调用结束的条件。
- 需要使用递归调用自身的情况。
- 每次递归需要移动步骤相同,但是盘子编号不同的三个柱子。
在实现过程中,我们可以使用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结构体用来实现栈的数据结构,以完成非递归的汉诺塔游戏。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:c语言 汉诺塔算法代码 - Python技术站