レポート１

ハノイの塔

• ルール
  1. 3本の杭と，中央に穴の開いた大きさの異なる複数の円盤から構 成される．
  2. 最初は，すべての円盤が左端の杭に小さいものが上になるように順 に積み上げられている．
  3. 円盤を１回に１枚ずつどこかの移動させることができるが， 小さな円盤の上に大きな円盤を乗せることはできない．
• 解法（nをAからCへ移動．このときBをn-1の退避場所に使用．） ）
  1. 上から n-1個目の円盤を「適切な方法」でAからBに移動する．
  2. 残った１枚をAからCに移動する．
  3. Bにある円盤を「適切な方法」でBからCに移動する．
• 注： 「適切な方法」で行うことは，n-1個目の円盤を移動するとい う副問題である．=> 再帰で解くことができる．

課題

1. ハノイの塔の実行過程を，show を用いて，見られるようにしなさい．次の点を参考にするとよい。
   • printf: printf("hogehoge")のようにすると，文字列を印字する． printf("x = %d, y = %d",x,y)のように，文字列中に%d が現れると，その後に続く対応する値を印字する．
   • gets: 文字列を読み込む．ここでは，実行を一時停止させるために 用いる．Returnを押すと先に進む．
   • 例： "\n" は改行を意味する．
     

     def test ()
      for i in 0..10
        for j in 0..10
          printf("i = %d, j = %d\n", i, j)
          gets()
        end
      end
     end
     

   • 注： 見通しがたたない人は，各大きさの円盤に対して，表示する 高さが固定されているとしてよい．
2. レポートについて：〆切：1月9日． プログラムの説明と考察の項目を用意して下さい．プログラムは，別途添付してください．