上級その2

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

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

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

スライド 1 / 14

難易度が上がります

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

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

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

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

とても複雑な弁当箱

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


繰り返す

繰り返す

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

実行してから 計算箱に変換
するとどうなる?
1
123
3
2
1
1
45
5
13
2
23
1
3
12
2
1
2
1
1234

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

ここで質問です。上の弁当箱を、実行してから 計算箱に変換 すると、どんな結果になるでしょう?

そんなの、すぐ答えられるわけないだろう!こんな複雑な弁当箱、実行 するのもひと苦労だよ!

サヤはすぐ分かったよ!実行してから 計算箱に変換 すると、結果は になるんじゃない?

結果は になると思う!

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

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

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

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

スライド 3 / 14

計算箱に置き換える・その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

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

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

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

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

なるほど…!

スライド 4 / 14

計算箱に置き換える・その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 / 14

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

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

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

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

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

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

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

以下のように置き換えてみるよ。複雑なので、↓の置き換え方は読み飛ばしても大丈夫!

  • 上にある の部分へ
  • その下にある の部分へ
  • 一番下の の部分へ

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

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

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

スライド 6 / 14

あとは実行するだけ

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

1
1
12
2
1

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

早送り を押してみて

12
2
1

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

結果は になった!

たしかに…!

スライド 7 / 14

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

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

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

サヤちゃんは、もともとの弁当箱を…
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 / 14

そのまま実行してみる

では、もともとの弁当箱を早送り してみましょう!

  • ステップが非常に多いので、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 / 14

ここまでの振り返り

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

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

弁当箱の一部分を…
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
<