【Project Euler】フィボナッチ数の和を求めよ【プログラミング】
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【Project Euler】フィボナッチ数の和を求めよ【プログラミング】

2018-03-09 19:00

    Problem2: Even Fibonacci Numbers
    -----------------------------------------------------------------------------------------------


     魔理沙~、次の問題の時間だよ~


     はいはい、えっと今日は何かな?

    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.


     また英語だ~…


     はいはい、また日本語にしておいたよ 笑

    フィボナッチ数列は、直前の二つの項を足すことで各項を求めることができる。例えば最初の項が1,2だとすると、最初の10個の項は以下のようになる

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

    では、400万まで求めた時の偶数だけを足したときの和は?


     ちょっと意訳ぽいけど、こんな感じかな

     フィボナッチ数列か、時々聞く話だよね
     ただこれ、地道に400万まで計算して、各項が偶数かどうか判別しないと
     いけないのかな…?

     ふふふふふ


     なんだその不敵な笑みは…?


     実は簡単な方法があります!


     まじかよ、どんな方法使えばいいん!?


     じゃあまず、さっきの数列の最初に1を加えてみよっか

     1を加える…?
     えっとそしたら、

     1,1,2,3,5,8,13,…
     ってなるのか、これでどうすればいいのさ


     各項は偶数と奇数、どうなってるかな?

     えっと、最初から
     奇数、奇数、偶数、奇数、奇数、偶数、奇数


     ってあれ?3の倍数の項が偶数になってる!

     そう、それがフィボナッチ数列の性質の一つなんだ!
     だからこの性質を利用すれば、奇数か偶数か判別する必要はなくなるよ


     よし、じゃあ早速コードを書いてみたよ!

    #include <iostream>

    int main(void) {
     /* 初期値を設定する */
     int oldval1, oldval2,
       val1=1, val2=1, result=0;
     
     while (val1+val2 < 4e6) {
      /* フィボナッチ数をresultに足す */
      result += val1 + val2;

      /* フィボナッチ数を計算する */
      oldval1 = val1;
      oldval2 = val2;
      val1 = oldval1 + 2 * oldval2, val2 = 2 * oldval1 + 3 * oldval2;
     }
     
     return 0;
    }


     我ながらいい出来だな~

     はいはい 笑
     じゃあ私もこんな感じで

    # ヘッダーを読み込む
    import numpy as np

    # 初期値を設定する
    val1, val2 = 1, 1
    result = 0

    while val1+val2 < 4e6:
     # フィボナッチ数をresultに足す
     result += val1 + val2 
     
     # フィボナッチ数を計算する
     val1, val2 = val1 + 2 * val2, 2 * val1 + 3 * val2

     やっぱPythonは少し遅いけど、コードは綺麗だなあ
     じゃあまた次の問題頑張ろう!


     お~!
    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。