No. 19≫ No.20 ≫No. 21
Yss
2015/12/16 10:50
問２はＱに解説してもらいましょう。
Ｑ「キミは、二進数を知っているかい？」
Ｂ「知ってますよ。」
Ｑ「じゃあ、二進の『グレイコード』は知っているかい？」
Ｂ「・・・いや、分かりません。」
Ｑ「グレイコードというのはね、普通の二進数と同様０と１で構成されているんだけど、数値が１進む度に、必ず１ビットだけ変化が出るように並べられているコードのことだよ。」
Ｂ「何となく分かるような、分からないような。」
Ｑ「二進数で７はどう表す？」
Ｂ「１１１です。」
Ｑ「では８は？」
Ｂ「１０００です。」
Ｑ「そうだね。数は１しか違わないのに、全ビットが反転していて、ここって妙に変化が大きいと思わないか？」
Ｂ「そうですけど、繰り上がりがあるので仕方ないですよね？」
Ｑ「そうなんだけど、数字が１個進むごとに、１ビットだけ反転していく、というコードが便利なときもあるんだよ。この、スイッチの探索なんてまさに、そういう話じゃないか。」
Ｂ「はぁ・・・分かったような、分からないような。」
Ｑ「二進４桁のグレイコードは、こういう並びになる。順に０から１５までを表す」
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Ｂ「なるほど確かに、ひとつ進むごとに一桁だけ反転している・・・」
Ｑ「このパズルでは、グレイコードそのものではないけれど、近い考え方でスイッチ探索をすると効率的だろう・・・ただ、キミはグレイコードを知らなかったのに、さっきの解法を思いついたのかい？」
Ｂ「え？まあそうですけど。」
Ｑ「実際、最短の手数になっていたので、知っていたのかと思ったよ。」
Ｂ「えへへ。野生の勘ってヤツ？」
Ａ「Ｂ太くん、あんまり野生は似合わないけど・・・」
Ｑ「それで、スイッチの探索は、まずこんな風に行う。ひとつ入れて、隣を入れて、ひとつ前のを切る、といった手順だ。」
最初の数字が手数、あとの５桁はそれぞれＴ１からＴ５のスイッチのＯＮ（１）／ＯＦＦ（０）を表す。
54321 ←スイッチの番号
0:00000
1:00001
2:00011
3:00010
4:00110
5:00100
6:01100
7:01000
8:11000
Ｑ「以上はあくまで計画で、もしこの操作の途中で、音の鳴らないスイッチに遭遇したら、そのスイッチは以後スルーする。例えば今回の場合Ｔ３が無音だったね。つまり手順の４番目で無音だったよね。そうしたらその時点で桁数を減らす。」
54321
0:00000
1:00001
2:00011
3:00010
4:00110 ←無音（＝Ｔ３は回路外）
↓考え方として、桁数を減らす（スイッチ操作はしていない）
5421
4:0010
↓そして、４桁にして続きを行う。
5:0110
6:0100
7:1100
ここまでで、回路外のスイッチを特定するだけでなくて、
正解があり得るパターンのうち、
0011
0110
1100
を試しているので、残りは、
1010
0101
1001
のみっつ。（なぜなら、ふたつＯＮ、ふたつＯＦＦのパターンと分かっているので、1111などは探索から除外してよい）
8:0100
9:0101 *
a:0001
b:1001 *
c:1000
d:1010 *
*をつけたところで、開く可能性がある。
Ｑ「というわけだけど。よく分からないと言いながら、実際にこのパターンで探索したんだから、大したもんだよ」
Ｂ「えへへ・・・」
Ｑ「キミは、二進数を知っているかい？」
Ｂ「知ってますよ。」
Ｑ「じゃあ、二進の『グレイコード』は知っているかい？」
Ｂ「・・・いや、分かりません。」
Ｑ「グレイコードというのはね、普通の二進数と同様０と１で構成されているんだけど、数値が１進む度に、必ず１ビットだけ変化が出るように並べられているコードのことだよ。」
Ｂ「何となく分かるような、分からないような。」
Ｑ「二進数で７はどう表す？」
Ｂ「１１１です。」
Ｑ「では８は？」
Ｂ「１０００です。」
Ｑ「そうだね。数は１しか違わないのに、全ビットが反転していて、ここって妙に変化が大きいと思わないか？」
Ｂ「そうですけど、繰り上がりがあるので仕方ないですよね？」
Ｑ「そうなんだけど、数字が１個進むごとに、１ビットだけ反転していく、というコードが便利なときもあるんだよ。この、スイッチの探索なんてまさに、そういう話じゃないか。」
Ｂ「はぁ・・・分かったような、分からないような。」
Ｑ「二進４桁のグレイコードは、こういう並びになる。順に０から１５までを表す」
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Ｂ「なるほど確かに、ひとつ進むごとに一桁だけ反転している・・・」
Ｑ「このパズルでは、グレイコードそのものではないけれど、近い考え方でスイッチ探索をすると効率的だろう・・・ただ、キミはグレイコードを知らなかったのに、さっきの解法を思いついたのかい？」
Ｂ「え？まあそうですけど。」
Ｑ「実際、最短の手数になっていたので、知っていたのかと思ったよ。」
Ｂ「えへへ。野生の勘ってヤツ？」
Ａ「Ｂ太くん、あんまり野生は似合わないけど・・・」
Ｑ「それで、スイッチの探索は、まずこんな風に行う。ひとつ入れて、隣を入れて、ひとつ前のを切る、といった手順だ。」
最初の数字が手数、あとの５桁はそれぞれＴ１からＴ５のスイッチのＯＮ（１）／ＯＦＦ（０）を表す。
54321 ←スイッチの番号
0:00000
1:00001
2:00011
3:00010
4:00110
5:00100
6:01100
7:01000
8:11000
Ｑ「以上はあくまで計画で、もしこの操作の途中で、音の鳴らないスイッチに遭遇したら、そのスイッチは以後スルーする。例えば今回の場合Ｔ３が無音だったね。つまり手順の４番目で無音だったよね。そうしたらその時点で桁数を減らす。」
54321
0:00000
1:00001
2:00011
3:00010
4:00110 ←無音（＝Ｔ３は回路外）
↓考え方として、桁数を減らす（スイッチ操作はしていない）
5421
4:0010
↓そして、４桁にして続きを行う。
5:0110
6:0100
7:1100
ここまでで、回路外のスイッチを特定するだけでなくて、
正解があり得るパターンのうち、
0011
0110
1100
を試しているので、残りは、
1010
0101
1001
のみっつ。（なぜなら、ふたつＯＮ、ふたつＯＦＦのパターンと分かっているので、1111などは探索から除外してよい）
8:0100
9:0101 *
a:0001
b:1001 *
c:1000
d:1010 *
*をつけたところで、開く可能性がある。
Ｑ「というわけだけど。よく分からないと言いながら、実際にこのパターンで探索したんだから、大したもんだよ」
Ｂ「えへへ・・・」