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

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

中級その5: 1を引く

スライド 1 / 9

返してもらった計算箱は…

では、計算箱を返してやろう!

返してもらった計算箱

あれ…これだけか?

これは「1を足す機能 」がある計算箱だけど…

「1を引く機能 」がある計算箱や、「繰り返しの機能 」がある計算箱はどこにいったんだ?

1を引く機能
繰り返しの機能

それらは、まだ返すわけにはいかないな。

いまお前たちに返せるのは、「1を足す機能 」がある計算箱だけだ。

な、なんだってー!

話が違うじゃないか!さっきの問題を解いたら、計算箱を返してくれると言っただろう?

計算箱を返すとは言ったが…計算箱のすべての機能を返すとは言っていないからな!

そ、そんなー!嘘つきじゃないか!

まあ、わたしは悪魔だからな。

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

中級その4·
·上級その1
スライド 2 / 9

どうすればいい?

じゃあ、どうしたらすべての機能を返してもらえるんだ?

そうだな…先ほどの問題ではお前たちに、計算箱の「1を足す機能 」を弁当箱で再現してもらったよな。

計算箱の「1を足す機能 」を…
弁当箱で再現した
1
に変換できる弁当箱
1
13
2
23
1

だから、「1を引く機能 」や「繰り返しの機能 」を返してほしかったら、それらを同じように弁当箱で再現してみることだな!

1を引く機能
弁当箱で再現
繰り返しの機能
弁当箱で再現

えミ

「1を足す機能 」を再現するのにも苦戦したのに、「1を引く機能 」や「繰り返しの機能 」を再現するなんて、できっこないよ!

だったら諦めることだな。

で、でも…「1を引く機能 」や「繰り返しの機能 」がないと、引き算や、大きな数の足し算・引き算ができないよ!

俺らは計算箱がないと何もできないんだ!

頑張って弁当箱で再現するしかないのか…

スライド 3 / 9

「1を引く機能 」 を再現するヒント

もちろん、ヒント無しでやれとは言わん。前回同様、ヒントを出してやろうじゃないか。

ミニオン、ヒントを説明したまえ!

わかりました。では、「1を引く機能 」 を弁当箱で再現するヒントを教えましょう!

「1を引く機能 」を
どうやって再現する?

「1を引く機能 」を弁当箱で再現するには、以下の弁当箱にある に、ある法則に基づいて料理を入れる必要があります。

それぞれの に、
ある法則に基づいて料理を入れると、
「1を引く機能 」を
再現することができる
3
2
1
12
2
1
123

なんか、めちゃくちゃ複雑な弁当箱だな…

複雑ですが、正しく に料理を当てはめることができれば、以下のように1を引く計算を行うことができます。

に変換できる弁当箱と
合体させ…
1
に変換できる弁当箱
1
3
2
1
12
2
1
123
実行 すると、
に変換できる弁当箱になる
に変換できる弁当箱

では、 にそれぞれ何が入るか考えてみてください!

うーん、こんな複雑な弁当箱の を正しい法則で埋めるなんて…何日かかってもできなさそうだ!

スライド 4 / 9

サヤちゃんが考えた弁当箱

村人たちが困っていると、またサヤちゃんが何かひらめいたようです。

ねえねえ、サヤも試しにやってみたんだけど…

え…サヤちゃん、まさか答えが分かったというのかい?

とりあえずこれを見てみて!

それぞれの に…
3
2
1
12
2
1
123
次のように料理を入れてみた!
3
2
1
12
2
1
123

ふむふむ…まさか今回も一発で正解なんてことはありえないと思うけど、とりあえず試してみるか。

まず、 に変換できる弁当箱と合体させてみよう!

それで、結果が になれば、 を計算できるということだよね。

に変換できる弁当箱と
合体させて…
1
に変換できる弁当箱
1
3
2
1
12
2
1
123
実行したときに、 に変換できる
弁当箱になれば、 を
計算できるので成功
それ以外なら失敗

では、こちらの に変換できる弁当箱と合体させて、実行 してみよう!

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

合体させるとこうなるよ!

に変換できる弁当箱と合体
1
1
1
1
3
2
1
12
2
1
123

よし、実行 してみよう!

スライド 5 / 9

実行 してみると…

それでは、実行 を押してみてください。途中までスキップすることも可能です。

1
1
1
1
3
2
1
12
2
1
123

複雑すぎて、目で追うのがしんどい…

すべてを目で追う必要はないですよ!なんとなく、「へー、こんなふうに進んでいくんだ」と思っていただければ大丈夫です。

それより見てみて!途中で 上 と 中 が同じ ピザ になったよ!

上 中 に同じ料理があります
1
上
上
塌
1
12
右
中
2
右
右
1

前回と同じように特別ルールで、上 が別の料理に変わるんだよね。

特別ルールを実行するには、次へ を押してみてください!

上 中 に同じ料理があります
1
上
上
塌
1
12
右
中
2
右
右
1

そうですね!結果が狂わないように、上 の ピザ を お寿司 に変えました。

では、実行 して最後まで見てみましょう!

1
上
上
塌
1
12
右
中
2
右
右
1

最終的に残った以下の弁当箱は、 に変換できる弁当箱です!

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

ということは、サヤちゃんの弁当箱は…

  • に変換できる弁当箱と合体させて実行すると、
  • に変換できる弁当箱になる

ということですね。

に変換できる弁当箱と
サヤちゃんの弁当箱を合体させ…
1
に変換できる弁当箱
1
3
2
1
12
2
1
123
実行すると、
に変換できる弁当箱になる
に変換できる弁当箱

つまり、 が計算できたので、成功です!

やったー!

す、すごい…!

スライド 6 / 9

はできる?

ぐぬぬ…しかし、 が計算できたからといって、「1を引く機能 」を再現できたとはまだ言い切れないぞ。

たとえば、 は計算できるのかな?

に変換できる弁当箱と
サヤちゃんの弁当箱を合体させ…
1
に変換できる弁当箱
1
3
2
1
12
2
1
123
実行したときに、 に変換できる
弁当箱になれば成功
それ以外なら失敗

じゃあ、 に変換できる弁当箱と合体させてみるね!

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

合体させるとこうなるよ!

に変換できる弁当箱と合体
1
12
2
1
1
3
2
1
12
2
1
123

では、実行してみよう!

  • 今回は、最後まで止まらずに実行するね!
  • 複雑なので、目で追わなくても大丈夫だよ!
  • ちょっと時間がかかるので、待てない方は下の「最後までスキップ →」を押してね!

実行 を押してみて!

1
12
2
1
1
3
2
1
12
2
1
123

最終的に残った以下の弁当箱は、 に変換できる弁当箱です!

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

ということは、サヤちゃんの弁当箱は…

  • に変換できる弁当箱と合体させて実行すると、
  • に変換できる弁当箱になる

ということですね。

に変換できる弁当箱と
サヤちゃんの弁当箱を合体させ…
1
に変換できる弁当箱
1
3
2
1
12
2
1
123
実行すると、
に変換できる弁当箱になる
に変換できる弁当箱

つまり、 が計算できたので、またしても成功です!

わーい、わーい!

ぐぬぬ…

スライド 7 / 9

「1を引く機能 」を再現できた!

まさか、こうも簡単に正解されるとは思わなかったが…

サヤちゃんが考えた弁当箱は、 「1を引く機能 」 を再現できる弁当箱だ!

「1を引く機能 」 は…
サヤちゃんが考えた弁当箱で、
再現できる!
1
に変換できる弁当箱
1
3
2
1
12
2
1
123

やった!ということは、正解だね!

よくこんなの分かったなあ。サヤちゃんは天才なのかもしれない!

そんなことないよ!でも、これで「1を引く機能 」を再現できたね!

計算箱の「1を引く機能 」は、
弁当箱で「再現」することができる

ちなみに、今回の「1を引く機能 」を再現する問題も、超難問です。だから、サヤちゃんのように答えを思いつけなくても大丈夫です。

前回話した通り、答えを思いつけなくても、答えを見て、「なるほど、そういうことだったのか」と理解できれば、コンピュータサイエンスを学ぶ素養は十分すぎるほどあります。

ちなみに: 「1を引く機能 」を再現できる弁当箱は、 サヤちゃんが考えた弁当箱以外にもあります。つまり、正解は他にもあるのです。

気になる方は、↓の「続きを読む」を押してみてください。 (読まなくても先に進めます!)

スライド 8 / 9

中級はここまで!

どうだ、「1を引く機能 」も、弁当箱で再現したぞ!(やったのは俺らじゃなくて サヤちゃんだけど…)

約束通り、「1を引く機能 」がある計算箱も返してもらう!

ぐぬぬ…では、返してやろう!

やったー!

「1を引く機能 」も返してもらった!

しかし、「繰り返しの機能 」がある計算箱は、まだ返すわけにはいかないな。

返してほしかったら、これらも弁当箱で再現してみるんだな!

を 回
繰り返す
弁当箱で再現
を 回
繰り返す