クイズ大陸クイズ大陸

参加型ナゾトキサイト『クイズ大陸』で、脳トレをどうぞ！

 FAQ
feedRSS

シェア
もしかして、有名問題??
難易度：★ 　
?aiu 2009/12/08 20:22
ハノイの塔において、初期状態でn段の円盤が積まれているとき、円盤の移動にかかる最短回数とその証明方法を答えよ。


－－－－ハノイの塔のルール－－－－
以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

・3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
・最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
・円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
（参考文献：Wikipedia）
Answer【2<sup>n</sup>－1回

n+1段の円盤の移動を行う場合、必ず以下の手順を踏まなければならない。

①n+1段あるうちの上からn段までを中央の杭に移動させる。
②残った一番下の円盤を右端に移動させる。
③①で中央に移動させたn段の塔を右端に移す。

n+1段の円盤の移動にかかる最短回数をA(n+1)回とすると、
①の操作にかかる最短回数はA(n)回
②にかかる最短回数は1回
③にかかる最短回数はA(n)回

したがって、A(n+1)＝A(n)＋1＋A(n)　⇔　A(n+1)＝2A(n)＋1　となる。また、A(1)＝1

この漸化式を解くと、A(n)＝2<sup>n</sup>－1】
■
回答募集は終了しました。

このクイズのヒント

    ヒント知らないよ

このクイズの参加者（8人）

ジャンル・キーワード

携帯用ページ


携帯電話のQRコード読み取り機能でこのページを見られます。

広告 お買い物は下記のリンクからどうぞ
楽天市場はこちらから
Amazonはこちらから

広告
クイズ大陸関連書籍