河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。
设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小得叠在一起。 各圆盘从小到大编号1,2,...,n,。现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应该遵守以下移动规则。
规则(1):每次只能移动1个圆盘;
规则(2):任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则(3):在满足移动规则(1)和规则(2)的前提下,可将圆盘移至a,b,c中任一塔座上.
这个问题有一个简单的解法。假设塔座a,b,c排成一个三角形,a→b→c→a构成一顺时针循环。在移动圆盘过程中若是奇数次移动,则将最小的圆盘移到顺时针方向的下一塔座上;若是偶数次移动,则保持最小的圆盘不动。而在其他两个塔座之间将较小的圆盘移到另一塔座上去。
demo
import java.io.*;
public class Hanoi
{
public static void main(String args[]) throws IOException
{
int n;
BufferedReader buf;
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘数:");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n, 'A', 'B', 'C');
}
public void move(int n, char a, char b, char c)
{
if(n == 1)
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
else
{
move(n - 1, a, c, b);
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, b, a, c);
}
}
}
运行为:
请输入盘数:4
盘 1 由 A 移至 B
盘 2 由 A 移至 C
盘 1 由 B 移至 C
盘 3 由 A 移至 B
盘 1 由 C 移至 A
盘 2 由 C 移至 B
盘 1 由 A 移至 B
盘 4 由 A 移至 C
盘 1 由 B 移至 C
盘 2 由 B 移至 A
盘 1 由 C 移至 A
盘 3 由 B 移至 C
盘 1 由 A 移至 B
盘 2 由 A 移至 C
盘 1 由 B 移至 C
分享到:
相关推荐
### hutc-双色Hanoi塔问题参考代码详解 #### Hanoi塔问题简介 汉诺塔(Hanoi Tower)问题是一种经典的递归算法问题,在计算机科学领域被广泛用于教授递归概念。传统的汉诺塔问题涉及到三个柱子及不同大小的盘子,...
### Hanoi塔问题的一种非递归算法:深入解析与实现 #### 一、引言 Hanoi塔问题作为计算机科学领域内经典的递归问题之一,因其简洁性和挑战性而广受关注。通常,Hanoi塔问题的解决方案多采用递归算法,尽管其逻辑...
哈诺伊塔问题中的日期处理与存储过程设计 在哈诺伊塔问题中,我们遇到了日期处理和存储过程设计的问题。下面,我们将详细地剖析这两个问题,并提供相应的解决方案。 一、日期处理 在日期处理中,我们需要计算每个...
### Hanoi塔问题的一个公式解 #### 摘要与背景 Hanoi塔问题自1883年由法国数学家Édouard Lucas首次发明以来,一直是数学、计算机科学及认知科学领域内的经典问题之一。该问题最初的形式是拥有三个柱子(标记为1、...
### 双色汉诺塔问题解析与参考代码详解 #### 问题背景 汉诺塔(Hanoi Tower)问题是一个经典的递归问题,起源于一个古老的印度传说。传说中,寺庙中的僧侣们需要将64个金盘从一个塔座移动到另一个塔座上,中间可以...
### Hanoi塔问题非递归算法的形式推导 #### 一、引言 Hanoi塔问题,也称为汉诺塔问题,是一个经典的递归问题。传统上,人们使用递归算法来解决这个问题,因为它的递归性质使得问题的解决变得直观而简单。然而,...
Hanoi塔问题非递归算法的形式化开发,涉及到一系列计算机科学和数学领域的知识点,尤其是形式化方法、算法设计、递归与迭代、以及循环不变式等方面。Hanoi塔问题也被称为汉诺塔问题,是计算理论领域的一个经典问题,...
Description A、B、C 是3个塔座。开始时,在塔座A 上有一叠共n 个圆盘,这些圆盘自下而上, 由大到小地叠在一起。各圆盘从小到大编号为1,2,……,n,奇数号圆盘着蓝色,偶数号圆盘着红色,如图所示。...
本文将通过实验,使用问题归约法实现Hanoi塔问题的解决方案。 一、问题描述 Hanoi塔问题是一个经典的递归问题。它的描述是:在A、B、C三根针上,从A针上取下n个圆盘,并将其移到C针上,但是每次只能移动一个圆盘,...
### HANOI塔问题的非递归解 #### 背景与介绍 汉诺塔(Hanoi Tower)是一个经典的递归问题,在计算机科学中被广泛用于教学递归概念。传统上,这个问题通过递归算法解决,即一个函数在执行过程中调用自身的方式解决...
【标题】:“用C# Generator解决Hanoi塔问题”揭示了如何使用C#编程语言来构建一个自动化生成器,以高效地处理经典的汉诺塔问题。汉诺塔问题是一个著名的递归问题,它涉及到将一组盘子从一根柱子移动到另一根柱子,...
《Hanoi塔问题在DELPHI中的实现》 Hanoi塔问题,又称汉诺塔问题,是一个经典的递归算法问题,源于19世纪由法国数学家爱德华·卢卡斯提出。它涉及到三个柱子和一堆大小不一的圆盘,目标是将所有圆盘从一个柱子移动到...
在众多数据结构的问题中,Hanoi塔问题是一个经典案例,其教学不仅关系到理论知识的传授,还涉及到启发学生兴趣、提高实践能力等多个方面。 Hanoi塔问题在数据结构教学中具有一定的难度,它来源于古老的印度传说,...
hanoi塔问题--数据结构与算法必备,学习数据结构与算法始终要掌握的,希望对你能有所帮助!
### 再次Hanoi塔问题解析与参考代码详解 #### 一、问题背景与定义 **汉诺塔问题**是一个经典的递归问题,通常被用来教授递归算法的基础概念。传统汉诺塔问题要求将一系列不同大小的圆盘从一个柱子通过另一个柱子...
### 奇偶型Hanoi塔问题研究 #### 背景介绍 Hanoi塔问题是一种经典的递归问题,在计算机科学、数学以及其他相关领域中有着广泛的应用。传统的Hanoi塔问题涉及三个柱子(通常标记为A、B、C)以及一定数量的圆盘,...
hanoi塔问题的递归算法 汉诺塔(Hanoi Tower)问题是一个经典的递归问题,它涉及到将一组圆盘从一个起始柱子移动到另一个目标柱子,中间可以使用一个辅助柱子,但有一个限制:任何时候,大盘子不能放在小盘子的上面...
java算法分析与设计之Hanoi塔问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,...