用栈实现汉诺塔

2024-07-14 04:05| 来源: 网络整理| 查看: 265

汉诺（Hanoi）塔问题

又称为河内塔问题。有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则：每次只允许移动一只盘，且大盘不得落在小盘上。如下图所示：

在如何编写递归程序（分治法）中，利用分治法递归程序提出了汉诺塔实现的方法，但是并没有在程序中真正地实现。由于汉诺塔的规则与栈的规则类似（先入后出），因此提出了用栈具体实现汉诺塔。

在栈的链式实现（C语言）中实现了栈的相关操作，在此不作讲解，只列出需要用到的操作函数。

实现代码：

typedef struct node //栈的结点结构 { int data; struct node *next; }*Link; typedef struct{ //栈顶作链表的头部 Link top; }*Stack; Stack init_stack()； // 定义栈 int push_stack(Stack s,int x)； // 变量x入栈 int pop_stack(Stack s,int &x)； // 出栈顶元素到x int pop_push(Stack sa,Stack sb); //栈sa出栈一次，数据入栈到sb void hanoi(int n,Stack sa,Stack sb,Stack sc) //把sa栈顶的n个元素按顺序放到栈sc中 void main() { int n; scanf("%d", &n); // 汉诺塔的层数 Stack sa = init_stack(); Stack sb = init_stack(); Stack sc = init_stack(); while(n-->0) // 初始化栈sa，代表最左边柱子和盘子 { push_stack(sa,i); } hanoi(n,sa,sb,sc); } void hanoi(int n,Stack sa,Stack sb,Stack sc) { if(n == 1) // 盘子数为1 pop_push(sa,sc); else { hanoi(n-1,sa,sc,sb); // 将栈sa的n-1个盘子顺序移到栈sb pop_push(sa,sc); // 将栈sa的第n个盘子移到栈sc hanoi(n-1,sb,sc,sa); // 将栈sb的n-1个盘子顺序移到栈sc } } int pop_push(Stack sa,Stack sb) { int x; if(sa->top ==NULL) { printf("栈空"); return 0; } else { pop_stack(sa,x); // 栈sa出栈 push_stack(sb,x); // 栈sb入栈 return 1; } }

栈sa首先被初始化，反序装入n~1的数字，代表盘子的大小顺序，程序运行后，栈sa元素都移到栈sc中，且顺序与栈sa初始化后顺序相同，因此从数据层面上实现了汉诺塔。由于实现汉诺塔需要的移动次数非常大，因此在输入汉诺塔层数时，尽量不要输入比较大的数，以免程序运行时间过长。

【本文地址】

公司简介

联系我们