个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/**
  * 栈方式非递归汉诺塔
  * @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程序设计有所帮助.

原文链接：http://zy3381.iteye.com/blog/1993895 。

最后此篇关于Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】的文章就讲到这里了,如果你想了解更多关于Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： Python对切片命名的实现方法
文章推荐： 下一站江湖战力怎么提升 快速提升战力攻略
文章推荐： Python 给某个文件名添加时间戳的方法
文章推荐： 下一站江湖广成山秘籍怎么拿 广成山秘籍获取方法攻略
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com