2進数による解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/16 04:07 UTC 版)
初期状態から n 回動かした状態は、n の2進数表記から、一意的に求めることができる。 すべて左端の棒にある状態からすべて右端の棒に移動させる場合、各円盤の位置は以下のように求められる。 n を2進数で書き表す。 最上位が一番大きい円盤、以下順に対応し1の位が一番小さい円盤に対応する。 最上位が0のとき、一番大きい円盤がまだ動いておらず、1の時には移動済みである。 各桁の数字を一つ上の位と比べる。同じ値の場合その円盤は一回り大きい円盤の上に乗っている（同じ棒上にある）。 異なっている場合その数字が0の場合下から奇数番目の場合、一回り大きい物の右隣にある。 下から偶数番目の場合、一回り大きい物の左隣にある。 その数字が1の場合下から奇数番目の場合、一回り大きい物の左隣にある。 下から偶数番目の場合、一回り大きい物の右隣にある。 ただし、左端の棒の左隣は右端、右端の棒の右隣は左端とする。 2進数の演算を利用すると、n 番目の移動を簡単に表記することができる。C言語の表記を用いると n 番目の移動は、「(n&(n-1))%3 番目の棒にある円盤を ((n|(n-1))+1)%3 番目の棒に移動する」となる。 なお、メルセンヌ数は二進数では全ての桁の位を占める数が1になるから、前述の二進数演算による解析は、全ての棒に与えられた枚数n分の二進メルセンヌ数桁との因果関係を明らかにしている。これは次項のパリティとグレイ・コード解法にも大きく関与しているといえる。
※この「2進数による解析」の解説は、「ハノイの塔」の解説の一部です。
「2進数による解析」を含む「ハノイの塔」の記事については、「ハノイの塔」の概要を参照ください。
- 2進数による解析のページへのリンク
