Magicode logo
Magicode
0
2 min read

【フィボナッチ数】一緒に考えませんか? #Project Euler

https://cdn.apollon.ai/media/notebox/DSC_00281.jpg

問2

1 2で始まるフィボナッチ数列で400万より小さい偶数項の和
Project Euler ※解法の公開は問1~100のみ可

考え方

1 2で始まるフィボナッチ数列で400万より小さい偶数項の和

まずは中間構造を考える
必要な値をリストでもってsumをとることにする
solve :: Int
solve = sum [フィボナッチ数列の400万より小さい偶数項]

-- フィボナッチ数列を作り、40000000より小さい偶数のみのリストの和を出せばいい
solve = sum [ n | n <- takeWhile (<4000000) fibs , even n]

再帰的な定義でフィボナッチ数列の無限リストを作る

数列を一つずらして足したのが項になるという定義(もはや構文)
fibs :: Integer
fibs = 1 : 2 : zipWith (+) fibs (tail fibs) 
haskell
solve_p2 :: Integer
solve_p2 = sum [ n | n <- takeWhile (< 4000000) fibs, even n]
fibs :: [Integer]
fibs = 1 : 2 : zipWith (+) fibs (tail fibs)
print solve_p2

4613732

末筆ながら

ご意見求む!!

こいった再帰的なデータ定義は再帰的な計算(fib(n-1) + fib(n-2)みたいな)ことはしないで、単純に1個ずらした値との和だけで出来ている?
  • やけに早い気がする
偶数項だけを最初から作り出せるかも?

Haskellerさんへ

計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします!

スキル指標

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください
読んだ本
  • すごいH本
  • 関数プログラミング実践入門 (途中)
つまり構文を知った程度で、関数型言語っぽい書き方を学び中です

Discussion

コメントにはログインが必要です。