汉诺塔递归解法
/*
* 汉诺塔(Hanoi)问题递归解法
* 汉诺塔问题描述:
* 设三个分别命名为X,Y,Z的塔座,在塔座X上有一叠共n个圆盘,这些圆盘自下而上,
* 由大到小地叠在一起.各圆盘从小到大编号为,2,…,n,现要求将塔座X上的这一叠圆盘
* 移到塔座Z上，并仍按同样顺序叠排.
* 在移动圆盘时应遵守以下移动规则:
* 规则- 每次只能移动个圆盘;
* 规则- 任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
* 规则- 圆盘可以移至X,Y,Z中任意一塔座上.
* DATE: 08/25/2010
* 参考自严蔚敏等《数据结构(C语言版)》清华大学出版社
*/
#include <iostream>
#include <stdlib.h>
using namespace std;
// global variables definition
static int count = 0; // record the steps moved
// move disk(disk_number) from base_src to base_dst
void move(int disk_number, char base_src, char base_dst)
{
cout << ++count << ": move disk " << disk_number
<< " from " << base_src << " to " << base_dst << endl;
}
// move disk(1~disk_number) on base_x to base_z, base_y as an auxiliary base
void hanoi(int disk_number, char
base_x, char base_y, char base_z)
{
if(disk_number == 1)
// move disk 1 from base_x to base_z and terminate recursion,
// NOTE - disk 1 is the last one on base_x, as we assume all other disks
// have been already moved to base_y
move(1, base_x, base_z);
else
{
// 1. move disk(1~disk_number - 1) on base_x to base_y,
// base_z as an auxiliary base
hanoi(disk_number - 1, base_x, base_z, base_y);
// 2. move disk(disk_number) from base_x to base_z
move(disk_number, base_x, base_z);
