中級その1

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

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

中級その2: 1を足す効果

スライド 1 / 16

難易度が急激に上がります

このページから難易度が急激に上がります。弁当箱も、以前に比べて複雑になります。

難易度が上がり、弁当箱も複雑に

ただ、内容を完全に理解する必要はありません。少しくらい分からなくても、雰囲気で読み進めていただいて大丈夫です。また、先に進んでから読み返すことで理解できる場合もあるので、分からなくてもとりあえず先に進んでみてください。

完全に理解する必要はありません!

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

中級その1·
·中級その3
スライド 2 / 16

問題の説明

では約束通り、これから出す問題に答えることができたら、計算箱を返してやろう!

これから出す難しい問題に
答えられたら計算箱を返してやろう!

この問題は非常に難しいから覚悟するんだな。ミニオン、問題を説明するんだ!

わかりました。まず、こちらの弁当箱をご覧ください

がたくさんありますが、それぞれの には何らかの料理が入ります。

それぞれの には
何らかの料理が入る
13
2
23
1

何だか複雑そうな弁当箱だなあ…

にはそれぞれ何の料理が入るの?

それが今回の問題です!村人のみなさんには、 には何の料理が入るかを当ててもらいます。

に何が入るかを
当ててもらいます!
13
2
23
1

でも、まだ何の情報もないから… に何が入るかなんて分かんないよ。

その通りです。まだ説明することがありますから。では、続けますね!

スライド 3 / 16

1を足す効果

先ほどの弁当箱は、それぞれの に、ある法則に基づいて料理を入れると…

1を足す効果 がある弁当箱になります。

それぞれの に、
ある法則に基づいて料理を入れると、
1を足す効果 がある弁当箱になる
13
2
23
1

背景に の模様がついた!

そうですね。背景にある の模様は単に、1を足す効果 があるということを表しているだけです。

その1を足す効果 ってどういう効果なの?

これから説明しますね!

スライド 4 / 16

になる

こちらの弁当箱をご覧ください:

1
1

前回の復習ですが、この弁当箱は、ぼくが計算箱に変換すると になります。

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

では上の弁当箱を、先ほどの1を足す効果 がある弁当箱と合体させてみます

1を足す効果 がある弁当箱と合体
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 / 16

になる

続いて、こちらの弁当箱をご覧ください

12
2
1

この弁当箱は、ぼくが計算箱に変換すると になります。

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

この弁当箱も、先ほどの1を足す効果 がある弁当箱と合体させてみました。

1を足す効果 がある弁当箱と合体
1
12
2
1
1
13
2
23
1

こちらを「実行してから 計算箱に変換 」するとどうなるか確かめてみてください!

1
12
2
1
1
13
2
23
1

になった!

そうなんです!まとめると、以下のようになります。

に変換できる弁当箱と、
1を足す効果 がある弁当箱を合体させ…
1
に変換できる弁当箱
1
13
2
23
1
実行してから 計算箱に変換
すると、結果は になる

ざっくり言うと、今度は になったのです。

ざっくり言うと、 になった
スライド 6 / 16

まとめ

まとめると、

  • ある数字 に変換できる弁当箱と、
  • 1を足す効果 がある弁当箱を合体させ、
  • 実行してから 計算箱に変換 すると、

結果は になるのです。

に変換できる弁当箱と、
1を足す効果 がある弁当箱を合体させ…
1
に変換できる弁当箱
1
13
2
23
1
実行してから 計算箱に変換
すると、結果は になる
スライド 7 / 16

計算箱の と同じようなもの

ここで思い出してほしいのですが、計算箱では、 を使えば、「1を足す」計算を行うことができましたよね

計算箱の場合、 を使えば
「1を足す」計算ができる

すなわち、この 1を足す効果 がある弁当箱は…

この 1を足す効果 がある弁当箱は…
13
2
23
1

計算箱における と同じようなもの、と言えるでしょう。

計算箱における、 と同じようなもの
スライド 8 / 16

計算箱を賭けた問題

では、ここで問題です。この弁当箱に、どのような法則に基づいて に料理を入れると…

どのような法則に基づいて
に料理を入れると…
13
2
23
1

先ほどのような、1を足す効果 がある弁当箱になるでしょう?

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

つまり、それぞれの に何を入れたら、1を足す効果 があるか当てろってこと?

それぞれの に何を入れたら
1を足す効果 がある弁当箱になる?
1
に変換できる弁当箱
1
13
2
23
1

はい、その通りです!ある法則に基づいて に料理を入れた時に限り1を足す効果 がある弁当箱になります。

それがどんな法則が、当ててみよう!という問題です。

この問題こそが、以前から話していた「難しい問題」だ。これを解けたら、約束通り計算箱を返してやろう!

この問題が解けたら、計算箱を返してやろう!
スライド 9 / 16

試しに適当な料理を入れてみる

うーん…問題を完全に理解できた自信がないし、どうやって解けばいいかさっぱり分からない!

大丈夫、安心してください!

試しに、 に適当な料理を入れてみると、問題を理解できると思います。

に適当な料理を入れてみて下さい!
13
2
23
1

わかった。じゃあとりあえず、 に適当な料理を入れてみよう。

お寿司 サンドイッチ ハンバーガー を適当な組み合わせで に入れてみたよ。

を適当に に入れてみた
13
2
23
1

この弁当箱に、1を足す効果 があれば成功 、なければ失敗 ということかな?

そうですね。そして、1を足す効果 があるかどうかを確かめるには、まず が計算できるかを確かめてみます。

が計算できるか確かめる

つまり、以下のように に変換できる弁当箱と合体させたときに…

結果が になれば1を足す効果 があるので成功 、 それ以外なら失敗 というわけです。

に変換できる弁当箱と、
先ほどの弁当箱を合体させ…
1
に変換できる弁当箱
1
13
2
23
1
実行してから 計算箱に変換
して、結果が になれば
1を足す効果 があるので成功
それ以外なら失敗
スライド 10 / 16

1を足す効果 があるかチェック

では、 が計算できるか確かめるために、冒頭にも登場した、 に変換できる弁当箱を使って試してみましょう。

に変換できる弁当箱
1
1

これを先ほどの弁当箱と組み合わせて、実行してから 計算箱に変換 し、 を計算できればいいんだな。

すなわち、結果が になれば成功 、それ以外なら失敗 というわけか。

に変換できる弁当箱と、
先ほどの弁当箱を合体させ…
1
1
1
1
13
2
23
1
実行してから 計算箱に変換
して、結果が になれば成功
それ以外なら失敗

では、上の弁当箱を実行したらどうなるか見ていこう!

スライド 11 / 16

初級編の復習

今回の弁当箱では、初級その5で学んだ法則が登場します。

覚えていなくても、早送りで勝手に進んでくれるので大丈夫ですが、いちおう復習をしておきましょう!

細かい法則1: 1 のペアが左右ふたつ以上ある場合は、一番左のペアからはじめます。

1 のペアが左右ふたつ以上ある場合は、
一番左の 1 のペアからはじめる
1
1
1
1

補足: 1 のペアが弁当箱の左端にない場合は、内側の 1 のペアからはじめる。

1 のペアが弁当箱の左端にない場合は、
内側の 1 のペアからはじめる
1
1

細かい法則2: 下段にひとつの料理しかなく、1 のペアからはじめられない場合、2 のペアからはじめます。

下段にひとつの料理しかなく、
1 のペアからはじめられない場合、
2 のペアからはじめる
12
2
1
スライド 12 / 16

早送りしてみよう

初級編の復習もしたことだし、先ほど考えた弁当箱に、1を足す効果 があるかどうか見ていこう!

以下のように、 が計算できれば成功 なんだよな。

に変換できる弁当箱と、
先ほどの弁当箱を合体させ…
1
1
1
1
13
2
23
1
実行してから 計算箱に変換
して、結果が になれば成功
それ以外なら失敗

それでは、早送り していきましょう!

まず初級編で説明した通り、1 のペアが左右ふたつ以上ある場合は、一番左の 1 のペアからはじめます。

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

1 のペアが左右ふたつ以上ある場合は、
一番左の 1 のペアからはじめる
1
1
1
1
13
2
23
1

続いて、また 1 のペアからはじめたいのですが、1 のペアの一番下の段にひとつの料理(サンドイッチ )しかないので不可能です。

というわけで、初級編で説明した通り、次は 2 のペアからはじめます。

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

下段にひとつの料理しかなく、
1 のペアからはじめられない場合、
2 のペアからはじめる
13
2
23
1
1
1

次も前回と同じく、2 のペアからはじめます。

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

下段にひとつの料理しかなく、
1 のペアからはじめられない場合、
2 のペアからはじめる
12
2
1
1
1

つまり、最終的に以下のようになりました!

実行結果
12
2
1
スライド 13 / 16

計算箱に変換できない

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

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

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

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

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

右上には の料理がひとつないといけませんが、ここでは になっているので、計算箱に変換できないのです。

右上が ハンバーガー ではなく、
サンドイッチ なので
計算箱に変換できない
12
2
1

ダメか…もし仮に右上がサンドイッチ ではなくてハンバーガー だったら、 に変換できていたのになあ。

も仮にし右上がハンバーガー
だったら、 に変換できていた
12