汉诺塔问题——递归算法与非递归算法

一、问题描述
       

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

二、具体问题：

        给出一个二维数组V和change方法，要求给出递归过程代码。

change方法

void change(vector<vector<int>>& V, int a, int b)
{
	cnt++;
	int tmp = V[a].back();
	V[a].pop_back();
	V[b].push_back(tmp);
	cout << "(" << a+1 << "->" << b+1 << ")" << endl;
}

数组构建

int main()
{
	int n = 0;
	cin >> n;
	vector<vector<int>> V;
	V.resize(3);
	V[0].resize(n);
	for (int i = n; i > 0; --i)
	{
		V[0][i - 1] = n - i + 1;
	}
	solve(V,...);
}

我们要写出solve方法的实现

三：递归思路分析

        递归求解，要找子问题，从结果出发。要将假设5个盘子放到第三个柱子上。这里我们要想子问题。

首先：

1.把问题转化为先把四个盘子放到第二个柱子上，把最大的盘子5号放到第三个柱子上，再把这四个盘子放到第三个柱子上。

接下来我们要考虑怎么把四个盘子放到第二个柱子上。

2.把这个问题转化为先把三个盘子放到第三个柱子上，把4号盘子放到第二个柱子上，再把这三个盘子放到第二个柱子上。

已经发现了规律：

3.把这个问题转化为先把二个盘子放到第二个柱子上，把3号盘子放到第三个柱子上，再把这二个盘子放到第三个柱子上。

4.把这个问题转化为先把一个盘子放到第三个柱子上，把2号盘子放到第二个柱子上，再把这一个盘子放到第二个柱子上。

找到了子问题：当只需要整体移动一个盘子时候，就是递归过程的叶子结点。

根据上边的分析，我们的递归函数，需要传参：  数组V ， 整体移动几个盘子n，移动其实柱子from，移动终点柱子dest 。

注意，我们每次整体移动时候，都会转化为把除了

最大的盘子其他的放到第三者柱子上，这个第三者是除了from与dest的第三者。所以我们考虑用一个异或的方式来处理

以下是代码过程：

int p = 0^1^2;

void solve(vector<vector<int>>& V, int n,int from, int dest)
{
	if (n == 1){change(V, from, dest);return;}
	solve(V, n - 1, from, p ^ from ^ dest);
	change(V, from, dest);
	solve(V, n - 1, p ^ from ^ dest,dest);
}

整体代码：

#include<iostream>


using namespace std;
#include<vector>
#include<string>
int cnt = 0;

void change(vector<vector<int>>& V, int a, int b)
{
	cnt++;
	int tmp = V[a].back();
	V[a].pop_back();
	V[b].push_back(tmp);
	cout << "(" << a+1 << "->" << b+1 << ")" << endl;
}




int p = 0^1^2;

void solve(vector<vector<int>>& V, int n,int from, int dest)
{
	if (n == 1){change(V, from, dest);return;}
	solve(V, n - 1, from, p ^ from ^ dest);
	change(V, from, dest);
	solve(V, n - 1, p ^ from ^ dest,dest);
}	









int main()
{
	int n = 0;
	cin >> n;
	vector<vector<int>> V;
	V.resize(3);
	V[0].resize(n);
	for (int i = n; i > 0; --i)
	{
		V[0][i - 1] = n - i + 1;
	}
	solve(V, n, 0, 2);

	for (int i = 0; i < n; ++i)
	{
		cout << V[2][i] << "->";

	}
	cout<<endl << cnt << endl;
	return 0;
}

运行结果，以5为例：

四、非递归思路分析：

进行非递归分析就得找循环。从1开始逐步分析其中的循环结构。

比较容易知道，1和2是需要特殊处理的。接下来对于三个盘子，我们的步骤是：

n == 1 :     change(V, 0, 2);

n == 2 :

     change(V, 0, 1);
     change(V, 0, 2);
     change(V, 1, 2);

n==3 : 

     change(V, 0, 2);
     change(V, 0, 1);
     change(V, 2, 1);

     change(V, 0, 2);
     change(V, 1, 0);
     change(V, 1, 2);

     change(V, 0, 2);
 

        

对于四个盘子，我们要先把三个盘子放到第二个柱子上，移动最大盘子，再把这三个盘子放到第三个柱子上。

对于五个盘子，我们要先把四个盘子放到第二个柱子上，就得先把三个盘子放到第三个柱子上，然后移动第四个盘子到第二个柱子上，再把三个盘子放到第二个柱子上。

然后把第五个盘子放到第三个柱子上，接着就是第二个柱子上的四个盘子放到第三个柱子上，就得先把三个盘子放到第一个柱子上，

把第四个柱子放到第三个柱子上后，就是最后一步把一号柱子上的三个盘子放到第三个柱子上。

我们初步发现了规律：奇数盘子和偶数盘子是不一样的（三个盘子对于奇数应该放到原本柱子的后两个柱子上，偶数则是接下来的一个），我们要分类讨论这两种情况。每次把三个盘子整体移动过后，我们就得把剩下两个柱子上的小盘子放到大盘子上，（如果有柱子为空另说）

所以得出了代码逻辑：

void solve(vector<vector<int>>& V,int n,int now)
{
	while (1) {
		if (V[2].size() == n)return;
		if (n == 1) { change(V, 0, 2); cout << endl; return solve(V, n, 2); }
		else if (n == 2) {
			change(V, 0, 1);
			change(V, 0, 2);
			change(V, 1, 2);
			cout << endl;
			return solve(V, n, 2);
		}
		else if (n % 2 == 1) {
			change(V, now, (now + 2) % 3);
			change(V, now, (now + 1) % 3);
			change(V, (now + 2) % 3, (now + 1) % 3);
			change(V, now, (now + 2) % 3);
			change(V, (now + 1) % 3, now);
			change(V, (now + 1) % 3, (now + 2) % 3);
			change(V, now, (now + 2) % 3);
			if (!V[now].empty() && !V[(now + 1) % 3].empty()) {
				int big = now;
				int sma = (now + 1) % 3;
				if (V[big].back() < V[(now + 1) % 3].back()) big = (now + 1) % 3, sma = now;
				change(V, sma, big);
			}
			else if (V[now].empty() && V[(now + 1) % 3].empty()) {
			}
			else if (!V[now].empty())
			{
				change(V, now, (now + 1) % 3);
			}
			else {
				change(V, (now + 1) % 3, now);

			}
			now = (now + 2) % 3;
		}
		else {
			change(V, now, (now + 1) % 3);
			change(V, now, (now + 2) % 3);
			change(V, (now + 1) % 3, (now + 2) % 3);
			change(V, now, (now + 1) % 3);
			change(V, (now + 2) % 3, now);
			change(V, (now + 2) % 3, (now + 1) % 3);
			change(V, now, (now + 1) % 3);
			if (!V[now].empty() && !V[(now + 2) % 3].empty()) {
				int big = now;
				int sma = (now + 2) % 3;
				if (V[big].back() < V[(now + 2) % 3].back()) big = (now + 2) % 3, sma = now;
				change(V, sma, big);
			}
			else if (V[now].empty() && V[(now + 2) % 3].empty()) {
			}
			else if (!V[now].empty())
			{
				change(V, now, (now + 2) % 3);
			}
			else {
				change(V, (now + 2) % 3, now);

			}
			now = (now + 1) % 3;
		}
	}
}

整体代码

#include<iostream>


using namespace std;
#include<vector>
#include<string>

#define NUM 3
int cnt = 0;
void change(vector<vector<int>>& V, int a, int b)
{
	cnt++;
	int tmp = V[a].back();
	V[a].pop_back();
	V[b].push_back(tmp);
	string res;
	cout << "(" << a << "->" << b << ")" << endl;
}


void solve(vector<vector<int>>& V,int n,int now)
{
	while (1) {
		if (V[2].size() == n)return;
		if (n == 1) { change(V, 0, 2); cout << endl; return solve(V, n, 2); }
		else if (n == 2) {
			change(V, 0, 1);
			change(V, 0, 2);
			change(V, 1, 2);
			cout << endl;
			return solve(V, n, 2);
		}
		else if (n % 2 == 1) {
			change(V, now, (now + 2) % 3);
			change(V, now, (now + 1) % 3);
			change(V, (now + 2) % 3, (now + 1) % 3);
			change(V, now, (now + 2) % 3);
			change(V, (now + 1) % 3, now);
			change(V, (now + 1) % 3, (now + 2) % 3);
			change(V, now, (now + 2) % 3);
			if (!V[now].empty() && !V[(now + 1) % 3].empty()) {
				int big = now;
				int sma = (now + 1) % 3;
				if (V[big].back() < V[(now + 1) % 3].back()) big = (now + 1) % 3, sma = now;
				change(V, sma, big);
			}
			else if (V[now].empty() && V[(now + 1) % 3].empty()) {
			}
			else if (!V[now].empty())
			{
				change(V, now, (now + 1) % 3);
			}
			else {
				change(V, (now + 1) % 3, now);

			}
			now = (now + 2) % 3;
		}
		else {
			change(V, now, (now + 1) % 3);
			change(V, now, (now + 2) % 3);
			change(V, (now + 1) % 3, (now + 2) % 3);
			change(V, now, (now + 1) % 3);
			change(V, (now + 2) % 3, now);
			change(V, (now + 2) % 3, (now + 1) % 3);
			change(V, now, (now + 1) % 3);
			if (!V[now].empty() && !V[(now + 2) % 3].empty()) {
				int big = now;
				int sma = (now + 2) % 3;
				if (V[big].back() < V[(now + 2) % 3].back()) big = (now + 2) % 3, sma = now;
				change(V, sma, big);
			}
			else if (V[now].empty() && V[(now + 2) % 3].empty()) {
			}
			else if (!V[now].empty())
			{
				change(V, now, (now + 2) % 3);
			}
			else {
				change(V, (now + 2) % 3, now);

			}
			now = (now + 1) % 3;
		}
	}
}




int main()
{
	int n = 0;
	cin >> n;
	vector<vector<int>> V;
	V.resize(3);
	V[0].resize(n);
	for (int i = n; i > 0; --i)
	{
		V[0][i-1] = n-i+1;
	}

	solve(V,n, 0);

	for (int i = 0; i < n; ++i)
	{
		cout << V[2][i]<<"->";

	}
	cout << endl << cnt << endl;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/388063.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Spring 用法学习总结（一）之基于 XML 注入属性

Spring 用法学习总结（一）之基于 XML 注入属性

百度网盘&#xff1a; &#x1f449; Spring学习书籍链接 Spring学习 1 Spring框架概述2 Spring容器3 基于XML方式创建对象4 基于XML方式注入属性4.1 通过set方法注入属性4.2 通过构造器注入属性4.3 使用p命名空间注入属性4.4 注入bean与自动装配4.5 注入集合4.6 注入外部属性…
阅读更多...
auto.js教程（autojs教程、autox.js、autoxjs）笔记（二）环境搭建——2、安卓手机投屏软件scrcpy的安装和使用（scrcpy教程）

auto.js教程（autojs教程、autox.js、autoxjs）笔记（二）环境搭建——2、安卓手机投屏软件scrcpy的安装和使用（scrcpy教程）

参考文章&#xff1a;【自动化技术】Autojs从入门到精通 参考文章&#xff1a;AutoXJS开发入门简介菜鸟教程 参考文章&#xff1a;关于Auto.js的下架说明 参考文章&#xff1a;Auto.js 4.1.0 文档 文章目录 005--【环境搭建】2、安卓手机投屏软件scrcpy的安装和使用scrcpy官…
阅读更多...
【1024】我的创作纪念日

【1024】我的创作纪念日

机缘 1024天了&#xff0c;开始在这里学习编程知识、IT技能&#xff0c;CSDN让我发现了一群热爱学习和分享的小伙伴&#xff0c;也逐渐在这里稳定下来。 收获 不知不觉已经两年多过去了&#xff0c;通过不断的分享&#xff0c;不仅自己的知识技能得到了提升&#xff0c;能帮…
阅读更多...
腾讯云4核8G服务器多少钱？

腾讯云4核8G服务器多少钱？

腾讯云4核8G服务器多少钱&#xff1f;轻量应用服务器4核8G12M带宽一年446元、646元15个月&#xff0c;云服务器CVM标准型S5实例4核8G配置价格15个月1437.3元&#xff0c;5年6490.44元&#xff0c;标准型SA2服务器1444.8元一年&#xff0c;在txy.wiki可以查询详细配置和精准报价…
阅读更多...
SpringCloud-Hystrix：服务熔断与服务降级

SpringCloud-Hystrix：服务熔断与服务降级

8. Hystrix&#xff1a;服务熔断 分布式系统面临的问题 复杂分布式体系结构中的应用程序有数十个依赖关系&#xff0c;每个依赖关系在某些时候将不可避免失败&#xff01; 8.1 服务雪崩 多个微服务之间调用的时候&#xff0c;假设微服务A调用微服务B和微服务C&#xff0c;微服…
阅读更多...
B2科目二考试项目笔记

B2科目二考试项目笔记

B2科目二考试项目笔记 1 桩考1.1 右起点倒库1.2 移库&#xff08;左→右&#xff09;1.3 驶向左起点1.4 左起点倒库1.5 驶向右起点 2 侧方停车考试阶段&#xff08;从路边开始&#xff09;&#xff1a; 3 直角转弯4 坡道定点停车和起步5 单边桥6 通过限速限宽门7 曲线行驶8 连续…
阅读更多...
[数学建模] 计算差分方程的收敛点

[数学建模] 计算差分方程的收敛点

[数学建模] 计算差分方程的收敛点 差分方程&#xff1a;差分方程描述的是在离散时间下系统状态之间的关系。与微分方程不同&#xff0c;差分方程处理的是在不同时间点上系统状态的变化。通常用来模拟动态系统&#xff0c;如在离散时间点上更新状态并预测未来状态。 收敛点&…
阅读更多...
Selenium图表自动化开篇

Selenium图表自动化开篇

目录 前言&#xff1a; 使用 Canvas 或者 SVG 渲染 选择哪种渲染器 代码触发 ECharts 中组件的行为 前言&#xff1a; 图表自动化一直以来是自动化测试中的痛点&#xff0c;也是难点&#xff0c;痛点在于目前越来越多公司开始构建自己的BI报表平台但是没有合适的自动化测试…
阅读更多...
计算机设计大赛 深度学习OCR中文识别 - opencv python

计算机设计大赛 深度学习OCR中文识别 - opencv python

文章目录 0 前言1 课题背景2 实现效果3 文本区域检测网络-CTPN4 文本识别网络-CRNN5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习OCR中文识别系统 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;…
阅读更多...
使用bpmn-js 配置颜色

使用bpmn-js 配置颜色

本篇文章介绍如何使用bpmn-js给图例配置颜色。该示例展示了如何向BPMN图添加颜色的多种不同方法。 通过层叠设置颜色 这种方式比较简单&#xff0c;直接通过设置图片的CSS层叠样式就可实现。 .highlight-overlay {background-color: green; /* color elements as green */opa…
阅读更多...
Python算法探索：从经典到现代

Python算法探索：从经典到现代

引言 Python&#xff0c;作为一种功能强大的编程语言&#xff0c;一直是算法实现的首选工具。从经典的排序和查找算法到现代的机器学习和深度学习算法&#xff0c;Python都展现出了其强大的实力。接下来&#xff0c;我们将一起探索Python算法的经典与现代。 一、经典算法&#…
阅读更多...
关于Django的中间件使用说明。

关于Django的中间件使用说明。

目录 1.中间件2. 为什么要中间件&#xff1f;3. 具体使用中间件3.1 中间件所在的位置&#xff1a;在django的settings.py里面的MIDDLEWARE。3.2 中间件的创建3.3 中间件的使用 4. 展示成果 1.中间件 中间件的大概解释&#xff1a;在浏览器在请求服务器的时候&#xff0c;首先要…
阅读更多...
小区周边适合开什么店？商机无限等你来挖掘

小区周边适合开什么店？商机无限等你来挖掘

在小区周边开店&#xff0c;是许多创业者的首选。那么&#xff0c;到底开什么店才能抓住商机呢&#xff1f; 作为一名开店 5 年的资深创业者&#xff0c;我将以我的鲜奶吧为例&#xff0c;分享一些实用的经验和见解。 我的鲜奶吧采用了鲜奶吧酸奶店结合体的模式&#xff0c;产…
阅读更多...
操作 Docker 存储卷的常用指令汇总

操作 Docker 存储卷的常用指令汇总

1. 什么是存储卷&#xff1f; 存储卷就是将宿主机的本地文件系统中存在的某个目录直接与容器内部的文件系统上的某一目录建立绑定关系。使得可以在宿主机和容器内共享数据库内容&#xff0c;让容器直接访问宿主机中的内容&#xff0c;也可以宿主机向容器写入内容&#xff0c;容…
阅读更多...
基于函数计算AIGC图片识别

基于函数计算AIGC图片识别

目录 在 OSS 中建立图片目录 在函数计算中基于模板创建ImageAI应用 体验ImageAI图像识别效果 我们不但可以基于函数计算创建AIGC应用&#xff0c;实现以文生图&#xff0c;同时我们也可以基于函数计算创建ImageAI应用&#xff0c;通过简单几步实现对图片中对象的识别。下面我…
阅读更多...
【初学者必看】迈入Midjourney的艺术世界：轻松掌握Midjourney的注册与订阅！

【初学者必看】迈入Midjourney的艺术世界：轻松掌握Midjourney的注册与订阅！

文章目录 前言一、Midjourney是什么二、Midjourney注册三、新建自己的服务器四、开通订阅 前言 AI绘画即指人工智能绘画&#xff0c;是一种计算机生成绘画的方式。是AIGC应用领域内的一大分支。 AI绘画主要分为两个部分&#xff0c;一个是对图像的分析与判断&#xff0c;即…
阅读更多...
qt“五彩斑斓“ opengl

qt“五彩斑斓“ opengl

本篇文章我们来描述一下opengl相关知识 我们先看一下opengl渲染的效果 很漂亮&#xff1f; 那下面就来介绍一下这么漂亮的opengl OpenGL&#xff08;Open Graphics Library&#xff09;是一个跨平台的图形编程接口&#xff0c;用于渲染2D和3D图形。它提供了一系列函数和数据结…
阅读更多...
小白学习Halcon100例:如何利用动态阈值分割图像进行PCB印刷缺陷检测?

小白学习Halcon100例:如何利用动态阈值分割图像进行PCB印刷缺陷检测?

文章目录 *读入图片*关闭所有窗口*获取图片尺寸*根据图片尺寸打开一个窗口*在窗口中显示图片* 缺陷检测开始 ...*1.开运算 使用选定的遮罩执行灰度值开运算。*2.闭运算 使用选定的遮罩执行灰度值关闭运算*3.动态阈值分割 使用局部阈值分割图像显示结果*显示原图*设置颜色为红色…
阅读更多...
C语言习题----不同版本的差别

C语言习题----不同版本的差别

这个程序数组越界&#xff0c;但是结果是死循环&#xff1b; &#xff08;1&#xff09;死循环的这种情况只会在debug--x86的版本才会出现&#xff0c;其他版本不会出现&#xff1b;这种情况会在特定的情况下发生&#xff0c;和环境有和大的关系&#xff0c;不同的编译器对于内…
阅读更多...
lv15 平台总线驱动开发——ID匹配 3

lv15 平台总线驱动开发——ID匹配 3

一、ID匹配之框架代码 id匹配&#xff08;可想象成八字匹配&#xff09;&#xff1a;一个驱动可以对应多个设备 ------优先级次低&#xff08;上一章名称匹配只能1对1&#xff09; 注意事项&#xff1a; device模块中&#xff0c;id的name成员必须与struct platform_device中…
阅读更多...
最新文章

Copyright @ 2022~2023