汉诺塔问题详解--递归实现_汉诺塔用递归工具计算算法 han-程序员宅基地

汉诺塔问题详解--递归实现

汉诺塔问题来源：
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

思考：
有三根柱子（A，B，C）。A柱子上面套着n个圆盘。这些圆盘大小各异，按从小到大的顺序自上而下摆放。

现在要把套在A柱上的n个圆盘全部移动到B柱上。并且移动圆盘时必须遵守下述规则：

一次只能移动柱子最上端的一个圆盘。
小圆盘上不能放大圆盘。
将一个圆盘从一根柱子移到另一根柱子，算是移动1次，那么，将n个圆盘全部从A移动到B至少需要移动几次呢？

首先：我们应该先从小汉诺塔入手。
一开始就考虑n个圆盘的话头脑会混乱，所以我们先缩小问题的规模，从3个圆盘开始思考。
即：暂时不考虑n个圆盘的问题，而是先找出3个圆盘的“3层汉诺塔”的解法。

经过尝试我们可以得到“3层汉诺塔”的解法，移动7次即可解决问题，即：

仔细观看这个移动过程，我们仿佛在做“重复且相似的事情”。之所以会有这种感觉是因为我们看到了一丝规律：
我们仔细看看图中①②③和⑤⑥⑦的移动过程：

①②③中，移动3次将2个圆盘从A柱移动到了C柱。
⑤⑥⑦中，移动3次将2个圆盘从C柱移动到了B柱。

再仔细看看移动2个圆盘的规律：

虽然移动的目的地不同，但是这两个行为动作却是非常相似的。而这种“移动2个圆盘”的动作不就是“2层汉诺塔”的解法吗。
用同样的思路我们可以进一步解决“5层汉诺塔”的问题，即：

首先，将4个圆盘从A柱移到C柱（解出4层）
然后，将（5个中）最大的圆盘从A柱移到B柱
最后，将4个圆盘从C柱移到B柱（解出4层）
“4层汉诺塔”，“3层汉诺塔”“2层汉诺塔”…也是用同样的解法。当然“1层汉诺塔”只需要移动一次圆盘就完成了。

通过这种方式我们可以总结出n层汉诺塔的解法：
我们用x,y,z来分别代表起点柱，目标柱，中转柱。注意：x,y,z并不具体代表A,B,C柱子，在不同情况下会不固定的对应A,B,C中的某一个。
解决n层汉诺塔的步骤，即：利用z柱将n个圆盘从x柱转移至y柱。
将n个圆盘从x柱，经由z柱中转，移到y柱时：

当n=0时：
* 不做任何操作
当n>0时：
* 首先，将n-1个圆盘从A柱移到C柱（解出n-1层）
* 然后，将（n个中）最大的圆盘从A柱移到B柱
* 最后，将n-1个圆盘从C柱移到B柱（解出n-1层）

由以上步骤可知：为了解出n层汉诺塔，要使用n-1层汉诺塔的解法。
那么，我们可以用H(n)表示解出n层汉诺塔所需的最少移动次数。
当n=0时，H(0)=0;
当n=1时，H(1)=1;
当n=2时，H(2)=H(1) + 1 + H(1) = 3;
当n=3时，H(3)=H(2) + 1 + H(2) = 7;
。
。
。
最终我们可以得到：

即：

这就是我们这个问题的递推公式。
当然，仔细的朋友已经发现：
0 = 1 - 1；
1 = 2 - 1；
3 = 4 - 1；
7 = 8 - 1；
。。。
即：H(n) = 2^n - 1;

前面的思路其实已经相当于伪代码了。既然我们的思路已经这么清晰了，那我们来尝试写写代码吧：

#include <iostream>
#include <cstdio>
using namespace std;
int hanoi(int n, char x, char y, char z);
int num = 0;
int main()
{
    
	int n;
	printf("请输入汉诺塔的层数：");
	cin >> n;
	hanoi(n, 'A', 'B', 'C');
	printf("共移动了 %d 次。\n", num);
	return 0;
}
// n表示要将多少个"圆盘"从起始柱子A移动至目标柱子B
// x表示起始柱子,y表示目标柱子,z表示过渡柱子
int hanoi(int n, char x, char y, char z)
{
    
	if (n == 0)
	{
    
	}
	else
	{
    
		hanoi(n - 1, x, z, y);// 递归处理,一开始的时候,先将n-1个盘子移至过渡柱z上
		printf("第%d步：  将 %d 号圆盘从 %c 移至 %c \n",num+1, n, x, y); // 然后再将最底下的大盘子直接移至目标柱子y
		num++;
		hanoi(n - 1, z, y, x); // 然后重复以上步骤,递归处理放在过渡柱z上的n-1个盘子,
							   // 这时x已经为空，所以x被当成过渡柱了
	}
	return 0;
}

假设我们算的是4层汉诺塔，运行结果如下：
在这里插入图片描述

本文链接：https://blog.csdn.net/qq_41879343/article/details/88671673

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

while循环&CPU占用率高问题深入分析与解决方案_main函数使用while(1)循环cpu占用99-程序员宅基地

文章浏览阅读3.8k次，点赞9次，收藏28次。直接上一个工作中碰到的问题，另外一个系统开启多线程调用我这边的接口，然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法，放到线上后发现确实是可以正常取到结果，但是一旦调用，CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了，类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99

【无标题】jetbrains idea shift f6不生效_idea shift +f6快捷键不生效-程序员宅基地

文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效

node.js学习笔记之Node中的核心模块_node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是-程序员宅基地

文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别，这些API绝大多数都被包装到了一个具名和核心模块中了，例如文件操作的 fs 核心模块，http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是

数学建模【SPSS 下载-安装、方差分析与回归分析的SPSS实现(软件概述、方差分析、回归分析)】_化工数学模型数据回归软件-程序员宅基地

文章浏览阅读10w+次，点赞435次，收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件

利用hutool实现邮件发送功能_hutool发送邮件-程序员宅基地

文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢？1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件

docker安装elasticsearch，elasticsearch-head，kibana，ik分词器_docker安装kibana连接elasticsearch并且elasticsearch有密码-程序员宅基地

文章浏览阅读867次，点赞2次，收藏2次。docker安装elasticsearch，elasticsearch-head，kibana，ik分词器安装方式基本有两种，一种是pull的方式，一种是Dockerfile的方式，由于pull的方式pull下来后还需配置许多东西且不便于复用，个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码

随便推点

Python 攻克移动开发失败！_beeware-程序员宅基地

文章浏览阅读1.3w次，点赞57次，收藏92次。整理 | 郑丽媛出品 | CSDN（ID：CSDNnews）近年来，随着机器学习的兴起，有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块，内置..._beeware

Swift4.0_Timer 的基本使用_swift timer 暂停-程序员宅基地

文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停

元素三大等待-程序员宅基地

文章浏览阅读986次，点赞2次，收藏2次。1.硬性等待让当前线程暂停执行，应用场景：代码执行速度太快了，但是UI元素没有立马加载出来，造成两者不同步，这时候就可以让代码等待一下，再去执行找元素的动作线程休眠，强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待