平成30年春期午後問3  14行目

内定取り消しさん  
(No.1)
https://www.ap-siken.com/kakomon/30_haru/pm03.html

「現在のマスの移動順序を取り消して、マスを通過していない状態に戻す」というⅱ-3の記述がある意味が分かりません(解答欄キの部分です)。
2020.03.19 03:58
健闘お祈りしますさん 
(No.2)
巡回問題というと難しそうですが、チェスのナイトの駒を使ったパズルですね。
スタートからナイトが移動できるルールで駒を動かし、全てのマスを1回ずつ通りなさいという問題です。

このアルゴリズムは、比較的人間の思考法に近い形でできているように思います。
次のような感じで進みます。(若干簡略化しています。ご容赦ください)
(1)ナイトのルールで次に移動する空きマス(まだ通ってないマス)を探す
(2)移動する
(3)移動後、今のマスに今何番目の移動か書き込む
(4)次の移動できるマスを探す(以降(2)から繰り返し)

ここで、まだ何も書き込んでいない空きマスがあり、かつ(4)での次の移動先がない場合、今いる場所に駒を進めたこと自体が間違っている、ということになりますね?
この場合、(2)(3)をなかったことにして一マス分移動を巻き戻し、(2)ではない別の移動先からやり直す必要があります。

(ⅱ-3)「現在のマスの移動順序を取り消して、マスを通過していない状態に戻す」は、上記でいう(3)の「このマス使いましたよ」チェックを取り消す処理です。
その後の、
(ⅱ-4)「再帰関数 search の呼出し元へ戻る」が、(2)に来たことを忘れて(1)に戻ることを指します。
2020.03.19 16:40

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop