数列のAn、拒否反応出るかもしれませんが、

こんにちは！

京都開発研究所受託プロダクトチームのインターン生、村高歩夢です！

本日は本日はガーディアン独自の、そして自慢のcms、OWLetでFAQページをパーツ化しました！

つまり、cms（web専門知識という魔法を持たないマグルの方でも簡単にホームページ制作ができるシステム）でマグルの方々がFAQページを作成できるようにするためのテンプレートを作成してました！

まだOWLetの操作に手間取っていますが、日々新しいことを覚えることができるので楽しいです。

今日はね、先週説明できなかった動的計画法のリベンジもしたいわけですが、動的計画法、絶対活動日記で説明できる重さじゃないんだよな。

できるだけ分かりやすく説明したいので、今日は動的計画法を使う場面について説明します！

さて、フィボナッチ数列って知ってます？

まだ諦めないで！難しいのは名前だけです。

ある値がその一つ前の数字と二つ前の数字を足し算した値になる並び方です。具体的には

1番目を0、２番目を1とすると3番目は0+1=1、4番目は1+1=2、5番目は1+2=3、6番目は・・・と続いていきます。

したがって、この数列は0,1,1,2,3,5,8,13,・・・となるわけです。

簡単でしょ？

で、この数列を式にすると

N番目の数をAn（例えば４番目はA4）とすると

An = An-1 + An-2

もう少し頑張って、僕も辛いです。。

これをプログラミングで動的計画法ではなく純粋に書くと

An-1を計算し、次にAn-2を計算して二つを足し合わせます。

ここで問題なのが、じゃあAn-1とAn-2どうやって計算するん？ってことなんですね。

みなさん、よく考えてください？An-1の前の数字とその前の数字を足せば良いんです。

てことは、

An-1 = An-2 + An-3

An-2 = An-3 + An-4

これを A0になるまで計算します！

でもこれって僕の二度寝くらい無駄なんですよ。

そう二度！

An = An-1 + An-2

これ、An-2の値は二度計算してるんです。

ほら、An-1=An-2 + An-3なので

An = (An-2 + An-3) + An-2

ね？

なんなら、最後の方は10回くらい同じ計算してます。

こんな無駄な計算してたらパソコンでも答えが出るまでに何十秒もかかってしまうんですよね。

この状況で使えるアルゴリズムが動的計画法！

計算が被らず、一回だけでいいのでめちゃくちゃ処理が早くなります。

以上！

みなさん。お疲れ様です！

理解できました？難しいですよね！ではまた！

---------------------------------------------------------------------------------------------

インターン募集ページ: https://guardian.jpn.com/recruit/intern/

メンバー紹介ページ：https://guardian.jpn.com/member/Murataka_Ayumu/

---------------------------------------------------------------------------------------------