(Erlang) 求不超過 4,000,000 費氏數列偶數總和

在電子郵件論壇有人問 Project Euler 的 Problem #2 ,他用到 Erlang 的 Lazy evaluation 技巧。於是,今天我也寫了一個。首先我先弄一個基本的費氏數字函數。

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fibonacci(0, N, fib(0), fib(1)).
fibonacci(N, N, N_2, _) -> N_2;
fibonacci(N, T, N_2, N_1) when N < 0 -> fibonacci(0,  T, N_2, N_1);
fibonacci(N, T, N_2, N_1) -> fibonacci(N+1, T, N_1, N_2+N_1).

然後我想要產生費氏數列。從 fibonacci/4 我得到一些基本知識是:如果我呼叫 fibonacci(N, N, N_2, N_1) ,答案就會是 N_2 ,而且這有個前提是 N_2 這個底數是正確的。另一項重要的知識是費氏數列前後二數的關係,前一個數字的參數是 { N, T, N_2, N_1 } 則後一個數字參數就是 { N+1, T, N_1, N_2+N_1 } 。由於要計算費氏數列的項數可能非常、非常大,所以數列的產生可以開始用 Lazy evaluation 。而且數列畢竟是有限的,在 Project Euler 的 Problem #2 問題所給的明確限定是上限值 4,000,000 ,所以我做了一個限定數的數列產生函數。

fib_seq(From, Limited_value) ->
    fib_seq_l(From, fib(From), fib(From+1), Limited_value).
fib_seq_l(From, _, _, Limited_value) when From > Limited_value -> [];
fib_seq_l(From, N_2, N_1, Limited_value) when From < 0 ->
    fib_seq_l(0,  N_2, N_1, Limited_value);
fib_seq_l(From, N_2, N_1, Limited_value) ->
    [fibonacci(From, From, N_2, N_1)
     | fun() -> fib_seq_l(From+1, N_1, N_2+N_1, Limited_value end ].

接著,產生的數列要從其中挑出偶數,本來 lists:takewhile/2 可以用,但是基本它不 lazy 。我要一個 lazy 的偶數過濾函數,所以自己做一個。

even_seq_l([]) -> [];
even_seq_l([H|T]) when H rem 2 == 0 ->
    [H|fun() -> even_seq_l(T) end];
even_seq_l([_|T]) ->
    fun() -> even_seq_l(T) end.

所以費氏數列的偶數集合函數是這樣:

even_fib_seq(From, Limited_value) ->
    even_seq_l(fib_seq_l(From , Limited_value)).

執行起來是產生像 [1|#fun<PID>] 這樣的內容,頭是一個數字,但尾是一個函數。這種待解的資料格式要用對應的消費函數來處理:

explode([]) -> [];
explode(L) when is_function(L) -> explode(L());
explode([H|T]) -> [H|explode(T)].

加總函數也是一種消費函數,所以格式照抄:

sum([]) -> 0;
sum(L) when is_function(L) -> sum(L());
sum([H|T]) -> H + sum(T).

所以解題函數可以寫出來了。

solution_problem2() ->
    R = even_fib_l(0, 4000000),
    io:format("Sum of ~w is ~w.~n", [explode(R), sum(R)]).

除了我的作法,在 Haskell 學者社群中會講一種稱為 Banana Split 的解決方法,對產生的數列只走訪一次,每一項都用較大的結構同時處理費氏數字和偶數的計算。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Arena, Erlang。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s