开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。
算法介绍：
其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n - 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步 *** 作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2） *** 作，最后就能按规定完成汉诺塔的移动。
所以结果非常简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。
●汉诺塔算法的递归实现C++源代码
#include <fstream>
#include <iostream>
using namespace std
ofstream fout(“out.txt”)
void Move(int n,char x,char y)
{
fout<<“把”<<n<<“号从”<<x<<“挪动到”<<y<<endl
}
void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c)
else
{
Hannoi(n-1,a,c,b)
Move(n,a,c)
Hannoi(n-1,b,a,c)
}
}
int main()
{
fout<<“以下是7层汉诺塔的解法:”<<endl
Hannoi(7,‘a’,‘b’,‘c’)
fout.close()
cout<<“输出完毕！”<<endl
return 0
}
●汉诺塔算法的递归实现C源代码：
#include<stdio.h>
void hanoi(int n,char A,char B,char C)
{
if(n==1)
{
printf(“Move disk %d from %c to %c\n”,n,A,C)
}
else
{
hanoi(n-1,A,C,B)
printf(“Move disk %d from %c to %c\n”,n,A,C)
hanoi(n-1,B,A,C)
}
}
main()
{
int n
printf(“请输入数字n以解决n阶汉诺塔问题：\n”)
scanf(“%d”,&n)
hanoi(n,‘A’,‘B’,‘C’)
}
●汉诺塔算法的非递归实现C++源代码
#include <iostream>
using namespace std
//圆盘的个数最多为64
const int MAX = 64
//用来表示每根柱子的信息
struct st{
int s[MAX]//柱子上的圆盘存储情况
int top//栈顶，用来最上面的圆盘
char name//柱子的名字，可以是A，B，C中的一个
int Top()//取栈顶元素
{
return s[top]
}
int Pop()//出栈
{
return s[top--]
}
void Push(int x)//入栈
{
s[++top] = x
}
}
long Pow(int x, int y)//计算x^y
void Creat(st ta[], int n)//给结构数组设置初值
void Hannuota(st ta[], long max)//移动汉诺塔的主要函数
int main(void)
{
int n
cin >>n//输入圆盘的个数
st ta[3]//三根柱子的信息用结构数组存储
Creat(ta, n)//给结构数组设置初值
long max = Pow(2, n) - 1//动的次数应等于2^n - 1
Hannuota(ta, max)//移动汉诺塔的主要函数
system(“pause”)
return 0
}
void Creat(st ta[], int n)
{
ta[0].name = ‘A’
ta[0].top = n-1
//把所有的圆盘按从大到小的顺序放在柱子A上
for (int i=0i<ni++)
ta[0].s[i] = n - i
//柱子B，C上开始没有没有圆盘
ta[1].top = ta[2].top = 0
for (int i=0i<ni++)
ta[1].s[i] = ta[2].s[i] = 0
//若n为偶数，按顺时针方向依次摆放 A B C
if (n%2 == 0)
{
ta[1].name = ‘B’
ta[2].name = ‘C’
}
else //若n为奇数，按顺时针方向依次摆放 A C B
{
ta[1].name = ‘C’
ta[2].name = ‘B’
}
}
long Pow(int x, int y)
{
long sum = 1
for (int i=0i<yi++)
sum *= x
return sum
}
void Hannuota(st ta[], long max)
{
int k = 0//累计移动的次数
int i = 0
int ch
while (k <max)
{
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch = ta[i%3].Pop()
ta[(i+1)%3].Push(ch)
cout <<++k <<“: “ <<
“Move disk “ <<ch <<” from “ <<ta[i%3].name <<
” to “ <<ta[(i+1)%3].name <<endl
i++
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
if (k <max)
{
//把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
if (ta[(i+1)%3].Top() == 0 ||
ta[(i-1)%3].Top() >0 &&
ta[(i+1)%3].Top() >ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop()
ta[(i+1)%3].Push(ch)
cout <<++k <<“: “ <<“Move disk “
<<ch <<” from “ <<ta[(i-1)%3].name
<<” to “ <<ta[(i+1)%3].name <<endl
}
else
{
ch = ta[(i+1)%3].Pop()
ta[(i-1)%3].Push(ch)
cout <<++k <<“: “ <<“Move disk “
<<ch <<” from “ <<ta[(i+1)%3].name
<<” to “ <<ta[(i-1)%3].name <<endl
}
}
}
}
附录：主要源程序(1) Disk.java
package code
import java.awt.*
public class Disk extends Button {
int number//盘子的个数
public Disk(int number) {this.number = number
setBackground(Color.yellow)}
public int getNumber() {return number}}
(2) TowerPoint.java
package code
import java.awt.*
public class TowerPoint {
int x, y//塔上的点位置，即盘子的放置位置
boolean isHaveDisk//判断点上是否有盘子
Disk disk HannoiTower con
public TowerPoint(int x, int y, boolean boo) {this.x = x this.y = y isHaveDisk = boo}
public boolean getIsHaveDisk() {return isHaveDisk}
public void setIsHaveDisk(boolean boo) {isHaveDisk = boo}
public int getX() { return x } //获得点位置坐标
public int getY() { return y }
public void putDisk(Disk disk, HannoiTower con) {//在点上放盘子
this.con = concon.setLayout(null)//设置布局
this.disk = diskcon.add(disk)//加盘子到容器中
int w = disk.getBounds().width//获得盘子的长和宽 getBounds()以Rectangle对象的形式获取组件的边界
int h = disk.getBounds().height
disk.setBounds(x - w / 2, y - h / 2, w, h)//setBounds()移动组件并调整其大小，控件位置坐标，后面是宽度和高度
isHaveDisk = truecon.validate() }
public Disk getDisk() {return disk}}
(3) HannoiTower.java
package code
import javax.swing.*
import java.awt.*
public class HannoiTower extends JPanel{
TowerPoint point[]//塔上点数组
boolean move = false//判断是否移动
Disk disks[]//盘子数组
int diskNum = 0//定义盘子个数
int width, height//盘子的宽度和高度
char towerName[] = { 'A', 'B', 'C' }//塔名
TextArea infoArea
int autoNum = 1//计算步数
public HannoiTower(int number, int w, int h, char[] name, TextArea text) {towerName = namediskNum = numberwidth = wheight = h
infoArea = textsetLayout(null)
disks = new Disk[diskNum]//初始化盘子个数
//设置塔上的点属性
point = new TowerPoint[3 * diskNum]//塔上点的个数=3*盘子个数
int space = 20
for (int i = 0i <diskNumi++) {//第一根柱子上的点
point[i] = new TowerPoint(40 + width, 100 + space, false)//设置点的位置和没有盘子
space = space + height}
space = 20
for (int i = diskNumi <2 * diskNumi++) {//第二根柱子上的点
point[i] = new TowerPoint(200 + width, 100 + space, false)
space = space + height }
space = 20
for (int i = 2 * diskNumi <3 * diskNumi++){//第三根柱子上的点
point[i] = new TowerPoint(360 + width, 100 + space, false)
space = space + height }
//设置盘子属性
int tempWidth = width
int sub = (int) (tempWidth / diskNum)
for (int i = diskNum - 1i >= 0i--) {disks[i] = new Disk(i)
disks[i].setSize(tempWidth, height)//设置盘子的宽和高
tempWidth = tempWidth - sub}
for (int i = 0i <diskNumi++) {point[i].putDisk(disks[i], this)
}}
public void paint(Graphics g) {super.paint(g)
g.drawLine(point[0].getX(), point[0].getY(), point[diskNum - 1].getX(),point[diskNum - 1].getY())//画3根竖线
g.drawLine(point[diskNum].getX(), point[diskNum].getY(),
point[2 * diskNum - 1].getX(), point[2 * diskNum - 1].getY())
g.drawLine(point[2 * diskNum].getX(), point[2 * diskNum].getY(),
point[3 * diskNum - 1].getX(), point[3 * diskNum - 1].getY())
g.drawLine(point[diskNum - 1].getX() - width,
point[diskNum - 1].getY(), point[3 * diskNum - 1].getX()
+ width, point[3 * diskNum - 1].getY())
int leftx = point[diskNum - 1].getX() - width//画灰色矩形
int lefty = point[diskNum - 1].getY()
int w = (point[3 * diskNum - 1].getX() + width) - (point[diskNum - 1].getX() - width)
int h = height / 2
g.setColor(Color.gray)
g.fillRect(leftx, lefty, w, h)
g.setColor(Color.red)//画红点
int size = 4
for (int i = 0i <3 * diskNumi++) {
g.fillOval(point[i].getX() - size / 2, point[i].getY() - size / 2, size, size)}
g.drawString("" + towerName[0] + "塔", point[diskNum - 1].getX(),
point[diskNum - 1].getY() + 30)
g.drawString("" + towerName[1] + "塔", point[2 * diskNum - 1].getX(),
point[diskNum - 1].getY() + 30)
g.drawString("" + towerName[2] + "塔", point[3 * diskNum - 1].getX(),
point[diskNum - 1].getY() + 30)
g.drawString("将全部盘子从" + towerName[0] + "塔搬运到" + towerName[1] + "塔"+ towerName[2] + "塔", point[diskNum - 1].getX(),point[diskNum - 1].getY() + 80)}
/**
* 自动演示函数
*/
public void autoMoveDisk(int diskNum, char one, char two, char three) {//one塔1、two塔2、three塔3
if (diskNum == 1) //当盘子只有一个时
{infoArea.append(autoNum + ":" + one + "塔 ----->" + three + "塔\n")
autoNum++
Disk disk = getTopDisk(one)//获得塔1上最上面的盘子
int startI = getTopDiskPosition(one)//
int endI = getTopDiskUp(three)
if (disk != null) {point[endI].putDisk(disk, this)
point[startI].setIsHaveDisk(false)pause()}}
else {autoMoveDisk(diskNum - 1, one, three, two)
infoArea.append(autoNum + ":" + one + "塔 ----->" + three + "塔\n")
autoNum++
Disk disk = getTopDisk(one)
int startI = getTopDiskPosition(one)
int endI = getTopDiskUp(three)
if (disk != null) {point[endI].putDisk(disk, this)
point[startI].setIsHaveDisk(false)pause()}
autoMoveDisk(diskNum - 1, two, one, three)}}
/**
* 取最上方的盘子
*/
public Disk getTopDisk(char towerN) {//towerN塔名
Disk disk = null
if (towerN == towerName[0]) {
for (int i = 0i <diskNumi++) {
if (point[i].getIsHaveDisk() == true) {//判断是否有盘子
disk = point[i].getDisk()break}}}
if (towerN == towerName[1]) {
for (int i = diskNumi <2 * diskNumi++) {
if (point[i].getIsHaveDisk() == true) {
disk = point[i].getDisk()break}}}
if (towerN == towerName[2]) {
for (int i = 2 * diskNumi <3 * diskNumi++) {
if (point[i].getIsHaveDisk() == true) {
disk = point[i].getDisk()break}}}
return disk}
/**
* 在塔中获取盘子的放置位置
*/
public int getTopDiskUp(char towerN) {
int position = 0
if (towerN == towerName[0]) {
int i = 0
for (i = 0i <diskNumi++) {
if (point[i].getIsHaveDisk() == true) {
position = Math.max(i - 1, 0)
break}}
if (i == diskNum) {position = diskNum - 1}}
if (towerN == towerName[1]) {
int i = 0
for (i = diskNumi <2 * diskNumi++) {
if (point[i].getIsHaveDisk() == true) {
position = Math.max(i - 1, 0)break}}
if (i == 2 * diskNum) {position = 2 * diskNum - 1}}
if (towerN == towerName[2]) {int i = 0
for (i = 2 * diskNumi <3 * diskNumi++) {
if (point[i].getIsHaveDisk() == true) {
position = Math.max(i - 1, 0)break}}
if (i == 3 * diskNum) {position = 3 * diskNum - 1}}
return position}
/**
* 在塔中获取最上面盘子的位置
*/
public int getTopDiskPosition(char towerN) {
int position = 0
if (towerN == towerName[0]) {
int i = 0
for (i = 0i <diskNumi++) {
if (point[i].getIsHaveDisk() == true) {
position = ibreak}}
if (i == diskNum) {position = diskNum - 1}}
if (towerN == towerName[1]) {int i = 0
for (i = diskNumi <2 * diskNumi++) {
if (point[i].getIsHaveDisk() == true) {position = ibreak}}
if (i == 2 * diskNum) {position = 2 * diskNum - 1}}
if (towerN == towerName[2]) {int i = 0
for (i = 2 * diskNumi <3 * diskNumi++) {
if (point[i].getIsHaveDisk() == true) {
position = ibreak}}
if (i == 3 * diskNum) {position = 3 * diskNum - 1}}
return position}
public void pause() {
try {Thread.sleep(1000)// 1s移动1步} catch (InterruptedException e) {}}}
(4) Tower.java
package code
import java.awt.*
import java.awt.event.*
import javax.swing.*
public class Tower extends Frame implements ActionListener, ItemListener, Runnable {
HannoiTower tower
JButton renew, auto
Choice diskNumComBox
char towerName[] = { 'A', 'B', 'C' }
int diskNum, diskWidth, diskHeight
Thread thread
TextArea infoArea
public Tower() {
thread = new Thread(this)
diskWidth = 120diskHeight = 18
infoArea = new TextArea(15, 15)
infoArea.setText(null)
diskNumComBox = new Choice()//下拉列表
diskNumComBox.setName("diskNumComBox")//设置名字
diskNumComBox.setSize(300, 10)//设置列表大小
diskNumComBox.setFont(new java.awt.Font ("Dialog", 0, 11))//设置字体
diskNumComBox.setBackground(java.awt.Color.white)//设置下拉按钮的背景色
diskNumComBox.setForeground(java.awt.Color.black)//设置下拉按钮的前景色
for(int i=1i<=9i++){diskNumComBox.add(String.valueOf(i))}//设置盘子数目
diskNum = Integer.valueOf(diskNumComBox.getSelectedItem().toString())
tower = new HannoiTower(diskNum, diskWidth, diskHeight, towerName, infoArea)
renew = new JButton("重新开始")
auto = new JButton("自动演示")
renew.addActionListener(this)
auto.addActionListener(this)
diskNumComBox.addItemListener(this)
JPanel topPanel = new JPanel()//设置两个按钮和下拉按钮的布局，放于容器topPanel中
topPanel.add(auto, BorderLayout.WEST)
topPanel.add(renew, BorderLayout.CENTER)
topPanel.add(diskNumComBox, BorderLayout.EAST)
add(tower, BorderLayout.CENTER)//设置整体布局为边界布局
add(topPanel, BorderLayout.NORTH)
add(infoArea, BorderLayout.EAST)
addWindowListener(new WindowAdapter() {//关闭窗口时调用
public void windowClosing(WindowEvent e) {
System.exit(0)}})
setVisible(true)setBounds(40, 20, 700, 540)
validate()//是Container类中的方法，该方法用来更新容器中的布局}
public void actionPerformed(ActionEvent e) {//重置
if (e.getSource() == renew) {
if (!(thread.isAlive())) {//判断线程不活着
this.remove(tower)//Frame中的函数，重新构建，从此窗体移除指定的菜单栏。
infoArea.setText(null)
tower = new HannoiTower(diskNum, diskWidth, diskHeight, towerName, infoArea)
add(tower, BorderLayout.CENTER)
validate()}
else {}}
if (e.getSource() == auto) {//创建线程，自动演示
if (!(thread.isAlive())) {thread = new Thread(this)}
try {thread.start()} catch (Exception eee) {}}}
public void itemStateChanged(ItemEvent e) {
if (e.getSource() == diskNumComBox) {
if (!(thread.isAlive())) {
this.remove(tower)
infoArea.setText(null)
diskNum = Integer.valueOf(diskNumComBox.getSelectedItem().toString())
tower = new HannoiTower(diskNum, diskWidth, diskHeight, towerName, infoArea)
add(tower, BorderLayout.CENTER)
validate()}
else {}}}
public void run() {
this.remove(tower)
infoArea.setText(null)
tower = new HannoiTower(diskNum, diskWidth, diskHeight, towerName, infoArea)
add(tower, BorderLayout.CENTER)validate()
tower.autoMoveDisk(diskNum, towerName[0], towerName[1], towerName[2])}
public static void main(String args[]) {
new Tower()}}
public class Disk {private static int nDisks = 3
// 汉诺塔算法
public static void inDisk(int top,char from,char inner,char to) {
if(top == 1){
System.out.println("Disk1 from "+ from+" to "+ to)
}else{
inDisk(top-1,from,to,inner)
System.out.println("Disk"+top+" from "+ from+" to "+ to)
inDisk(top-1,inner,from,to)
}
}
public static void main(String[] args) {
inDisk(nDisks,'A','B','C')
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）