Project Eulerの2問目をやっていきます

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

 

項の値が4,000,000以下の, 偶数値の項の総和を求めよ

出典;Problem 2 - Project Euler

フィボナッチ数列ってなんだっけ?

昔、ミステリー小説によく出ていて、フィボナッチ数列を解くことが犯人への手がかりみたいなのが多かったですが、最近は使い古されたためか廃れてきましたね.

さてさて、フィボナッチ数って何?って話の途中でした.Wikipediaの解説を見たほうが早いかもしれませんが、簡単に言うとこんな数列です.

これの偶数値を足していくわけです.

\[{\begin{cases} ~~~F_0=0\\ ~~~F_1=1\\ ~~~F_{n+1}=F_n+F_{n+1} (n\ge 0)\end{cases} }\]

 

 

実際に書いてみる

例によってVisual studioのC++を使います.

 

基本的な指針としては

  1. 無限ループを回す
  2. フィボナッチ数列を計算する
  3. n項目の値が偶数かを判定する
  4. 400万を超えたらbreakする

ということです。ただし、毎回フィボナッチ数を呼び出して計算するのも非効率な気がしてきたので、こんなふうに書き換えました。

スマートなコードではない気がしますが、まぁパッと思いつくのはこんなもんかと。

 

 

コメント