Hanoi塔问题，以前都是用递归实现它，怎么用迭代呢？

Question

以前用递归实现后就没再想过还能用迭代，
现在想来似乎有点难理解了。想知道迭代的思想，或者有贴出迭代代码的（带注释）是先用递归的思想想出模式后，再转化成迭代代码呢？（只有这样了？）谢谢。顺便我有个帖沉了，没人回答，现在送分了。
http://community.csdn.net/Expert/topic/4634/4634196.xml?temp=.8235437

Answer 1

在百度搜了，听说是任何递归都能转化成迭代，我想应该是这样的，因为原来的一些语言还有不支持递归的呢。有人用C++写了迭代的代码，不过没有注释。如下，有谁能帮忙解释下他的思想吗，谢谢#include <stack>
#include <iostream>struct element{
    unsigned char number; // 一个数字，为了节省，限制在255以内
    char from, to, buff;    element(unsigned char num, char f, char t, char b) :
        number(num),from(f),to(t),buff(b){}
};typedef std::stack<element> han_stack;han_stack stack;void move(char from, char to)
{
    std::cout<<"move the top disk from "<<from<<" to "<<to<<std::endl;
}inline void push(unsigned n, char f, char t, char b)
{
    element e(n,f,t,b);
    stack.push(e);
}
void hannoi()
{
    while(!stack.empty()){
        element tos(stack.top());
        stack.pop();
        if(tos.number==1)
            move(tos.from,tos.to);
        else{
            push(tos.number-1,tos.buff,tos.to,tos.from);
            push(1,tos.from,tos.to,0); //ther 4th is not used
            push(tos.number-1,tos.from,tos.buff,tos.to);
        }
    }
}

Answer 2

任何递归都可以转化成迭代是对的。可以通过模拟计算机底层实现来证明。不怕麻烦的话，你可以自己实现一个递归栈，这种方法算是迭代。我以前用C实现过这个问题的一个算法，使用位操作，塔片的数量最多为long的位数（64位），虽然不是很大，但对现在计算机的处理能力来说应该足够大了。效率可能不是最好的，关键是代码很短，大概四十行的样子。需要的话我可以帮你找找，不知道还没有了。

Answer 3

java帮你重写了一下
public class Han {
    public static class Element{
        int number; 
        char from, to,buffer;        public Element(int num, char f, char t,char buffer){
            this.number=num;
            this.from=f;
            this.to=t;  
            this.buffer=buffer;
        }
        public void out(){
            System.out.println("move the top disk from "+from+" to "+to);
        }
    };
    public static void main(String[] args){
        Stack stack=new Stack();
        stack.push(new Element(3,'A','C','B'));;
        hannoi(stack);
    }    static void hannoi(Stack stack)
    {
        while(!stack.empty()){
            Element ele=(Element) stack.pop();
            //stack.pop();
            if(ele.number==1)
                ele.out();
            else{
                stack.push(new Element(ele.number-1,ele.buffer,ele.to,ele.from));
                stack.push(new Element(1,ele.from,ele.to,(char)0)); //ther 4th is not used
                stack.push(new Element(ele.number-1,ele.from,ele.buffer,ele.to));
            }
        }
    }
}

Answer 4

//Nonrecursive funcion for the towers of Hanoi promblem
//By 呵呵，我的学号#include <iostream>
#include <string>using namespace std;void OneStep(unsigned n, unsigned long count, int x, int y, int z)
{//compute the operation in a certain step
   for(int zero=0; !(count>>zero & 1); zero++)   //compute the length of zero sequence of count from right end
      ;
   for(int i=n-1; i>zero; i--)
      if(count & 1<<i)   //correspond to the final step in a recursive function
      {
         int temp=x;
         x=z;
         z=temp;
      }
      else            //the first step in a recursive function
      {
         int temp=y;
         y=z;
         z=temp;
      }
   cout<<x<<"->"<<y<<endl;   //the middle step in the recursive function
}void TowersOfHanoi(int n)
{//compute each step separately
   for(unsigned long count=1; !(count>>n); count++)
      OneStep(n, count, 1, 2, 3);
}void main()
{
   int n;   cout<<"Please enter a integer:";
   cin>>n;
   if(n>8*8)   //too long to compute
      cout<<"Sorry, this number is too large.";
   cout<<endl;
   TowersOfHanoi(n);
}//当前学算法时写的，算法还勉勉强强，真正的实现只有二十几行，但是代码质量很糟糕。

Answer 5

public class T
{
public static void main(String[] args)
{
int rings,last,next = 0,width;
int[] z = new int[500];
int[] s = new int[3];

if (args.length != 1) return ;
try {
rings = Integer.parseInt(args[0]);
width = rings + 1;
}catch(NumberFormatException e)
{
System.out.println("please input a integer!");
return ;
}

 for(int x=1;  x  <=rings;  x++)    /*  put  rings  on  first  peg  */
          z[x]=width-x;
   for(int x=0;  x  <=2*width;  x+=width)    /*  set  base  for  each  peg    */
          z[x]=1000;
 
/*  if  even  number  of  rings,  put  first  ring  on  second  peg;  if  odd,  on  third  */
 
  if(rings%2==0)
          {
          last=1;  s[2]=0;  s[1]=1;
          z[width+1]=z[rings];
          }
  else
          {
          last=2;  s[1]=0;  s[2]=1;
          z[2*width+1]=z[rings];
          }
 
  System.out.println("from  1  to  " + (last+1));  
 
  s[0]=rings-1;
 
  while(s[0]!= 0 || s[1]!= 0)    /*  while  first  and  second  pegs  aren't  empty  */
          {
/*  next  ring  to  move  is  smaller  of  rings  on  the  two  pegs  not  moved  onto  last  */
 
          if(last==0)    next=z[width+s[1]]  <z[2*width+s[2]]?1:2;
          if(last==1)    next=z[s[0]]  <z[2*width+s[2]]?0:2;
          if(last==2)    next=z[s[0]]  <z[width+s[1]]?0:1;
 
/*  top  ring  of  'to'  peg  must  be  larger  and  an  even  'distance'  away  */
 
          if((z[next*width+s[next]]  >z[last*width+s[last]])||
      ((z[last*width+s[last]]-z[next*width+s[next]])%2==0))  last=3-next-last;
 
          System.out.println(  "from  " + (next+1) + "  to  " + (last+1));
         
          s[next]=s[next]-1;  s[last]=s[last]+1;  /*  move  from  'next'  to  'last'  peg  */
          z[last*width+s[last]]=z[next*width+s[next]+1];
          }
}
}
F:\>java T 3
from  1  to  3
from  1  to  2
from  3  to  2
from  1  to  3
from  2  to  1
from  2  to  3
from  1  to  3

Answer 6

搬第一个盘子时
如果是偶数就是第二个柱子，否则第三个柱子。
Why？统计的吗？

Answer 7

这样看来连堆栈都不需要用到。性能应该比递归要好。只是有两点疑点：
1.搬第一个盘子的规则
2.循环中确定目的地的时用 (prev柱的盘数-current柱的盘数)%2都是移动的规律吗？

Answer 8

Sorry
是盘号，不是盘数(上一次已经移动的盘号 - 当前确定要移动的盘号) % 2 == 0为什么？

Answer 9

有三根柱子A/B/C，是三角形的三个顶点，顺时针方向为A->B->C->A, Hanoi 的非递归算法：1. 把最小的盘子顺时针移到下一位置
2. 把顶上第二小的盘子移动一个位置（只可能有一种移法）
3. 重复1/2，直到所有盘子从一个柱子移到另一个柱子

Answer 10

自己用堆栈写的，Mark一下。
类HanoiElem 的结构：address | number | sourceTower | tempTower | destTower
m_stack 则是存储该类对象的堆栈。public void startMoving() throws Exception
{
Object ta, tb, tc;
HanoiElem hTemp = null;

pushHanoi(new HanoiElem(0, m_count, m_towerA, m_towerB, m_towerC));
while (m_towerC.length() < m_count)
{
         hTemp = peekHanoi();
ta = hTemp.getFrom();
tb = hTemp.getTemp();
tc = hTemp.getTo();
if (1 == hTemp.getNumber())
{
   m_stack.pop();
   moveHanoi(ta, tc);
} else
{
            switch (hTemp.getAddress())
   {
   case 0:
      pushHanoi(new HanoiElem(0, hTemp.getNumber() - 1, ta, tc, tb));
      hTemp.setAddress(hTemp.getAddress() + 1);
      break;
   case 1:
      moveHanoi(ta, tc);
      pushHanoi(new HanoiElem(0, hTemp.getNumber() - 1, tb, ta, tc));
      hTemp.setAddress(hTemp.getAddress() + 1);
      break;
   default:
      m_stack.pop();
      break;
}
}
}是根据递归的思想写的。在想不到"有酒醉"的思路，又不能用递归时，这是种折中的办法。