◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇

再帰呼び出しによるハノイの塔解法計算の実装

発行：エスオーエル株式会社
https://www.sol-j.co.jp

連載「測定の新常識！？SOLがお伝えするノウハウ！」
2024年7月10日号　VOL.E-0163

平素は格別のお引き立てを賜り、厚く御礼申し上げます。
X線CTによる精密測定やアプリケーション開発情報などをテーマに、
無料にてメールマガジンを配信いたしております。

◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇



こんにちは、こんばんは。
技術グループの米村です。

前回の私担当のメルマガではWerth社の
アプリケーションであるWinWerthにて使用される、
DMISという言語で階乗計算の再帰関数を実装いたしました。

今回は前回に引き続き再帰関数を用いてハノイの塔というものの
解法を求めるプログラムを実装します。

ハノイの塔というのはパズルの一種になります。
ルールとしては下記の通りです。

・３本の塔と大きさの異なる複数の円盤から構成される。
・最初は全ての円盤が左端の塔に、小さいものが上になるように
　積み重なっている。
・円板を１つずつ他の塔に移動することができるが、
　小さな円盤の上に大きな円盤を乗せることは出来ない。
・全ての円盤を右端の塔に移動させるのが目標。

例えば、３枚の円盤で考えると下記の手順で動かします。

(1)　１枚目を左から右の塔へ移動。　（２３｜　　｜１）
(2)　２枚目を左から中央の塔へ移動。（３　｜２　｜１）
(3)　１枚目を右から中央の塔へ移動。（３　｜１２｜　）
(4)　３枚目を左から右の塔へ移動。　（　　｜１２｜３）
(5)　１枚目を中央から左の塔へ移動。（１　｜２　｜３）
(6)　２枚目を中央から右の塔へ移動。（１　｜　　｜２３）
(7)　１枚目を左から右の塔へ移動。　（　　｜　　｜１２３）

文字で表現すると分かりづらいですが、想像しながら
実際に手を動かして考えてみるとわかりやすいかもしれません。

この動作を再帰関数で実装する場合、下記のようになります。

(1)　n-1枚目までを左から中央の塔へ移動。
(2)　n枚目を中央から右の塔へ移動。
(3)　中央の塔に残ったn-1枚を右の塔へ移動。

詳細は省きますがこのような手順となり、(1)と(3)にて再帰呼び出しを行います。

実際にDMISにて実装したものは以下になります。

-----------------------------------------------------------------------
MACRO / Hanoi
  LET / $i = $i+1
  LET / $height[$i] = $CALLARG[0]
  LET / $temp1[$i] = $CALLARG[1]
  LET / $temp2[$i] = $CALLARG[2]
  LET / $temp3[$i] = $CALLARG[3]

  IF / ($height[$i] < 1), (ReturnHanoi)
    CALL / Hanoi, $height[$i] -1, $temp1[$i], $temp3[$i], $temp2[$i]
    TEXT / OUTPUT, '$height[$i]枚目, $temp1[$i] -> $temp3[$i]'
    CALL / Hanoi, $height[$i] -1, $temp2[$i], $temp1[$i], $temp3[$i]
    (ReturnHanoi)
  LET / $i = $i-1
ENDMAC

DECL / INT, i
DECL / INT, height[1000]
DECL / CHAR, temp1[1000], temp2[1000], temp3[1000]

CALL / Hanoi, 3, '左', '中央', '右'

ENDFIL
-----------------------------------------------------------------------

このプログラムでは、それぞれの塔を「左」「中央」「右」と名付け、
３枚の円盤のときの解法を求めています。

実行結果は以下になります。

----------------------------------
1枚目, 左 -> 右
2枚目, 左 -> 中央
1枚目, 右 -> 中央
3枚目, 左 -> 右
1枚目, 中央 -> 左
2枚目, 中央 -> 右
1枚目, 左 -> 右
----------------------------------

例で挙げたものと同じ結果になりました！

今回は円盤の枚数を３枚としています。
それというのも、ハノイの塔の手数は「２のｎ乗－１」となっており、
少し数を増やしただけでとんでもない数になってしまうからになります。

ここには載せませんが、円盤の枚数を１０枚としたときの計算もして、
その際は1023行となりました。

そして、プログラムを見て気付いた方も居られるかも知れませんが
DMISで再帰関数を作る上で悲しい事実が発覚しました。

再帰呼び出しをした際の関数の引数は新しい領域を
確保せず同じ領域を使いまわします。

そのため処理が終わり1つ前の関数に戻った際に
引数に齟齬が発生するという事態がありました。

今回は関数の外に作業用の配列をそれぞれ1000個用意して
そこに引数を記憶させておくというゴリ押しにより解決いたしました。

もしDMISで再帰関数を実装されるという方が居られましたらご注意ください。

これにて今回の内容は以上となります。
最後までお読みいただきありがとうございました。


--
T.Y