Qiitaからの移植です。
Elixir初心者です。Elixir学習の一貫としてフィボナッチ数列を実装したので、実装をここに記そうと思います。
フィボナッチ数列の定義
フィボナッチ数列の定義をさらっと書いておきます。
実装
実際に実装したのはこちらです。
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
関数で、フィボナッチ数列の項を実現しています。
Fibonacci.first_of
関数は、フィボナッチ数列の最初の個の項をリストを返す関数です。
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番目の要素を計算するときは、すでに値がわかっている8、9番目の要素
だけを使って計算すればよいですが、上の実装ではそのようになっていません。
の計算にわざわざ
までたどって計算しています。
リストをうまく操作する関数を定義すればよいのですが、今の自分のElixir力では難しいので、記事はここで終わらせます。
追記(2020/03/29)
@piacerex さんより
以下が、続き的な感じですかねー
https://qiita.com/t-manome/items/34c4bc22b029ebfb89b2 https://qiita.com/bakenezumi/items/fe767263630c670f8eff https://qiita.com/melpon/items/2d58f1b1b242ef7c1074
「メモ化」が高速化にかなり有効です