玩一下java，顺便写了下汉诺塔问题，两种方法实现。

Posted on 2009-02-22 22:10 邹江平 阅读(455) 评论(0)  编辑  收藏
  1public class Hanoi_X8023Z {
  2    /// <summary>
  3    /// 将n个盘从one座借助two座,移动到three座.
  4    /// </summary>
  5    /// <param name="n">盘子个数</param>
  6    /// <param name="one">第一个标识座A</param>
  7    /// <param name="two">第二个标识座B</param>
  8    /// <param name="three">第三个标识座C</param>
  9    void hanoi(int n, String one, String two, String three)
 10    {
 11        if (n == 1)
 12        {
 13            move(one, three);//从A座移动到C座
 14        }
 15        else
 16        {
 17            hanoi(n - 1, one, three, two);//将A上n-1个盘借助于C座先移动到B座上
 18            move(one, three);
 19            hanoi(n - 1, two, one, three);//将n-1个盘从B借助于A座移动到C座上
 20        }
 21
 22    }
 23
 24    /// <summary>
 25    /// 并未真正移动盘子,只是打印出移盘的方案
 26    /// </summary>
 27    /// <param name="x">from从哪个座开始移</param>
 28    /// <param name="y">to移动到哪个座</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    //定义三个字符串
 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个盘子从A座移动到C座
128        // 步骤1:将A座上n-1个盘借助C座先移动到B座上
129        // 步骤2:把A座上剩下的一个盘移动到C座上
130        // 步骤3:将n-1个盘从B座借助于A座移动到C座上
131        // 上面第一步与第三步,都是把n-1个盘从一个座移动到另一个座上,采取的办法是一样的,只是座的名字不同而已
132        // 对应关系如下:第一步:one--A two--B three--C;第三步:one--B two--C three--A
133
134        Hanoi_X8023Z hanoi_x8023z = new Hanoi_X8023Z();//实例化数据排序对象
135        hanoi_x8023z.InitStr();//初始化字符串
136        String A = "A";//第一个座A
137        String B = "B";//第二个座B
138        String C = "C";//第三个座C
139        int n=5;//盘子个数
140        hanoi_x8023z.hanoi(n,A,B,C);//调用汉诺塔排序方法
141        System.out.println();
142      
143    }
144}
145

结果：

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;               //汉诺塔规模大小
 5    static int count;                             //盘子搬动次数
 6    static Hashtable<String ,Integer> abc;       //泛型,记录柱子上的盘子状态，如：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);              //将编号为1的盘从x移到z
13        }
14        else
15        {
16            hanoi(n - 1, x, z, y);      //将x上编号为1至n-1的盘移动到y，z作为辅助
17            move(x, n, z);              //将编号为n的圆盘从x移到z
18            hanoi(n - 1, y, x, z);      //将y上编号为1至n-1的盘移动到z，x作为辅助
19        }
20    }
21
22   
23    static void move(String x, int n, String y)
24    {
25        System.out.println("第" + ++count + "次移动，把盘" + 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)//右补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        //初始化柱子状态，和搬动次数计数
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

结果：
第1次移动，把盘1从A --> C
54320 0000 1000
第2次移动，把盘2从A --> B
54300 2000 1000
第3次移动，把盘1从C --> B
54300 2100 0000
第4次移动，把盘3从A --> C
5400 2100 3000
第5次移动，把盘1从B --> A
54100 2000 3000
第6次移动，把盘2从B --> C
54100 0000 3200
第7次移动，把盘1从A --> C
5400 0000 32100
第8次移动，把盘4从A --> B
5000 4000 32100
第9次移动，把盘1从C --> B
5000 4100 3200
第10次移动，把盘2从C --> A
5200 4100 3000
第11次移动，把盘1从B --> A
52100 4000 3000
第12次移动，把盘3从C --> B
52100 4300 0000
第13次移动，把盘1从A --> C
5200 4300 1000
第14次移动，把盘2从A --> B
5000 43200 1000
第15次移动，把盘1从C --> B
5000 43210 0000
第16次移动，把盘5从A --> C
0000 43210 5000
第17次移动，把盘1从B --> A
1000 43200 5000
第18次移动，把盘2从B --> C
1000 4300 5200
第19次移动，把盘1从A --> C
0000 4300 52100
第20次移动，把盘3从B --> A
3000 4000 52100
第21次移动，把盘1从C --> B
3000 4100 5200
第22次移动，把盘2从C --> A
3200 4100 5000
第23次移动，把盘1从B --> A
32100 4000 5000
第24次移动，把盘4从B --> C
32100 0000 5400
第25次移动，把盘1从A --> C
3200 0000 54100
第26次移动，把盘2从A --> B
3000 2000 54100
第27次移动，把盘1从C --> B
3000 2100 5400
第28次移动，把盘3从A --> C
0000 2100 54300
第29次移动，把盘1从B --> A
1000 2000 54300
第30次移动，把盘2从B --> C
1000 0000 54320
第31次移动，把盘1从A --> C
0000 0000 543210

只有注册用户登录后才能发表评论。
网站导航: