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

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

上級その3: 一部分を置き換える

スライド 1 / 12

難易度が上がります

このページからまた難易度がアップします。ただ、内容を完全に理解する必要はありません。少しくらい分からなくても、雰囲気で読み進めていただいて大丈夫です。

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

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

上級その2·
·上級その4
スライド 2 / 12

とても複雑な弁当箱

では、これから「繰り返しの機能 」を弁当箱で再現するのに役立つヒントを出していきますね。


繰り返す
弁当箱で再現

繰り返す
弁当箱で再現

まずは、こちらの弁当箱をご覧ください。

複雑な弁当箱
1
123
3
2
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234

めちゃくちゃ複雑な弁当箱だなあ…

ここで質問です。上の弁当箱を実行 すると、どんな結果になるでしょう?

そんなの、すぐ答えられるわけないだろう!こんな複雑な弁当箱の実行結果なんて、見当がつかないよ!

サヤはすぐ分かったよ! に変換できる弁当箱になるんじゃない?

結果は
に変換できる弁当箱になると思う!
に変換できる弁当箱

まさにその通り!サヤちゃん、正解です!

へ?なんでそんな早く正解が分かるの…?

サヤちゃん、まさか一瞬で頭の中で実行 したのかい?

ううん、そんなことはしていないよ。じゃあ、どうやって解いたかを教えてあげるね!

スライド 3 / 12

計算箱に置き換える・その1

まず、一番上の部分に注目してみて!

一番上の部分に注目
1
123
3
2
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234

あ、一番上の部分をよく見ると、これは に変換できる弁当箱だ!

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

そう!だから、とりあえずこれを に置き換えてみるね。

上の部分を に置き換えてみる
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234

次は、右の真ん中の部分に注目してみて!

右の真ん中の部分に注目
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234

右の真ん中の部分をよく見ると、これは に変換できる弁当箱だ!

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

そう!だから、これを に置き換えてみるね。

に置き換えてみる
1
1
45
5
13
2
23
1
3
2
1
1234

なるほど…!

スライド 4 / 12

計算箱に置き換える・その2

次に、この右の黄色の部分に注目してみて!

右の部分に注目
1
1
45
5
13
2
23
1
3
2
1
1234

これはもしかして…中級その3で サヤちゃんが考えた、 「1を足す機能 」 を再現できる弁当箱かな?

サヤちゃんが考えた、
1を足す機能 」 を再現できる弁当箱
13
2
23
1

その通り!だから、この部分をいったん に置き換えるね。

に置き換えてみる
1
1
45
5
3
2
1
1234

なるほど、だいぶシンプルになってきたぞ…

スライド 5 / 12

計算箱に置き換える・その3

最後に、右下の全ての部分に注目してみて!

右下の全ての部分に注目
1
1
45
5
3
2
1
1234

そういればこれは、前回やった「条件分岐の機能 」に変換できる弁当箱と同じだ!

条件分岐の機能 」に
変換できる弁当箱
4
に変換できる弁当箱
3
に変換できる弁当箱
2
1
に変換できる弁当箱
1234

そう!だから、右下の部分を「条件分岐の機能 」に置き換えるんだ。

条件分岐の機能 」に置き換える

以下のように置き換えてみるよ。

置き換え前(右下の部分のみ)
45
5
3
2
1
1234
置き換え後(右下の部分のみ)
12
2
1

置き換えるとこうなります!

条件分岐の機能
の部分を置き換えた後
1
1
12
2
1

なんと、超シンプルになった!

スライド 6 / 12

あとは実行するだけ

あとは、これを実行 するだけだよ。というわけで、実行 を押してみて

1
1
12
2
1

ここまできたら、後は簡単だよね。 だから、 に入っている が残るんだ。

実行 を押してみて

12
2
1

ほらね、サヤがさっき言ったように、最後に が残ったでしょう?

結果は になった!

たしかに…!

スライド 7 / 12

そのまま実行していたら?

しかし…サヤちゃんがとった手法はズルなんじゃないか?

サヤちゃんは、もともとの弁当箱を、それぞれの要素に対応する計算箱に置き換えてから実行したけど…

サヤちゃんは、もともとの弁当箱を…
1
123
3
2
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234
それぞれの要素に対応する計算箱に
置き換えてから実行していた
1
1
12
2
1

もともとの弁当箱を、そのまま実行 しても、結果は同じく になっていたのかな?

もともとの弁当箱を、
そのまま実行 しても…
1
123
3
2
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234
結果は同じく
になっていた?

では、確かめてみましょう!

スライド 8 / 12

そのまま実行してみる

では、もともとの弁当箱を実行 してみましょう!

  • ステップ数が非常に多いので、3倍速で進めます!
  • 実行中は、目に優しくなるように弁当箱を半透明にしています。
  • 待てない方は、「最後までスキップ」を押して下さい!
1
123
3
2
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234

最後に残った以下の弁当箱は、 に変換できる弁当箱ですね。

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

サヤちゃんのやり方でやったときと、結果が同じになった!

ということは、サヤちゃんのやり方は間違ってなかったのか…

そういうことですね!

スライド 9 / 12

ここまでの振り返り

ここで一旦立ち止まって振り返ってみましょう。

さきほどサヤちゃんがやったのは、「弁当箱の一部分を、同じ効果がある計算箱と置き換える」という手法でした。図で説明すると、以下のような感じですね。

弁当箱の一部分を…
1
1
同じ効果がある 計算箱と置き換える
1
1

重要なのは、このように弁当箱の一部分を計算箱と置き換えても、実行したら結果は同じになるということです。

弁当箱の一部分を計算箱と置き換えても…
実行したら
結果は同じになる!

たしかに先ほどの場合は、サヤちゃんの手法を使っても、そのまま実行しても、どちらも結果は になったな。

はい。複雑な弁当箱は、それぞれの部分をシンプルな計算箱に置き換えると分かりやすくなります。

結果は変わらないのだから、積極的に置き換えていくべきということですね。

複雑な弁当箱は…
1
123
3
2
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234
それぞれの部分を
シンプルな計算箱 に置き換えると
分かりやすくなる
1
1
12
2
1
ちなみに、どちらの場合も
実行結果は になる
スライド 10 / 12

繰り返しの機能との関係

でもさあ…質問なんだけど、この話って、「繰り返しの機能 」と何の関係があるの?


繰り返す
弁当箱で再現

繰り返す
弁当箱で再現

すると、サヤちゃんが何かに気づいたようです。

ねえねえ、もしかしたらサヤ、「繰り返しの機能 」を弁当箱で再現できたかもしれない!

繰り返しの機能を再現できたかも!

え!サヤちゃん、本当かい?

うん、それでは説明するね!

スライド 11 / 12

を3回繰り返す

まず、この「繰り返しの機能 」がある計算箱を見てみて!

繰り返しの機能 」がある計算箱

この計算箱は、以下のように を3回繰り返すことにより、 を計算できるわけだよね。

を3回繰り返す
123
3
2
1

これを弁当箱で再現する方法が分かったんだ!

なんと!ぜひ教えてくれ!

スライド 12 / 12

先ほどの弁当箱にいろいろ追加してみる

先ほど登場した、複雑な部分を計算箱に置き換えた弁当箱に注目してみて!

これに変更を加えることで、「繰り返しの機能 」を再現してみるよ。

先ほど登場した弁当箱
1
1
12
2
1

この弁当箱に、以下のようにいろいろ追加してみたの。黄色の部分が追加した部分だよ。

黄色が追加した部分
2
1
1234
4
3
2
1
12
1
12
2
1
1
12
2
1

ふむふむ…何やら複雑になったなあ。

で、これがどうしたっていうの?

実は、上の弁当箱を実行すると、先ほどの「繰り返しの機能 」がある計算箱と全く同じように変化するんだ。

つまり、以下のようになるんだよ。

この弁当箱を実行すると…
2
1
1234
4
3
2
1
12
1
12
2
1
1
12
2
1
繰り返しの機能 」と同じく、
に対して を3回繰り返す
123
3
2
1
つまり、 を計算できる

えー、まさか!本当なのかい?

もし本当だとしたら…これで「繰り返しの機能 」を再現できるということになるけど…

この「繰り返しの機能 」を使った計算箱は…
以下の弁当箱で再現できている?
2
1
1234
4
3
2
1
12
1
12
2
1
1
12
2
1

でも、サヤちゃんが言っていることは正しいのだろうか?

実行して確かめてみないと分からないなあ…

うん、では次のページで実行して確かめてみよう!

次のページへ進む上級その4
上級は残り2ページです!
上級その2
プライバシーポリシー · 当サイトについて · Twemoji