Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

本文实例讲述了java基于栈方式解决汉诺塔问题。分享给大家供大家参考，具体如下：

/**
 * 栈方式非递归汉诺塔
 * @author zy
 *
 */
public class stackhanoi
{
  /**
   * @param args
   */
  public static void main(string[] args)
  {
    system.out.println("测试结果：");
    system.out.println("递归方式：");
    hanoinormal(3, 'a', 'b', 'c');
    system.out.println();
    system.out.println("非递归方式：");
    hanoi(3, 'a', 'b', 'c');
  }
  /**
   * 递归汉诺塔
   * @param n
   * @param a
   * @param b
   * @param c
   */
  public static void hanoinormal(int n, char a, char b, char c)
  {
    //hanoinormal(1, a, b, c)等价于直接移动a到c（ move(a,c) ）
    if(n==1)
    {
      move(a, c);
      return;
    }
    else
    {
      hanoinormal(n-1, a, c, b);
      move(a, c);
      hanoinormal(n-1, b, a, c);
    }
  }
  /**
   * 非递归汉诺塔
   * @param n
   * @param a
   * @param b
   * @param c
   */
  public static void hanoi(int n, char a, char b, char c)
  {
    //创建一个栈
    statestack s = new statestack();
    //将开始状态进栈
    s.push( new state(n, a, b, c) );
    //保存出栈元素
    state state = null;
    //出栈
    while((state = s.pop()) != null)
    {
      //如果n为1( hanoi(1,a,b,c) )，直接移动a->c
      if(state.n == 1)
      {
        move(state.a, state.c);
      }
      //如果n大于1，则按照递归的思路，先处理hanoi(n-1,a,c,b)，再移动a->c(等价于hanoi(1,a,b,c) ),然后处理hanoi(n-1,b,a,c)，因为是栈，所以要逆序添加
      else
      {
        //栈结构先进后出，所以需要逆序进栈
        s.push( new state(state.n-1, state.b, state.a, state.c) );
        s.push( new state(1, state.a, state.b, state.c) );
        s.push( new state(state.n-1, state.a, state.c, state.b) );
      }
    }
  }
  /**
   * 从s到d移动盘子
   */
  public static void move(char s, char d)
  {
    system.out.println(s+"->"+d);
  }
}
//状态
class state
{
  public int n;
  public char a;
  public char b;
  public char c;
  public state(int n, char a, char b, char c)
  {
    this.n = n;
    this.a = a;
    this.b = b;
    this.c = c;
  }
}
//栈
class statestack
{
  private state[] storage = new state[1000];
  //栈顶
  private int top = 0;
  //入栈
  public void push(state s)
  {
    storage[top++] = s;
  }
  //出栈
  public state pop()
  {
    if(top>0)
    {
      return storage[--top];
    }
    return null;
  }
}

运行结果：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。