中級その3

こんにちは!このページは「コンピュータサイエンスと魔法のYコンビネータ」という記事の10ページ目です。1ページ目から読むにはこちらからどうぞ

コンピュータサイエンスと
魔法のYコンビネータ

中級その4: 1を足せない?

スライド 1 / 9

サヤちゃんの疑問

サヤちゃんは、1を足す効果 がある弁当箱について、あることに気が付きました。

ねえねえ、見てほしいものがあるんだけど。

まず、これは に変換できる弁当箱だよね。

右下には がついた が「1
→ 計算箱に変換すると になる
1
1

うん、そうだけど、それがどうしたの?

これを、前回サヤが考えた1を足す効果 がある弁当箱と合体させて、実行してから 計算箱に変換 すると、どうなると思う?

1を足す効果 と合体させて、
実行してから 計算箱に変換
するとどうなる?
1
1
1
1
13
2
23
1

そりゃあ、 を計算できるんだから、 になるに決まっているだろう?

結果は になるはず…?

じゃあ、実行 してみてよ!

他のページをお探しですか?

中級その3·
·中級その5
スライド 2 / 9

実行してみると…

それでは、早送り を押してみてください最後までスキップすることも可能です。

1
1
1
1
13
2
23
1

実行を終えたので、 計算箱に変換 したいところですが…

残念ながら、この弁当箱はぼくが計算箱に変換することができません。

計算箱に変換できない
12
2
1

理由は、以下の法則に沿っていないからです。

一番左の料理を
真ん中の料理を とした場合、
右上に がひとつあり、
右下に がいくつかある
ひとつ
いくつか

右上には の料理が「ひとつだけ」ある必要があります。しかし、ここでは の料理がふたつもあるので、計算箱に変換できないのです。

右上に がふたつあるので、
計算箱に変換できない
12
2
1

お、おかしい…なんで に変換できる弁当箱にならないんだ?前回はちゃんとできていたのに…

スライド 3 / 9

前回と比較してみよう

では、前回と比較してみましょう。前回実行したのは、こちらの弁当箱でした。

先ほどと唯一違うのは、上の部分に サンドイッチ のかわりに フライドポテト が入っているところです。(黄色で示しています)

早送り を押してみてください:

前回実行した弁当箱:
上の部分は に変換できる。
先ほどと違うのは、上の の部分。
それ以外はすべて先ほどと同じ。
1
1
1
1
13
2
23
1

こちらは、最終的に に変換できる弁当箱になりますね。

右下には がついた が「2
→ 計算箱に変換すると になる
12
2
1

うーん、どうして結果に違いが出るんだろう?

スライド 4 / 9

に同じ料理があると、結果が狂う

では、ここでネタばらしをしましょう。

こちらに、先ほど失敗した例をもう一度表示しています。

先ほど を計算できなかった
1
1
1
1
13
2
23
1

次に、 の印をつけてみます。

の印をつけます
1
1
1
1
13
2
23
1

ここで、 の両方に、サンドイッチ があるのに注目してみてください。

の両方にサンドイッチ がある
1
1
1
1
13
2
23
1

実は、このように に同じ料理があると、実行結果が狂ってしまうのです。

実行結果が狂ってしまうから、 を計算できない、ということになります。

に同じ料理があると、
実行結果が狂う

(先ほどの場合はサンドイッチ
両方にある)

へー、そうなんだ!どうして結果が狂うの?

この例だと複雑すぎて説明が難しいので、簡単な例を使って説明しますね!

スライド 5 / 9

に同じ料理がない場合とある場合

では、簡単な例で説明します。次のふたつの例をご覧ください。

  • 左側は、 が違います。
  • 右側は、 が同じサンドイッチ です。

それぞれを進めてみますね。

が違う
2
1
12
2
1
12
2
1
12
2
1
12
下の料理が違う
1
1
が同じ
2
1
12
2
1
12
2
1
12
2
1
12
下の料理が同じ
1
1

左側は、下のふたつの料理が違うけど、右側は下のふたつの料理が同じになった!

そうなんです。このまま最後まで実行すると、

  • 左側は ハンバーガー が残るのに対し、
  • 右側は チキン が残ります。
1
1
1
1
1
1
1
1
1
1

最初と最後だけをピックアップすると、以下のようになります。

が違う
2
1
12
が同じ
2
1
12

というわけで、 に同じ料理がない場合とある場合で、最終的な結果が狂ってくることがお分かりいただけたでしょうか。

に同じ料理があると、
実行結果が狂う
スライド 6 / 9

話を戻すと…

では、先ほど を計算できなかった弁当箱に話を戻しましょう。

の両方にサンドイッチ があるので、結果が狂うのですね。

を計算できなかった理由:
の両方にサンドイッチ
あるせいで、結果が狂ったから
1
1
1
1
13
2
23
1

じゃあ、どうすればいいんだろう?

のどちらかのサンドイッチ を別の料理に変えれば、上手くいくというわけだよね。

じゃあ…ミニオンさんお願い!特別ルールを設けてくれないかな?

どういうことですか?

「弁当箱のパズル に、「 に同じ料理が登場したら、どちらかを別な料理に変える」という特別ルールを設けてほしいんだ。

に同じ料理が登場したら、
どちらかを別な料理に変える

という特別ルールを設けてほしい

分かりました、いいですよ!

やったー、ありがとう!

え、そんなに簡単にルールを改変してくれるの…?

スライド 7 / 9

特別ルール

それでは、

  • に同じ料理が登場したら、
  • 自動的に を、まだ使われてない料理にランダムに変える。

という特別ルールを設けましょう。

に同じ料理が登場したら、
自動的に がまだ使われてない料理に
ランダムに変わる

つまり、先ほどのように に同じ料理が登場した場合…

に同じ料理があります
1
1
1
1
13
2
23
1

サンドイッチ が自動的に別の料理に変わります。

何に変わるかについてですが、まだ使われていない料理にランダムに変わります。ここでは、フライドポテト になりました。

特別ルール: を別の料理に
1
1
1
1
13
2
23
1
サンドイッチ が、まだ
使われていないフライドポテト に変わる

これで、 が被らなくなった!

では、最後まで進めてみましょう。早送り を押してみてください:

1
1
1
1
13
2
23
1

やった!無事、 に変換できる弁当箱になった!

右下には がついた が「2
→ 計算箱に変換すると になる
12
2
1

ということは、 を計算できたということだね!

その通りです。では、そろそろ今回のまとめに入りましょう!

スライド 8 / 9

まとめ

前回サヤちゃんが考えた1を足す効果 がある弁当箱は、

1を足す効果 がある弁当箱
13
2
23
1

次の に変換できる弁当箱と組み合わせた場合、

右下には がついた が「1
→ 計算箱に変換すると になる
1
1

に同じ料理があり、そのままだと結果が狂ってしまいます。

の両方にサンドイッチ がある
1
1
1
1
13
2
23
1

しかし、今回から新たに以下の特別ルールが適用されます:

  • に同じ料理が登場したら、
  • 自動的に を、まだ使われてない料理にランダムに変える。
特別ルール: を別の料理に
1
1
1
1
13
2