漸化式(ぜんかしき)って何よ(^~^)?

あぼぼばぼおぼぼぼぼぼ(^q^) どんどんどふどふどどどどどどんどんどふどふ(^q^) 公開下書き

20210124shogi2a2b1.png
「 漸化式(ぜんかしき)って何よ?」

kifuwarabe-futsu.png
「 1つ前の計算結果を使うような式だぜ」

ohkina-hiyoko-futsu.png
「 ラーメン食べ郎は そんな説明で分からないのよ。
マンガで説明されないと 納得できないの」

ramen-tabero-futsu2.png
「 漸化式(recurrence relation)を見せてくれだぜ」

kifuwarabe-futsu.png
「 フィボナッチ数列と カタラン数が 超有名かな。
パスカルの三角形は 漸化式といっていいのかな」

ohkina-hiyoko-futsu.png
「 数式を見せると ラーメン食べ郎は 拒否反応を起こして 床にラーメンを吐きまくって倒れるわよ」

20210702math1.png

kifuwarabe-futsu.png
「 👆 これが フィボナッチ数めがね だぜ。
これをかけると フィボナッチ数列が視えるぜ」

ramen-tabero-futsu2.png
「 そういうやつで頼む」

20210702math3.png

kifuwarabe-futsu.png
「 👆 これが カタラン数めがね だぜ。
これをかけると カタラン数列が視えるぜ」

ramen-tabero-futsu2.png
「 ぜったい分からせてやるぞ、というやる気のあるデザインだぜ!」

20210702math4.png

kifuwarabe-futsu.png
「 👆 これが パスカルの三角形めがね だぜ。
これをかけると パスカルの三角形が視えるぜ」

ramen-tabero-futsu2.png
「 おおっ! なんだか 視えてきた気がしたぜ!」

kifuwarabe-futsu.png
「 ここで、 美味しい数列を食べるためには ひとてま 仕込みが必要だぜ」

ramen-tabero-futsu2.png
「 仕込んでくれだぜ」

20210702math5.png

kifuwarabe-futsu.png
「 👆 これが フィボナッチ数ベースケース だぜ。
これを仕込むと フィボナッチ数は 美味しくなる」

ramen-tabero-futsu2.png
「 …………」

20210702math6.png

kifuwarabe-futsu.png
「 👆 これが カタラン数ベースケース だぜ。
これを仕込むと カタラン数は 美味しくなる」

ramen-tabero-futsu2.png
「 …………」

20210702math7.png

kifuwarabe-futsu.png
「 👆 これが パスカルの三角形ベースケース だぜ。
これを仕込むと パスカルの三角形は 美味しくなる」

ramen-tabero-futsu2.png
「 …………」

ramen-tabero-futsu2.png
「 どうやって 食べるんだぜ!」

kifuwarabe-futsu.png
「 赤色のレンズと 緑色のレンズで ベースケースを 覗き込んでみてくれだぜ」

20210702math8.png

ramen-tabero-futsu2.png
「 👆 …………?」

20210702math9.png

ramen-tabero-futsu2.png
「 👆 …………?」

20210702math10.png

ramen-tabero-futsu2.png
「 👆 …………?」

kifuwarabe-futsu.png
「 はい、ここで 水色のレンズには 赤いレンズと 緑色のレンズの数を足した数が 視えてくるぜ」

20210702math11.png

ramen-tabero-futsu2.png
「 👆 おおっ! 視えてきた 視えてきた」

20210702math12.png

ramen-tabero-futsu2.png
「 👆 視えてきたぜ!」

20210702math13.png

ramen-tabero-futsu2.png
「 👆 どういう仕組みなんだぜ!?」

ohkina-hiyoko-futsu.png
「 足し算よ」

kifuwarabe-futsu.png
「 じゃあ フィボナッチ数めがね を 1マス右に ずらしてみてくれだぜ」

20210702math14.png

ramen-tabero-futsu2.png
「 👆 おおっ! 3 が視えてきたぜ!」

kifuwarabe-futsu.png
「 じゃあ カタラン数めがね を 1マス下に ずらしてみてくれだぜ。
カタラン数の左端のマスには 1 が入っているものとするぜ」

20210702math15.png

ramen-tabero-futsu2.png
「 👆 3 が視えたぜ!」

20210702math16.png

kifuwarabe-futsu.png
「 👆 カタラン数のレギュレーションなんだが、マスの全体は 三角形みたいに並んでいて、右端と、その1つ隣は 同じ数になるものとしてくれだぜ」

ramen-tabero-futsu2.png
「 面白」

kifuwarabe-futsu.png
「 これで カタラン数めがね が右に移動できるようになっただろ。
右に移動してみてくれだぜ」

20210702math17.png

ramen-tabero-futsu2.png
「 👆 5 が視えてきたぜ!」

20210702math18.png

kifuwarabe-futsu.png
「 👆 じゃあ パスカルの三角形のレギュレーションも説明するぜ。
マスの全体は 三角形みたいに並んでいて、左と右の両端は 1 が入っているものとしてくれだぜ」

kifuwarabe-futsu.png
「 これで パスカルの三角形めがね が下に移動できるようになっただろ。
左下に移動してみてくれだぜ」

20210702math19.png

ramen-tabero-futsu2.png
「 👆 3 が視えたぜ!」

20210702math20.png

20210702math21.png

20210702math22a1.png

ohkina-hiyoko-futsu.png
「 👆 遊び終わったのなら 片づけなさい!」

ramen-tabero-futsu2.png
「 漸化式なんか覚えて 何に使うんだぜ?」

kifuwarabe-futsu.png
「 うしろのマスを見てみろだぜ」

20210702math23.png

20210702math24.png

20210702math25.png

kifuwarabe-futsu.png
「 👆 計算結果を 記憶しておく マスのようなもの。 通称 メモ だぜ」

kifuwarabe-futsu.png
「 こういう メモ をさくっと コーディング できる能力が
のちに覚えることになる ダイナミック・プログラミング に生きてくるんだぜ」

ohkina-hiyoko-futsu.png
「 メモ って どうやって作んの?」

20210702math26.png

ramen-tabero-futsu2.png
「 👆 フィボナッチ数列のメモは 配列で十分だぜ」

ohkina-hiyoko-futsu.png
「 カタラン数のメモ って どうやって作んの?」

ramen-tabero-futsu2.png
「 三角形みたいな配列を作らないといけないのかだぜ?」

20210702math27a1.png

kifuwarabe-futsu.png
「 👆 カタラン数列って 上図の 水色のところだぜ?」

ramen-tabero-futsu2.png
「 おっ、配列で いけそう」

ohkina-hiyoko-futsu.png
「 でも 白色のマスもないと 水色のマスを 計算できなくない?」

20210702math30a1.png

ramen-tabero-futsu2.png
「 👆 じゃあ 2次元配列でも使うかな。 その半分だけ使えばいいだろ」

ohkina-hiyoko-futsu.png
「 パスカルの三角形のメモ って どうやって作んの?」

20210702math28.png

ramen-tabero-futsu2.png
「 👆 ななめに傾けてみると……」

20210702math29.png

ramen-tabero-futsu2.png
「 👆 二次元配列で いけそうだな」

kifuwarabe-futsu.png
「 じゃあ そのメモを 埋めろだぜ」

ramen-tabero-futsu2.png
「 すべてのマスを めがね で視ればいいんだろ」

kifuwarabe-futsu.png
「 やってみろだぜ」

20210702math31.png

ramen-tabero-futsu2.png
「 👆 じゃあ マス目の 番地の呼び方を決めようぜ。
フィボナッチ数列は 添え字の n が 1 と 2 のときをベースケースにする例があるので それに倣(なら)おう」

20210702math32a2.png

ramen-tabero-futsu2.png
「 👆 カタラン数列では 添え字の n が 1 と 2 のときを 数列の先頭 1, 1 に合わせる例があるので それに倣おう。
添え字の n は 行でもあるし、カタラン数列の添え字でもあるぜ。
ややこしいんで 添え字の0番 は使わないものとして、
添え字の i は 先頭を 1 として列を指すとでもしておこうぜ。 べつに使うアルファベットに決まりはないけどな」

20210702math33.png

ramen-tabero-futsu2.png
「 👆 パスカルの三角形は 番地を 添え字 i, j で示すのは思いつくんだが、
斜めを示す 簡単な方法は 頭を悩ますと思う」

20210702math34.png

ramen-tabero-futsu2.png
「 👆 例えば 上から4段目を見てほしい。 (1 4), (2 3), (3 2), (4 1) という番地が ナナメ1列だぜ」

ohkina-hiyoko-futsu.png
「 (i, size+1-i) で指定すればいいのよ」

20210702math35.png

ramen-tabero-futsu2.png
「 👆 フィボナッチ数めがね の水色のレンズを 添え字n番地 としようぜ?
カタラン数めがね の水色のレンズは 表と見比べてくれだぜ。
パスカルの三角形めがね では i, j 番地」

20210702math36.png

ramen-tabero-futsu2.png
「 👆 水色のレンズの番地を決めたら、これで 赤色のレンズと、水色のレンズの 番地も 決めれたな」

ohkina-hiyoko-futsu.png
「 赤色のレンズと 水色のレンズは マイナスの番地を指してるけど、
メモの外側を指してしまわない?」

20210702math37.png

20210702math38a1.png

20210702math39.png

ramen-tabero-futsu2.png
「 👆 ベースケース より後ろ?に戻そうとするなだぜ。計算を停止しろだぜ。
どこを ベースケース と呼ぶかは 見方で1つぐらいずれるから ガチャガチャしろだぜ」

ohkina-hiyoko-futsu.png
「 カタラン数を めがね で視ていくときの動きって むずかしくない?」

カタラン数めがね の動き

20210702math40.png

ramen-tabero-futsu2.png
「 👆 最初は ここだな。
赤色のレンズの 1 と、緑色のレンズの 1 は最初から入っているので 初項 と呼ぶらしいぜ。
水色のレンズの 2 は、初項の次だから 第2項 と呼ぶらしいぜ」

20210702math40a1.png

ramen-tabero-futsu2.png
「 👆 めがねを 下の段に 落としてみろだぜ。 水色のレンズの i は 2 だな」

20210702math40a2.png

ramen-tabero-futsu2.png
「 👆 i が n-1 になるまで、左へ めがねを ずらしていけだぜ。
あとは n が1つ増えるたびに 以下同様 だぜ」

ohkina-hiyoko-futsu.png
「 そんなもんで いいのかしら?」

kifuwarabe-futsu.png
「 AtCoder の ABC の制限時間の中で コーディングを正しくやりきる自信が無いぜ」

ohkina-hiyoko-futsu.png
「 それが コーディングのコンテストなのよ」

等差数列と、等比数列

kifuwarabe-futsu.png
「 さっきやった フィボナッチ数列、カタラン数列、パスカルの三角形 は、 階差数列 と呼ばれるらしいぜ」

ramen-tabero-futsu2.png
「 フーン」

kifuwarabe-futsu.png
「 それ以外にも 漸化式には 等差数列、 等比数列 があるらしいぜ」

ramen-tabero-futsu2.png
「 どんな めがね だぜ?」

20210703math41a1.png

kifuwarabe-futsu.png
「 👆 お父んの期待に応えられないかもしれないが、
等差数列のめがねは 1個だけ、
等比数列のめがねも 1個だけ だぜ」

ramen-tabero-futsu2.png
「 そんな……」

20210703math42.png

kifuwarabe-futsu.png
「 👆 等差数列のメモも、 等比数列のメモも、 フィボナッチ数列で使ったことのある 一直線のやつしか無さそうだぜ。
n は 1 から始まる」

ramen-tabero-futsu2.png
「 なんてこった…… 三角形とか 四角形とか いっぱいないのかだぜ?」

20210703math42a1.png

kifuwarabe-futsu.png
「 👆 左端、つまり n = 1 のところに 初めから数を入れておけだぜ。 これ、 初項

kifuwarabe-futsu.png
「 じゃあ、めがねで覗き込んでくれだぜ」

20210703math43.png

ramen-tabero-futsu2.png
「 👆 …………?」

20210703math44.png

ramen-tabero-futsu2.png
「 👆 …………?」

kifuwarabe-futsu.png
「 その めがね の頭に ツマミが付いてるだろ。 2 ぐらい ひねってくれだぜ」

20210703math45.png

ramen-tabero-futsu2.png
「 👆 7 が視えたぜ!」

20210703math46.png

ramen-tabero-futsu2.png
「 👆 10 が視えたぜ!」

ramen-tabero-futsu2.png
「 どういう仕組みなんだぜ!」

ohkina-hiyoko-futsu.png
「 足し算と 掛け算よ」

kifuwarabe-futsu.png
「 じゃあ、めがねを 1つ右に ずらしてくれだぜ」

20210703math47.png

ramen-tabero-futsu2.png
「 👆 9 が視えたぜ!」

20210703math48.png

ramen-tabero-futsu2.png
「 👆 20 が視えたぜ!」

20210703math49.png

20210703math50.png

ohkina-hiyoko-futsu.png
「 👆 遊び終わったのなら 片づけなさい!」

ramen-tabero-futsu2.png
「 等差数列めがね や、 等比数列めがね を覚えて 何に使うんだぜ!」

kifuwarabe-futsu.png
「 ほとんどの 漸化式 は解けないが、
解くことができる 漸化式は 階差数列、等差数列、等比数列 の3つのうちの どれか なんだぜ」

kifuwarabe-futsu.png
「 この3つの めがね を使いこなすことが 漸化式 をマスターするのに 必要なんだぜ」

ramen-tabero-futsu2.png
「 じゃあ マスターする」

TODO 特殊解型 漸化式

ramen-tabero-futsu2.png
「 (むずかしすぎる……)」

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事