汉诺塔问题(Hanoi问题)的递归算法与非递归算法详解

2024-03-15 03:18

本文主要是介绍汉诺塔问题(Hanoi问题)的递归算法与非递归算法详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

递归算法分析如下,
设A上有n个盘子。
如果n=1,则将圆盘从A直接移动到C。
如果n=2,则:
(1)将A上的n-1(等于1)个圆盘移到B上;
(2)再将A上的一个圆盘移到C上;
(3)最后将B上的n-1(等于1)个圆盘移到C上。
如果n=3,则:
A)将A上的n-1(等于2,令其为n`)个圆盘移到B(借助于C),步骤如下:
(1)将A上的n`-1(等于1)个圆盘移到C上。
(2)将A上的一个圆盘移到B。
(3)将C上的n`-1(等于1)个圆盘移到B。
B)将A上的一个圆盘移到C。
C)将B上的n-1(等于2,令其为n`)个圆盘移到C(借助A),步骤如下:
(1)将B上的n`-1(等于1)个圆盘移到A。
(2)将B上的一个盘子移到C。
(3)将A上的n`-1(等于1)个圆盘移到C。到此,完成了三个圆盘的移动过程。

从上面分析可以看出,当n大于等于2时, 移动的过程可分解为三个步骤:
第一步 把A上的n-1个圆盘移到B上;
第二步 把A上的一个圆盘移到C上;
第三步 把B上的n-1个圆盘移到C上;
其中第一步和第三步是类同的。 当n=3时,第一步和第三步又分解为类同的三步,即把n`-1个圆盘从一个针移到另一个针上,这里的n`=n-1。




Hanoi塔问题中函数调用时系统所做工作

一个函数在运行期调用另一个函数时,在运行被调用函数之前,系统先完成3件事:

①将所有的实参、返回地址等信息传递给被调用函数保存。

②为被调用函数的局部变量分配存储区;

③将控制转移到被调用函数的入口。

从被调用函数返回调用函数前,系统也应完成3件事:

①保存被调用函数的结果;

②释放被调用函数的数据区;

③依照被调用函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时,按照“后调用先返回”的原则(LIFO),上述函数之间的信息传递和控制转移必须通过“栈”来实现,即系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就为其在栈顶分配一个存储区,每当从一个函数退出时,就释放其存储区,因此当前运行函数的数据区必在栈顶。堆栈特点:LIFO,除非转移或中断,堆栈内容的存或取表现出线性表列的性质。正是如此,程序不要求跟踪当前进入堆栈的真实单元,而只要用一个具有自动递增或自动递减功能的堆栈计数器,便可正确指出最后一次信息在堆栈中存放的地址。

一个递归函数的运行过程类型于多个函数的嵌套调用,只是调用函数和被调用函数是同一个函数。因此,和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层,则从主函数调用递归函数为进入第1层;从第i层递归调用本函数为进入下一层,即i+1层。反之,退出第i层递归应返回至上一层,即i-1层。为了保证递归函数正确执行,系统需设立一个“递归工作栈”,作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”,其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归,就产生一个新的工作记录压入栈顶。每退出一层递归,就从栈顶弹出一个工作记录,则当前执行层的工作记录必是递归工作栈栈顶的工作记录,称这个记录为“活动记录”,并称指示活动记录的栈顶指针为“当前环境指针”。
递归源码如下:
#include<stdio.h>
/*主程序*/
int hanoi(int,char,char,char);
int  main()
{
char a='A',b='B',c='C';
int dishes;

while(1)
{
printf("输入盘子个数:  ");
scanf("%d",&dishes);
hanoi(dishes,a,b,c);
}
return 0;
}

int hanoi(int dishs,char ap,char bp,char cp)

{
if  ( dishs == 1 )
printf("盘子从%c 移动到 %c /n",ap,cp);
else
{
hanoi(dishs - 1,ap,cp,bp );
printf("盘子从%c 移动到 %c/n",ap,cp);
hanoi(dishs - 1,bp,ap,cp);
}
return 0;
}

非递归算法概述
/*《数学营养菜》(谈祥柏 著)提供的一种方法,编了一个程序来实现。
*/
/*
算法介绍:
首先容易证明,当盘子的个数为n时,移动的次数应等于2^n - 1。
一位美国学者发现一种出人意料的方法,只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上。
根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放 A B C;
若n为奇数,按顺时针方向依次摆放 A C B。
(1)按顺时针方向把圆盘1从现在的柱子移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;
若圆盘1在柱子B,则把它移动到C;若圆盘1在柱子C,则把它移动到A。
(2)接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。
即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘
这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。
(3)反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。
*/
#include <iostream>
using namespace std;
const int MAX = 64; //圆盘的个数最多为64


struct st{ //用来表示每根柱子的信息

int s[MAX]; //柱子上的圆盘存储情况

int top; //栈顶,用来最上面的圆盘

char name; //柱子的名字,可以是A,B,C中的一个


int Top()//取栈顶元素

{
return s[top];
}
int Pop()//出栈

{
return s[top--];
}
void Push(int x)//入栈

{
s[++top] = x;
}
} ;

long Pow(int x, int y); //计算x^y

void Creat(st ta[], int n); //给结构数组设置初值

void Hannuota(st ta[], long max); //移动汉诺塔的主要函数


int main(void)
{
int n;
cin >> n; //输入圆盘的个数


st ta[3]; //三根柱子的信息用结构数组存储

Creat(ta, n); //给结构数组设置初值


long max = Pow(2, n) - 1;//动的次数应等于2^n - 1

Hannuota(ta, max);//移动汉诺塔的主要函数


system("pause");
return 0;
}

void Creat(st ta[], int n)
{
ta[0].name = 'A';
ta[0].top = n-1;
for (int i=0; i<n; i++) //把所有的圆盘按从大到小的顺序放在柱子A上

ta[0].s[i] = n - i;

ta[1].top = ta[2].top = 0;//柱子B,C上开始没有没有圆盘

for (int i=0; i<n; i++)
ta[1].s[i] = ta[2].s[i] = 0;

if (n%2 == 0) //若n为偶数,按顺时针方向依次摆放 A B C

{
ta[1].name = 'B';
ta[2].name = 'C';
}
else //若n为奇数,按顺时针方向依次摆放 A C B

{
ta[1].name = 'C';
ta[2].name = 'B';
}
}

long Pow(int x, int y)
{
long sum = 1;
for (int i=0; i<y; i++)
sum *= x;

return sum;
}

void Hannuota(st ta[], long max)
{
int k = 0; //累计移动的次数

int i = 0;
int ch;
while (k < max)
{
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子

ch = ta[i%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << "Move disk " << ch << " from " << ta[i%3].name << " to " << ta[(i+1)%3].name << endl;
i++;
//把另外两根柱子上可以移动的圆盘移动到新的柱子上

if (k < max)
{ //把非空柱子上的圆盘移动到空柱子上,当两根柱子都为空时,移动较小的圆盘

if (ta[(i+1)%3].Top() == 0 || ta[(i-1)%3].Top() > 0 && ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i-1)%3].name << " to " << ta[(i+1)%3].name << endl;
}
else
{
ch = ta[(i+1)%3].Pop();
ta[(i-1)%3].Push(ch);
cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i+1)%3].name << " to " << ta[(i-1)%3].name << endl;
}
}
}
}

 

这篇关于汉诺塔问题(Hanoi问题)的递归算法与非递归算法详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/810614

相关文章

Linux线程同步/互斥过程详解

《Linux线程同步/互斥过程详解》文章讲解多线程并发访问导致竞态条件,需通过互斥锁、原子操作和条件变量实现线程安全与同步,分析死锁条件及避免方法,并介绍RAII封装技术提升资源管理效率... 目录01. 资源共享问题1.1 多线程并发访问1.2 临界区与临界资源1.3 锁的引入02. 多线程案例2.1 为

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile:专业级归档工具2.zipfile:跨平台归档首选3.

解决pandas无法读取csv文件数据的问题

《解决pandas无法读取csv文件数据的问题》本文讲述作者用Pandas读取CSV文件时因参数设置不当导致数据错位,通过调整delimiter和on_bad_lines参数最终解决问题,并强调正确参... 目录一、前言二、问题复现1. 问题2. 通过 on_bad_lines=‘warn’ 跳过异常数据3

idea的终端(Terminal)cmd的命令换成linux的命令详解

《idea的终端(Terminal)cmd的命令换成linux的命令详解》本文介绍IDEA配置Git的步骤:安装Git、修改终端设置并重启IDEA,强调顺序,作为个人经验分享,希望提供参考并支持脚本之... 目录一编程、设置前二、前置条件三、android设置四、设置后总结一、php设置前二、前置条件

解决RocketMQ的幂等性问题

《解决RocketMQ的幂等性问题》重复消费因调用链路长、消息发送超时或消费者故障导致,通过生产者消息查询、Redis缓存及消费者唯一主键可以确保幂等性,避免重复处理,本文主要介绍了解决RocketM... 目录造成重复消费的原因解决方法生产者端消费者端代码实现造成重复消费的原因当系统的调用链路比较长的时

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性:有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的

python使用try函数详解

《python使用try函数详解》Pythontry语句用于异常处理,支持捕获特定/多种异常、else/final子句确保资源释放,结合with语句自动清理,可自定义异常及嵌套结构,灵活应对错误场景... 目录try 函数的基本语法捕获特定异常捕获多个异常使用 else 子句使用 finally 子句捕获所

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499