【算法】递归、搜索与回溯——汉诺塔

2024-05-28 20:12

本文主要是介绍【算法】递归、搜索与回溯——汉诺塔,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题解:汉诺塔(递归、搜索与回溯算法)

目录

  • 1.题目
  • 2.题目背景(拓展了解)
  • 3.题解
  • 4.参考代码
  • 5.细节
  • 6.总结

1.题目

题目链接:LINK
在这里插入图片描述
在这里插入图片描述

2.题目背景(拓展了解)

汉诺塔问题是一个通过隐式使用递归栈来进行实现的一个经典问题,该问题最早的发明人是法国数学家爱德华·卢卡斯。

汉诺塔传说
传说印度某间寺院有三根柱子,上串64个金盘。寺院里的僧侣依照一个古老的预言,以上述规则移动这些盘子;预言说当这些盘子移动完毕,世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说,还是他受他人启发。若传说属实,僧侣们需要2^64 − 1步才能完成这个任务;若他们每秒可完成一个盘子的移动,就需要5845亿年才能完成。整个宇宙现在也不过137亿年。这个传说有若干变体:寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭,其中一说是位于越南的河内,所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。佛教中确实有“浮屠”(塔)这种建筑;有些浮屠亦遵守上述规则而建。“汉诺塔”一名可能是由中南半岛在殖民时期传入欧洲的。
在这里插入图片描述

与之相似的一个故事就是“棋盘放大米的故事”:
故事是这样的,最初一位大哥发明了一种玩具叫做围棋,这个围棋有64个格子组成,国王很高兴问发明者什么赏赐,发明者说到“第一个格子放1粒大米,第二个格子放2粒大米,第三个格子放4粒大米,此后每个格子都是前面的两倍大米,放满棋盘上的64个格子就好”,随后国王欣然接受,然而经过实践,即使把整个王国的大米搬过来放,也不能放满64个棋格。
在这里插入图片描述

这两个故事都揭示了一个道理——指数大爆炸

3.题解

我们枚举不同N情况下移动过程如下:
在这里插入图片描述
写递归的步骤
在这里插入图片描述

  • 函数头的设计
    除N = 1,情况外,所有N的情况都可以分为三步,即先把A柱上的前N-1个盘子放到B柱上,再把A柱的最下面一个盘子放到C上,再把B柱上的盘子放到C上。
    所以,解决此问题,我们只需要接受A、B、C、N的个数即可。

  • 函数体的设计
    先把A柱上的N-1个盘子放到B柱上,再把A的最下的一个盘子放到C上,再把B上的N-1个盘子放到C上。

  • 函数结束
    当N = 1时,不再满足上述三步走规律,只需要把那个盘子放到C上即可。

4.参考代码

class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {dfs(A,B,C,A.size());}void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n){//出递归if(n == 1){C.push_back(A.back());A.pop_back();return;}//1.先把A中的N-1个盘子借助C扔到B上dfs(A,C,B,n-1);//2.再把A中剩下的一个盘子扔到C上C.push_back(A.back());A.pop_back();//3.再把B中的N-1个盘子借助A扔到C上dfs(B,A,C,n-1);}
};

5.细节

思考:
如果我们把代码C.push_back(A.back())改成C.push_back(A[0])可以吗?为什么?

答:不行。 因为我们思考顺序与实际挪动顺序不一致。
虽然我们直觉上认为A.back()与A[0]在只剩下一个元素时候都表示的是最后的那个盘子,但是计算机运行的顺序跟我们脑子想的顺序并不一致,计算机先从最小的子问题(不可分割)的情况开始运算,而我们想的是先从最大问题的那个开始思考。
在只剩下一个元素的情况下A[0]和A.back()的确是一样的,但是计算机运行的时候并不是只有一个元素!!!

举个例子:
在这里插入图片描述

6.总结

汉诺塔作为经典的简单递归题目,是需要好好理解的,比如我上面提到的写递归的步骤以及为什么A.back()不能写成A[0]的问题。


EOF

这篇关于【算法】递归、搜索与回溯——汉诺塔的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这