Posted on 2009-02-22 22:10
鄒江平 閱讀(464)
評(píng)論(0) 編輯 收藏
1
public class Hanoi_X8023Z 
{
2
/// <summary>
3 /// 將n個(gè)盤從one座借助two座,移動(dòng)到three座.
4 /// </summary>
5 /// <param name="n">盤子個(gè)數(shù)</param>
6 /// <param name="one">第一個(gè)標(biāo)識(shí)座A</param>
7 /// <param name="two">第二個(gè)標(biāo)識(shí)座B</param>
8 /// <param name="three">第三個(gè)標(biāo)識(shí)座C</param>
9 void hanoi(int n, String one, String two, String three)
10
{
11 if (n == 1)
12 {
13 move(one, three);//從A座移動(dòng)到C座
14
}
15 else
16 {
17 hanoi(n - 1, one, three, two);//將A上n-1個(gè)盤借助于C座先移動(dòng)到B座上
18 move(one, three);
19 hanoi(n - 1, two, one, three);//將n-1個(gè)盤從B借助于A座移動(dòng)到C座上
20 }
21
22 }
23
24 /// <summary>
25 /// 并未真正移動(dòng)盤子,只是打印出移盤的方案
26 /// </summary>
27 /// <param name="x">from從哪個(gè)座開始移</param>
28 /// <param name="y">to移動(dòng)到哪個(gè)座</param>
29 void move(String x, String y)
30 {
31 FormatStr(x + y);
32 System.out.println(strA + "\n" + strB + "\n" + strC + "\n");
33 }
34
35 //定義三個(gè)字符串
36 private String strA ="0";//A座
37 private String strB ="0";//B座
38 private String strC ="0";//C座
39 private int _long = 5;//初始值
40
41 /// <summary>
42 /// 格式化字符串
43 /// </summary>
44 /// <param name="strType">字符串類型</param>
45 public void FormatStr(String strType)
46 {
47 remove0();
48
49 if (strType .equals("AB"))
50 {
51 strB = strB + strA.substring(strA.length() - 1, strA.length());
52 strA = strA.substring(0, strA.length() - 1);
53
54 }
55 else if (strType .equals("AC"))
56 {
57 strC = strC + strA.substring(strA.length() - 1, strA.length());
58 strA = strA.substring(0, strA.length() - 1);
59
60 }
61 else if (strType .equals("BA"))
62 {
63 strA = strA + strB.substring(strB.length() - 1, strB.length());
64 strB = strB.substring(0, strB.length() - 1);
65 }
66 else if (strType .equals("BC"))
67 {
68 strC = strC + strB.substring(strB.length() - 1, strB.length());
69 strB = strB.substring(0, strB.length() - 1);
70 }
71 else if (strType .equals("CA"))
72 {
73 strA = strA + strC.substring(strC.length() - 1, strC.length());
74 strC = strC.substring(0, strC.length() - 1);
75 }
76 else if (strType .equals("CB"))
77 {
78 strB = strB + strC.substring(strC.length() - 1, strC.length());
79 strC = strC.substring(0, strC.length() - 1);
80 }
81 Add0();
82
83 }
84
85 /// <summary>
86 /// 加0
87 /// </summary>
88 public void Add0()
89 {
90 for (int i = 0; i < _long; i++)
91 {
92 if (i == strA.length())
93 strA = strA + "0";
94 if (i == strB.length())
95 strB = strB + "0";
96 if (i == strC.length())
97 strC = strC + "0";
98 }
99 }
100
101 /// <summary>
102 /// 去0
103 /// </summary>
104 public void remove0()
105 {
106 strA = strA.replace("0", "");
107 strB = strB.replace("0", "");
108 strC = strC.replace("0", "");
109 }
110
111 /// <summary>
112 /// 初始化字符串
113 /// </summary>
114 public void InitStr()
115 {
116 for (int i = _long; i > 0; i--)
117 {
118 strA += String.valueOf(i);
119 strB += "0";
120 strC += "0";
121 }
122 }
123
124 public static void main(String[] args) {
125 // TODO Auto-generated method stub
126 //漢諾塔問題分析方法與解答
127 // 問題:將n個(gè)盤子從A座移動(dòng)到C座
128 // 步驟1:將A座上n-1個(gè)盤借助C座先移動(dòng)到B座上
129 // 步驟2:把A座上剩下的一個(gè)盤移動(dòng)到C座上
130 // 步驟3:將n-1個(gè)盤從B座借助于A座移動(dòng)到C座上
131 // 上面第一步與第三步,都是把n-1個(gè)盤從一個(gè)座移動(dòng)到另一個(gè)座上,采取的辦法是一樣的,只是座的名字不同而已
132 // 對(duì)應(yīng)關(guān)系如下:第一步:one--A two--B three--C;第三步:one--B two--C three--A
133
134 Hanoi_X8023Z hanoi_x8023z = new Hanoi_X8023Z();//實(shí)例化數(shù)據(jù)排序?qū)ο?/span>
135 hanoi_x8023z.InitStr();//初始化字符串
136 String A = "A";//第一個(gè)座A
137 String B = "B";//第二個(gè)座B
138 String C = "C";//第三個(gè)座C
139 int n=5;//盤子個(gè)數(shù)
140 hanoi_x8023z.hanoi(n,A,B,C);//調(diào)用漢諾塔排序方法
141 System.out.println();
142
143 }
144
}
145
結(jié)果：
54320
00000
10000
54300
20000
10000
54300
21000
00000
54000
21000
30000
54100
20000
30000
54100
00000
32000
54000
00000
32100
50000
40000
32100
50000
41000
32000
52000
41000
30000
52100
40000
30000
52100
43000
00000
52000
43000
10000
50000
43200
10000
50000
43210
00000
00000
43210
50000
10000
43200
50000
10000
43000
52000
00000
43000
52100
30000
40000
52100
30000
41000
52000
32000
41000
50000
32100
40000
50000
32100
00000
54000
32000
00000
54100
30000
20000
54100
30000
21000
54000
00000
21000
54300
10000
20000
54300
10000
00000
54320
00000
00000
54321
<第二種>
1import java.util.*;
2public class hanoi {
3
4 final static int HANOI_SIZE = 5; //漢諾塔規(guī)模大小
5 static int count; //盤子搬動(dòng)次數(shù)
6 static Hashtable<String ,Integer> abc; //泛型,記錄柱子上的盤子狀態(tài)，如：A-54321
7
8 static void hanoi(int n, String x, String y, String z)
9 {
10 if (n == 1)
11 {
12 move(x, 1, z); //將編號(hào)為1的盤從x移到z
13 }
14 else
15 {
16 hanoi(n - 1, x, z, y); //將x上編號(hào)為1至n-1的盤移動(dòng)到y(tǒng)，z作為輔助
17 move(x, n, z); //將編號(hào)為n的圓盤從x移到z
18 hanoi(n - 1, y, x, z); //將y上編號(hào)為1至n-1的盤移動(dòng)到z，x作為輔助
19 }
20 }
21
22
23 static void move(String x, int n, String y)
24 {
25 System.out.println("第" + ++count + "次移動(dòng)，把盤" + n + "從" + x + " --> " + y);
26 abc.put(x, abc.get(x)/10);
27 abc.put(y, abc.get(y)*10+n);
28 System.out.println(Filter(abc.get("A")) + " " + Filter(abc.get("B")) + " " + Filter(abc.get("C")));
29 }
30
31
32 static String Filter(int i)
33 {
34 return hanoi.rightFillMethod(String.valueOf(i),HANOI_SIZE);
35 }
36
37 public static String rightFillMethod(String str,int j)//右補(bǔ)0
38 {
39 if(j<str.length())
40 return str;
41 for(int i=0;i<=j-str.length();i++)
42 str+="0";
43 return str;
44 }
45
46 public static void main(String[] args) {
47 //初始化柱子狀態(tài)，和搬動(dòng)次數(shù)計(jì)數(shù)
48 abc = new Hashtable<String, Integer>();
49 abc.put("A", 0);
50 abc.put("B", 0);
51 abc.put("C", 0);
52
53 count = 0;
54
55 int size;
56 for (size = HANOI_SIZE; size > 0; size--)
57 {
58 abc.put("A", abc.get("A") * 10 + size);
59 }
60 hanoi(HANOI_SIZE, "A", "B", "C");
61 System.out.println();
62 }
63
64}
65
結(jié)果：
第1次移動(dòng)，把盤1從A --> C
54320 0000 1000
第2次移動(dòng)，把盤2從A --> B
54300 2000 1000
第3次移動(dòng)，把盤1從C --> B
54300 2100 0000
第4次移動(dòng)，把盤3從A --> C
5400 2100 3000
第5次移動(dòng)，把盤1從B --> A
54100 2000 3000
第6次移動(dòng)，把盤2從B --> C
54100 0000 3200
第7次移動(dòng)，把盤1從A --> C
5400 0000 32100
第8次移動(dòng)，把盤4從A --> B
5000 4000 32100
第9次移動(dòng)，把盤1從C --> B
5000 4100 3200
第10次移動(dòng)，把盤2從C --> A
5200 4100 3000
第11次移動(dòng)，把盤1從B --> A
52100 4000 3000
第12次移動(dòng)，把盤3從C --> B
52100 4300 0000
第13次移動(dòng)，把盤1從A --> C
5200 4300 1000
第14次移動(dòng)，把盤2從A --> B
5000 43200 1000
第15次移動(dòng)，把盤1從C --> B
5000 43210 0000
第16次移動(dòng)，把盤5從A --> C
0000 43210 5000
第17次移動(dòng)，把盤1從B --> A
1000 43200 5000
第18次移動(dòng)，把盤2從B --> C
1000 4300 5200
第19次移動(dòng)，把盤1從A --> C
0000 4300 52100
第20次移動(dòng)，把盤3從B --> A
3000 4000 52100
第21次移動(dòng)，把盤1從C --> B
3000 4100 5200
第22次移動(dòng)，把盤2從C --> A
3200 4100 5000
第23次移動(dòng)，把盤1從B --> A
32100 4000 5000
第24次移動(dòng)，把盤4從B --> C
32100 0000 5400
第25次移動(dòng)，把盤1從A --> C
3200 0000 54100
第26次移動(dòng)，把盤2從A --> B
3000 2000 54100
第27次移動(dòng)，把盤1從C --> B
3000 2100 5400
第28次移動(dòng)，把盤3從A --> C
0000 2100 54300
第29次移動(dòng)，把盤1從B --> A
1000 2000 54300
第30次移動(dòng)，把盤2從B --> C
1000 0000 54320
第31次移動(dòng)，把盤1從A --> C
0000 0000 543210