ハノイの塔

目的

1. 目的

   ハノイの塔と呼ばれるパズルの解をプログラムで作成するのが目的です。
   
   

2. キーワード

   ハノイの塔の問題
   再帰的な手法、再帰的プログラム
   エディットコントロールに複数行表示、
   ダイアログのフォントの設定
   
   

ハノイの塔の問題

1. 問題

   再帰的呼びだしを行う興味深い例として" ハノイの塔の問題"を紹介しましょう。
   n枚の大きさの円盤を順に重ねた塔Aがあります．この塔Aの円盤を塔Bに次のルールにしたがって移すのがハノイの塔の問題です．
   　ルール１：他の塔Cを移動作業用に利用できるが、それ以外の場所に円盤を置くことはできない．
   　ルール２：小さな円盤の上に大きな円盤を置くことはできない．
   
   

2. n=2の場合

   2枚の場合は簡単です。左から中央に移すものとし、右の塔を作業場として利用します。
   
   
   
   

3. n=3の場合

   2枚の場合が解けると、3枚の場合も次のように求められます。
   　S1.上の２枚の塔をBを利用してしてAからCに移動する
   　S2.最後の3枚目の円盤をAからBに移す
   　S3.Cにある２枚の塔をAを利用してCからAに移す
   
   n=2の移動法は既に定まっていますから，これで，n=3の場合も定まります．n=3の解では，n=2を行うとき３枚目の円盤が既に配置されていますが，これは一番大きな円盤ですから解法に影響はありません．
   
   

4. 一般の場合

   n-1枚の場合の方法が決まれば、n枚の場合も求まります。
   一般にn枚の場合、これを最初の n-1 と最後の1枚に分割します。
   　S1: 上のnｰ1枚の塔をBを利用してしてAからCに移動する
   　S2: 最後のn枚目の円盤をAからBに移す
   　S3: Cにあるnｰ1枚の塔をAを利用してCからAに移す
   0枚の移動はなにもしないことにします．
   
   n枚の場合
   
   
   
   

プロジェクト（Java)の作成

1. レイアウト

   円盤の数を設定する文字入力ボックス、経過を表示する文字エリア、実行開始ボタン、詳細な呼び出し表示を設定するチェックボックスを用意します。実行画面を参考にして下さい。
   
   

2. 実行例

   
   
   
   

3. ソース

   
   

   //ハノイの塔
   
   import java.awt.*;
   import java.awt.event.*;
   import java.applet.*;
   
   public class cHanoi extends Applet {
     private boolean isStandalone = false;
     int m_num;
     String str;
     boolean m_vs=false;
   
     private TextField textField1 = new TextField();
     private Label label1 = new Label();
     private TextArea textArea1 = new TextArea();
     private Button button1 = new Button();
     private Checkbox checkbox1 = new Checkbox();
   
     //アプレットの初期化
     public void init() {
       try {
         jbInit();
       }
       catch(Exception e) {
         e.printStackTrace();
       }
     }
   
     //コンポーネントの初期化
     private void jbInit() throws Exception {
       textField1.setText("3");
       textField1.setBounds(new Rectangle(157, 25, 72, 21));
       this.setLayout(null);
       label1.setText("枚数");
       label1.setBounds(new Rectangle(55, 16, 51, 22));
       textArea1.setText("textArea1");
       textArea1.setBounds(new Rectangle(22, 64, 272, 172));
       button1.setLabel("実行");
       button1.setBounds(new Rectangle(58, 248, 61, 24));
       button1.addActionListener(new java.awt.event.ActionListener() {
         public void actionPerformed(ActionEvent e) {
           button1_actionPerformed(e);
         }
       });
       checkbox1.setLabel("詳細");
       checkbox1.setBounds(new Rectangle(183, 250, 48, 22));
       this.add(textField1, null);
       this.add(label1, null);
       this.add(textArea1, null);
       this.add(button1, null);
       this.add(checkbox1, null);
     }
   
   //「実行」ボタンを押すと実行します
     void button1_actionPerformed(ActionEvent e) {
     //枚数を読み込む
       m_num=Integer.parseInt(textField1.getText());
       m_vs=checkbox1.getState();
       str="";
       Hanoi(m_num,'A','B','C');
       textArea1.setText(str);
     }
   
     void Hanoi(int Num,char A,char B,char C)
     {
       if (Num > 0){
         if(m_vs){
           space(Num);
           str += "(Hanoi Num:"+(Num-1)+" from:"+A+" to:"+C +")\n";
         };
         Hanoi(Num-1,A,C,B);
         space(Num);
         str += "move "+Num+" th disk from " + A+ " to "+ B+"\n";
         if(m_vs){
           space(Num);
           str += "(Hanoi Num:"+(Num-1)+" from:"+C+" to:"+B +" via "+A+")\n";
         };
         Hanoi(Num-1,C,B,A);
       }
     }
   
   //枚数に応じて空白を表示する
     void space(int Num)
     {
       for(int i=0;i<(m_num-Num);i++) str +="  ";
     }
   
   }

   
   

演習