Problem 2

今日は Problem 2。フィボナッチ数列のうち4,000,000以下で偶数のみを合計せよ,という問題。

cf. http://projecteuler.net/index.php?section=problems&id=2

Haskell ではやってる人がいるので,OCaml でやってみた。

let fibs_under_n n =
let rec fibs a b x =
let c = a + b in
if c > x then [] else c :: fibs b c x
in
1 :: 2 :: fibs 1 2 n
let even n = if n mod 2 = 0 then true else false
let sum lis = List.fold_left (+) 0 lis
let euler002 n = sum (List.filter even (fibs_under_n n))
let () = print_int (euler002 4000000)

even とか sum とかありそうな関数なんだけど,マニュアル見ても見つからなかったから自分で定義した。

コンパイルして実行:

^o^ >ocamlc -o euler002.exe euler002.ml
^o^ >euler002
4613732

追記:

_さんに教えてもらった方法で。

# let fibs_under_n2 n =
let rec fibs a b x =
let c = 4 * b + a in
if c > x then [] else c :: fibs b c x
in
2 :: 8 :: fibs 2 8 n
;;
# fibs_under_n2 5000;;
- : int list = [2; 8; 34; 144; 610; 2584]

元の関数を使うと

# List.filter even (fibs_under_n 5000);;
- : int list = [2; 8; 34; 144; 610; 2584]

「Problem 2」への1件のフィードバック

  1. 偶数のフィボナッチ数は
    E(1)=2,E(2)=8,E(n+2)=4*E(n+1)+E(n)
    と書けるという手を使う方法もあります。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください