 |
 |
ハノイの塔Tower of Hanoi ２進数との関係
左側Ｘに積まれている板を一枚ずつ動かして、右側Ｚへそのままの順番で積み上げてください。図Ａから図Ｂへ。
ただし、動かす板は自分より小さな板の上に乗せることは出来ません。中央Ｙも利用できます。
一番少ない回数で完了して下さい。
簡単にするため、図ＡではＸに４枚の板を大きさの順に番号を付けて積み上げてあります。何回で図ＢのようにＺへ移動できるかやってみましょう。
Ｘ Ｙ Ｚ
（順番） 移動板番号→移動場所です。
(00001) 1→Ｙ (空)
(00010) 2→ Z（空） ２ケタ
(00011) 1→ 2
(00100) 3 →Y（空） ３ケタ
(00101) 1→ 4
(00110) 2→ 3
(00111) 1→ 2
(01000) 4→ Z（空） ４ケタ
(01001) 1→ 4
(01010) 2 →X
(01011) 1→ 2
(01100) 3→ 4
(01101) 1→ Y
(01110) 2→ 3
(01111) 1 →2 移動完了
図A
図B
図Ｃ（途中手番 0111）
順に２進数でカウントしながら、全手数を順に並べてみました。面白いことが分かってきます。
（１）奇数回目には、１番の板を動かす。つまり１番の板は他の板と交互に動かす。
（２）初めて１番の板を動かすのは 0001回目、
初めて２番の板を動かすのは 0010回目、
初めて３番の板を動かすのは 0100回目、
初めて４番の板を動かすのは 1000回目、
これは、20 21 22 23
です(拡張 出来そう)。
（３） 図Ｃをご覧ください ３枚の板をＹに順に積み重ねた後、次には４番をＺに動かし、
その４番の上に再び３枚の板を移動して４枚の板の移動が完了します（再帰さいき）。
この手順が最小ですが証明を略しますから感じ取って下さい。
一般的に、ｎ枚の板をＸからＺへ移動する場合も同様です。
上からｎ枚の板が移動完了するまでの回数を Ｐｎ とおくと、
（３）で述べたように
Ｐｎ＝Ｐｎー１＋1＋Ｐｎ−１
＝２Ｐｎー１＋１ ……� ，燭世掘◆。�１＝１ ……��
�，鯤儼舛靴董。�ｎ＋1=２（ｐｎ−１＋１）
ｎ＝２ のとき Ｐ２＋１＝２（Ｐ１＋１）＝２２ （ �‖綟�）
ｎ＝３ のとき Ｐ３＋１＝２（Ｐ２＋１）＝２３
ｎ＝４ のとき Ｐ４＋１＝２（Ｐ３＋１）＝２４
… …
Ｐｎ ＋１ ＝ ２ｎ
故に Ｐｎ＝２ｎ−１
勿論 ｎ＝４ のとき Ｐ４＝２４−１＝１５ （回）でもあります。
ハノイの塔 ４枚手順 アニメ画像
Tower of Hanoi （ハノイの塔）を遊ぶため（？）のとてもきれいな 英語サイトを見つけました。板の枚数は最大Ｎ＝１0まで増加することが出来ます。動きは自動（Ｆａｓｔ/Ｓｌｏｗ）と手動があり便利です。下記アドレスをクリック で動きます。ただしWindows上で Ｊａｖａテクノロジを許可してやらないとダメなようです。自己責任（じぶんのせきにん）ですよ。
http://www.cut-the-knot.org/recurrence/hanoi.shtml
数当てゲーム
２進数との関係をさがそう
口上は次の通り
さーてお立会い。次の５枚のカードに数字が１ ６個ずつ書いてあります。この中からどれか数字を１つ頭にしまってください。それはどれとどれのカードにありますか（^o^。）
ｙｏｕは 「チョメチョメ」 あらそうですか、ではその数字を当ててご覧にいれま〜す。
ｙｏｕが仮に１４を覚えたとすると、それは BとCとD のカードに あると告げるでしょう。
ｍｅはそれを聴いて、 ２＋４＋８ を計算してそれは １４ だと答えます。つまり、
A→１ Ｂ→２ Ｃ→４ Ｄ→８ Ｅ→１６ をそれぞれ当てて計算します。
図に、5ビット列が出てきました。上のカードに対応します。
カードＡには0番ビットがONになる5ビット２進数を全部含めています。以下同様にして、
Ｂには1番ビットがON、 Ｃには2番ビットON、 Ｄには３番ＯＮ、 Ｅは４番ＯＮです。＊印はＯＮ、ＯＦＦどちらでも構いません。
ｙｏｕのように Ｂ Ｃ Ｄに含まれており、Ａ E にはないと言いますと、それは ０１１１０（２進） ということになります。
２進数の性質を見事にとらえています。
さて、カードＡ B E に あるとＭｅは告げています。その数を当てて見ましょうm(^_^)m。
自分でもいろいろ作って遊びをやって見ましょう。下の図のカードも理屈は同じですが、少しだけ「ひねり」が入っています。下の図で Ｂ Ｃ Ｄ にあると告げられたら、覚えた数は １２ です。
また、カードＡ B E に あるとｍｅは告げています。その数を当てて見ましょうm(^_^)m。 「ひねり」が分かると簡単ですね。
偽(にせ)金貨
２進数を利用して解決する
重量秤（はかり）を１回だけ使って、どれが偽金貨の入った袋であるか見分けて下さい。 クラシックな有名な問題です。ヒントとして２進数を利用すると申しておきます m(^_^)m
更に、これは袋が幾つあっても秤を１回だけ使って見分けられると言うから驚きです。
３山くずし（順型）
２進数で必勝パターン
大変ポピュラーで石取りゲームなどとも呼びます。A、B、Cに適当に石が山になっています。２人が交互に石を取っていき、最後に全部の石を取った方が勝ちです。
３山くずしのルールは単純で、 （１）いずれか１つの山から取る （２）そのとき幾つ取ってもいいが、パスは出来ないというものです。この３山くずしには先手必勝パターンと後手必勝パターンがあります。さてme は、
上図 (Ａ…7個、Ｂ…4個、Ｃ…3個）のようにしてから、相手に手番を渡しましたが、これは me の必勝パターンです。２進数とどんな関係があるのか調べてみます。 以下（A,B,C）と表記するのは、次に相手に手番を渡すときの、 A,B,C それぞれの石の個数を表すものとします。
� 。瓜海砲靴徳蠎蠅房衄屬鬚錣燭垢班蕕院�つまり （A,B,C）=（0,0,1）は負け。
２山にしてわたすときは、同個数の石のとき勝ち、異なる個数の石のとき負け。
つまり（0,1,1）は勝ち、（0,1,2）は負け。
�◆�m, n≧1 , m≠n のとき、（A,B,C）=（m,m,m）,（m,m,n）は負けパターン。つまり （1,1,1）,（1,1,2） のように、同数の山があるときに手番をわたすと負け。
�� よって相手に�´△良蕕吋僖拭璽鵑鮑遒蕕擦襪燭瓩砲蓮�me は（A,B,C）= （1,2,3） として渡すといいことになります。
ここで再登場するのが、論理演算（２進ビット演算）XOR （演算子
）です。
表は２進表記してXORを調べてみました。 勝ちパターンは、０１
１０１１
= ００ つまりＡ
ＢＣ =
０ のようになっています。| �� | �� | �� | �� | �� | �� | ||
| 勝負 | 勝ち | 勝ち | 負け | 負け | 負け | 負け | |
| A | 01 | 0 | 00 | 0 | 1 | 01 | |
| B | 10 | 1 | 01 | 0 | 1 | 01 | |
| C | 11 | 1 | 10 | 1 | 1 | 10 | |
| XOR | 00 | 0 | 11 | １ | 1 | 10 |
|
上例 (Ａ…7個、Ｂ…4個、Ｃ…3個）はme の必勝パターンといいましたが、次表で me と you の対戦例を示しました（残りの石数）。me
は毎回 XOR が０になるように、石を取っています。you
は１つの山のビットを反転させなければならないので、XORを０に出来ません。パターン（1,2,3,）へ導く例として参考にして見ましょう。 |
| me | you | me | you | me | you | me | ||
| A | 7 | 111 | 110 | 110 | 101 | 101 | 101 | 10 |
| B | 4 | 100 | 100 | 100 | 100 | 100 | 011 | 11 |
| C | 3 | 011 | 011 | 010 | 010 | 001 | 001 | 01 |
| XOR | 000 | 001 | 000 | 011 | 000 | 111 | 00 |
|
さて ３山くずしで、最後に全部の石を取った方が勝ちとしましたが、これを「順型」とします。別に、最後に石を取らされたら負けとするのもあり、これを「逆型」といいます。これは少し難しいように思います。 また、4山や５山にして遊ぶことも可能ですから楽しんで見るのがいいでしょう。 |
前回答え 情報試験出題方式
ア) 符号部：0 正の数、指数部: 1、仮数部 0. 5 → 2 1×0. 5 = 1イ）符号：正の数、指数部：1001 は 0111= 7(10)の補数表示、仮数: 0. 5
→ 2 -7×0. 5 = 0. 00390625 (有限小数)
エ）負数 -2 1×0. 5 = - 1
前回答えＩＥＥＥ754 方式（単精度）
�� 5. 75＝ 101. 11(10) = 1. 0111×2 2符号部: 0、指数部: 2 + 127(ゲタ) = 1000 0001、仮数部: 整数 1 捨てて 01110000…0 (23ビット)故に、 0 / 1000 0001 / 011 1000 0000 0000 0000 0000
�� 80 = 2 6+2 4 = 1010000 = 1. 01× 2 6
符号部 : 1 (負数)、指数部: 6＋１２７ = 1000 0101 、仮数部: 0100000…0 (23ビット)
故に 1 / 1000 0101 / 010 0000 0000 0000 0000 0000
| |
|
Copyright(C) 2001-2024 Harry PotterAll Rights Reserved.