実用的な解法

ウィキペディア小見出し辞書

実用的な解法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/16 04:07 UTC 版)

「ハノイの塔」の記事における「実用的な解法」の解説

再帰的でない解き方として、以下のような手順がある。人間が解く場合にも利用可能である。 いちばん小さい円盤とそれ以外の円盤を交互に動かす。 いちばん小さい円盤は常にB→C→A→B(nが偶数の場合)またはC→B→A→C(nが奇数の場合)の順に動かす。 いちばん小さな円盤以外の円盤を動かす場面では、動かせる方法は1通りしかない。 このような単純なアルゴリズムで表記されるにもかかわらず、実際には 2n − 1 手かかる。 棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。