Beyond the State-of-the-Art

最先端を超えたいと思ってる(大嘘)エンジニアのブログ

Elixirでフィボナッチ数列（不完全）

Qiita Elixir 数学

Qiitaからの移植です。

Elixir初心者です。Elixir学習の一貫としてフィボナッチ数列を実装したので、実装をここに記そうと思います。

フィボナッチ数列の定義

フィボナッチ数列\{ F_n \}の定義をさらっと書いておきます。

\begin{align} F_0 &= 0,\: F_1 = 1,\\\ F_n &= F_{n-1} + F_{n-2} \: (n \geq 2) \end{align}

実装

実際に実装したのはこちらです。

defmodule Fibonacci do
    def of(0), do: 0
    def of(1), do: 1
    def of(n) when n > 1 do
        of(n-1) + of(n-2)
    end

    def first_of(n) when n > 0 do
        Enum.map(for i <- 0..n-1 do i end, fn x -> of x end)
    end
end

Fibonacci.of関数で、フィボナッチ数列の項F_nを実現しています。

Fibonacci.first_of関数は、フィボナッチ数列の最初のn個の項をリストを返す関数です。

for i <- 0..n-1 do i end

で、0から始まるn個の整数のリストを生成して、Enum.mapでフィボナッチ数列に変換しています。

実行

iex fibonacci.exsで対話シェルを起動し、Fibonacci.first_ofを実行してみます。

iex(1)> Fibonacci.first_of 1
[0]
iex(2)> Fibonacci.first_of 2
[0, 1]
iex(3)> Fibonacci.first_of 3
[0, 1, 1]
iex(4)> Fibonacci.first_of 10
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

うまくいってそうですね。

最後に

Fibonacci.first_ofの実装だと、計算に無駄があります。例えば、リストの10番目の要素F_9を計算するときは、すでに値がわかっている8、9番目の要素F_7,F_8だけを使って計算すればよいですが、上の実装ではそのようになっていません。F_9の計算にわざわざF_0までたどって計算しています。

リストをうまく操作する関数を定義すればよいのですが、今の自分のElixir力では難しいので、記事はここで終わらせます。

追記(2020/03/29)

@piacerex さんより

以下が、続き的な感じですかねー

https://qiita.com/t-manome/items/34c4bc22b029ebfb89b2 https://qiita.com/bakenezumi/items/fe767263630c670f8eff https://qiita.com/melpon/items/2d58f1b1b242ef7c1074

「メモ化」が高速化にかなり有効です