本文目录一览：
用java编写hanoi塔的非递归算法。
这是个好问题，很少看到有人写汉诺塔的非递归...其实只要先写出递归，然后把递归的每一步要做的事情记录在一个栈里面就可以了
public class Test {
private static void emitStep(int source, int dest) {
System.out.println(source + " - " + dest);
}
static class Step {
Step(int n, int s, int d, int t) {
this.n = n;
source = s;
dest = d;
temp = t;
}
int n, source, dest, temp;
}
private static void hanoi(int n, int source, int dest, int temp) {
java.util.StackStep steps = new java.util.StackStep();
steps.add(new Step(n, source, dest, temp));
while (steps.empty() == false) {
Step step = steps.pop();
if (step.n == 1) {
emitStep(step.source, step.dest);
continue;
}
steps.push(new Step(step.n - 1, step.temp, step.dest, step.source));
steps.push(new Step(1, step.source, step.dest, 0));
steps.push(new Step(step.n - 1, step.source, step.temp, step.dest));
}
}
public static void main(String[] args) {
hanoi(3, 1, 3, 2);
}
}
汉诺塔非递归的写法
以前写过
#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=0; in; i++)
ta[0].s[i] = n - i;
//柱子B，C上开始没有没有圆盘
ta[1].top = ta[2].top = 0;
for (int i=0; in; i++)
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=0; iy; i++)
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;
}
}
}
}
谁会汉诺塔非递归的编程（java），并真正了解含义
public class Hannuota {
private int n;//储存盘子个数
public Hannuota(int n){
this.n = n;
}
public void function(){
//初始化三个柱子，A是开始堆满盘子的柱子，C是目标柱子
Pillar a = new Pillar(n,n,"A");
Pillar b = new Pillar(n,"B");
Pillar c = new Pillar(n,"C");
//把三个柱子按顺序排好，详见后面的算法那里的解释
Pillar[] pillars = new Pillar[3];
pillars[0] = a;
if(n%2==0){
pillars[1] = b;
pillars[2] = c;
}else{
pillars[1] = c;
pillars[2] = b;
}
//开始移动，k用来计数，移动次数为2^n-1,至于为什么，我不太清楚，
//反正有人证明过。i是用来保存最小那个盘子正在哪跟柱子上的。
int i=0;
for(int k=0;k(int)Math.pow(2, n)-1;){
int min;
//将最小的盘子顺时针移动一个柱子
min = pillars[i%3].Pop();
pillars[(i+1)%3].Push(min);
System.out.println(pillars[i%3]+"-"+pillars[(i+1)%3]);
k++;
i++;
//这个IF好像可以不要，当时写的，后面忘了删除。
if(k(int)Math.pow(2, n)-1){
//如果，剩下两根柱子中，某一根为空，则一定是非空那根中最上面个盘子
//移动到空的那个柱子上。若两根都不为空，则把编号小的一个盘子
//移动到另外跟柱子上
if(!pillars[(i-1)%3].isEmpty()(pillars[(i+1)%3].isEmpty()||pillars[(i+1)%3].Top()pillars[(i-1)%3].Top())){
min=pillars[(i-1)%3].Pop();
pillars[(i+1)%3].Push(min);
System.out.println(pillars[(i-1)%3]+"-"+pillars[(i+1)%3]);
}else{
min=pillars[(i+1)%3].Pop();
pillars[(i-1)%3].Push(min);
System.out.println(pillars[(i+1)%3]+"-"+pillars[(i-1)%3]);
}
k++;
}
}
}
//主函数，用来测试的。3表示3个盘子。
public static void main(String args[]){
new Hannuota(3).function();
}
}
class Pillar{//构造一个新类，表示柱子，实际是当一个栈在用
private int[] s;
private int top;
private String name;
public String toString(){
return name;
}
//这个构造函数用来构造BC两个柱子，下面那个用来构造柱子A。其实也可以写成一个构造函数。
public Pillar(int max,String name){
s = new int[max];
top = -1;
this.name = name;
for(int i=0;i s[i] = max+1;
}
}
public Pillar(int n,int max,String name){
s = new int[max];
top = n-1;
this.name = name;
for(int i=0;i s[i] = max - i;
}
}
//这后面这些就是栈的基本方法了，不用介绍了吧
public boolean isEmpty(){
return top==-1?true:false;
}
public int Top (){
return s[top];
}
public int Pop(){
return s[top--];
}
public void Push(int x){
s[++top] = x;
}
}
算法是这个
首先容易证明，当盘子的个数为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）操作，最后就能按规定完成汉诺塔的移动。
这玩意要非递归真麻烦。需不需要加点注释？
