Posted at

Elixirでフィボナッチ数列(不完全)

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}


実装

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


fibonacci.exs

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力では難しいので、記事はここで終わらせます。