问题描述
一说到递归可能就会想到最经典的汉诺塔问题.
先把汉诺塔问题简短的描述下.假如有start ,tmp , end三个柱子.
1.初始条件.最开始是tmp和end为空,而start上面有按从大到小往上摆的盘子(塔状).
2.最终目标.实现把所有盘子放到end柱子上,顺序跟之前的start柱子一样.从大到小往上的塔状形.
3.限制条件.我们在搬动的时候可以把tmp柱子拿来临时用下,不过在搬动的任何时候不能出现小盘到大盘上面的情况.
解决思路
我们先考虑最简单的情况,假如只有一个盘子,就直接从start搬到目的地end.如果两个盘子则是先把小盘子放tmp,然后大盘子放end,最后再把tmp里的盘子放end.
假如有N个盘子时,我们可以这样想,底下最大的那个我们先不管.(因为最大的如果你把它放那不动,则可以无视它的,其他盘子可以在三个柱子上移来移去.它是最大嘛).
于是我们可以先想办法把start上的N-1个盘子搬到tmp上,然后把最大的那个搬end上,最后再想办法把tmp上的N-1个搬到end上.
于是当有盘子3个时,先把上面2个搬到tmp上,再把最大那个搬到end,最后再想办法把tmp上的2个搬end上来.
C++实现代码
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
int totalSteps = 0; //用来计算所有操作总数是多少
//下面这个函数就是算出具体步骤的
void Hanoi(int totalNum, string start, string tmp, string end)
{
if(totalNum == 1)
{
//如果只有一个盘了,则直接从开始的start柱子搬到目的柱子end
string stepInfo = "Move disk from " + start +
" to " + end;
cout<<stepInfo<<endl;
totalSteps++;
}
else
{
Hanoi(totalNum - 1, start,end, tmp); //步骤1.先把start上的totalNum - 1个盘子搬到tmp上
string stepInfo = "Move disk from " + start +
" to " + end; //步骤2.把start上剩下的那大那个盘子直接盘end柱子上
cout<<stepInfo<<endl;
totalSteps++;
Hanoi(totalNum - 1, tmp, start, end); //步骤3.把tmp柱子上totalNum -1个盘子搬到end柱子上
}
}
int main()
{
int totalDiskNum = 4;
Hanoi(totalDiskNum, "start",
"tmp",
"end");
cout<<totalSteps<<endl; //结果是15
return 0;
}
总的步骤数规律是2^N - 1.其中N是盘子总数
所以N为4时,2的4次方为16,减1就是15
分享到:
相关推荐
哈诺塔问题迭代算法和分析 非常有用的,比较难找
任意输入N个盘,在三个柱子上实现汉诺塔问题的非递归求解,用栈进行
1汉诺塔问题: 包括了三种实现方式。a传统递归;b非递归,用Stack;c非递归,直接根据通项式规律求出 2普里姆算法: 其思想是加点法,程序中用一个StringBuffer来记录已经被访问了点 3克鲁斯克尔算法: 其思想是加边...
汉诺塔问题是用递归方法求解的一个典型问题,在实际教学中,可以在传统教学方式的基础上,利用计算机辅助教学进行算法的模拟演示教学,使学生更容易接受和理解递归算法的思想,不但能提高学生的学习兴趣,而且还能...
算法设计与分析 汉诺塔 分治法 1、采用分治法的思想,编写程序解决汉诺塔问题Hanio(n,A,B,C)。 2、分别采用蛮力法和分治法编程计算an。 3、分别采用二路归并(分治法)、快速排序(分治法)和选择排序(蛮力法),...
利用二叉树法,实现汉诺塔的非递归,根据盘子数和第几步,快速得到每一步移动的操作,速度快,省内存。已经经过调试运行,算法思想参见http://wenku.baidu.com/view/81a05a80e53a580216fcfeba.html,本人源码是根据...
此算法用递归算求思想求解实现汉诺塔问题,内有注释
汉诺塔问题是一个经典的数学谜题和递归算法问题,最早出现在印度,后来由法国数学家爱德华·卢卡斯命名。问题的描述如下: ...解决汉诺塔问题不仅有助于理解递归算法的思想,也展示了问题分解和递归求解的技巧。
其实算法非常简单,当盘子的个数为n时,移动的次数应等于2^n – 1(有兴趣的可以自己证明试试看)。后来一位美国学者发现一... 汉诺塔问题也是程序设计中的经典递归问题,下面我们将给出递归和非递归的不同实现源代码。
经典递归蓝桥杯练习+递归与分治策略 算法总体思想自顶向下逐步分解的策略递归的概念汉诺塔问题求解+递归算法的设计方法
递归是计算机语言课程中经常遇到且较为重要的一个问题,对此问题的讲解是否清楚、是否真正掌握对日后的程序学习都会产生较大影响,本人将结合教学中讲解递归程序时使用的方法,探讨如何更好地理解递归思想,从而为学好...
数据结构(c语言) 对于汉诺塔的递归实现。在对学习数据结构递归的人,帮助他们对汉诺塔和递归思想的理解
算法设计与分析实验报告--分治与递归算法 内含二分搜索、汉诺塔问题、循环赛日程安排 算法设计思想
10.6.1 汉诺塔算法 312 10.6.2 汉诺塔求解 314 10.7 窃贼问题 315 10.7.1 窃贼问题算法 315 10.7.2 窃贼问题求解 317 10.8 马踏棋盘 320 10.8.1 马踏棋盘算法 320 10.8.2 马踏棋盘求解 321 10.9 八皇后问题...
通过棋盘覆盖、大整数乘法、循环赛日程表、快速排序、汉诺塔问题的解决基本掌握了分治法的算法思想,这里是学习实例的源代码和一些算法心得。
该word文档包含分治算法的思想,适用于用...经典实例(递归求累加,求阶乘、汉诺塔问题、快速排序算法、二分查找算法(折半查找算法)、归并排序算法、矩阵乘法和Strassen、大整数乘法、循环赛日程表)。 *无题目链接
│ ├── HanoiGames.php 汉诺塔游戏 │ ├── BidirectionalQueue.php 双向队列 │ ├── ColorBricks.php 彩色砖块 │ ├── GetCattle.php 牛年求牛 │ ├── OnlyNumbers....
java算法分析与设计之Hanoi塔问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,...
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...
5.5.2 汉诺塔 170 5.5.3 火车车厢重排 172 5.5.4 开关盒布线 176 5.5.5 离线等价类问题 178 5.5.6 迷宫老鼠 180 5.6 参考及推荐读物 188 第6章 队列 189 6.1 抽象数据类型 189 6.2 公式化描述 190 6.3 链表描述 194 ...