[C++] Project Euler Problem 2

2021 8/21

2021年8月7日 2021年8月21日

Project Eulerの問題をC++で解く．

問題

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.
https://projecteuler.net/problem=2

英語わからない．和訳くれ

和訳

フィボナッチ数列の項は前の2つの項の和である．最初の2項を1，2とすれば，最初の10項は以下の通りである．

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

数列の項の値が400万以下のとき，値が偶数の項の総和を求めよ．

解答

[su_spoiler title=”解答を表示” style=”fancy” icon=”plus-square-1″ class=”my-custom-spoiler”]

4613732

[/su_spoiler]

プログラム

考え方

フィボナッチ数列の各項を順に求めながら，偶数を加算する．

ソースコード

[su_spoiler title=”ソースコード” style=”fancy” icon=”plus-square-1″ class=”my-custom-spoiler”]

#include <iostream>

int main(void)
{
    unsigned long term1 = 1;
    unsigned long term2 = 2;
    unsigned long term = 0;
    unsigned long answer = term2; // 第2項は偶数なので予め足しておく

    // 3項目以降の計算
    while (true)
    {
        term = term1 + term2;
        if (term > 4000000) break;
        if (term % 2 == 0) answer += term;
        term1 = term2;
        term2 = term;
    }

    std::cout << "Answer is " << answer << std::endl;

    return 0;
}

[/su_spoiler]

ソースコード（アルゴリズム）説明

unsigned long answer = term2; // 第2項は偶数なので予め足しておく

第1項は奇数項，第2項は偶数項なので，第2項のみ足しておく．

実行

$ g++ -o problem2 main.cpp
$ ./problem2

Answer is 4613732

プログラム（別解）

再利用性を考えると，「n個のフィボナッチ数列を求める関数」を作成したほうが良い．

その関数を用いた解答例を示す．

考え方

「n個のフィボナッチ数列を求める関数」を利用するために，問題の400万以下のフィボナッチ数列がいくつ存在するか知る必要がある．

400万以上となる項が第何項かを求めたのち，n個のフィボナッチ数列を求める．
求められた数列から，題意を満たす解答を求める．

フィボナッチ数列の一般項（第ｎ項のフィボナッチ数）は次式である．

$$F_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right) ^n – \left( \frac{1-\sqrt{5}}{2} \right) ^n \right\}$$

ソースコード

#include <iostream>
#include <vector>
#include <cmath>

namespace
{
    std::vector<unsigned long> CreateFibonacciSequence(const unsigned long &num_request_terms)
    {
        const unsigned long first_value  = 1;
        const unsigned long second_value = 1;
        std::vector<unsigned long> fibonacci_sequence;
        fibonacci_sequence.push_back(first_value);
        fibonacci_sequence.push_back(second_value);
        for (unsigned long i_term = 2; i_term < num_request_terms; i_term++)
        {
            fibonacci_sequence.push_back(fibonacci_sequence[i_term - 2]
                                         + fibonacci_sequence[i_term - 1]);
        }
        return fibonacci_sequence;
    }

    unsigned long CreateNthTermOfFibonacciSequence(const unsigned long &num_request_terms)
    {
        const double sqrt5 = std::sqrt(5.0e0);
        const double n     = static_cast<double>(num_request_terms);
        const double value =
            (std::pow((1.0e0 + sqrt5) * 0.5e0, n) - std::pow((1.0e0 - sqrt5) * 0.5e0, n)) / sqrt5;
        return static_cast<unsigned long>(std::lround(value));
    }

}

int main (void)
{
    constexpr unsigned long maximum_value = 4000000;
    unsigned long maximum_term            = 0;
    // find maximum term
    while (true)
    {
        if (CreateNthTermOfFibonacciSequence(maximum_term + 1) > maximum_value)
            break;
        maximum_term++;
    }

    std::vector<unsigned long> fibonacci_sequence;
    {  // the first term should be stashed.
        fibonacci_sequence = CreateFibonacciSequence(maximum_term);
        fibonacci_sequence.erase(fibonacci_sequence.begin());
    }

    unsigned long answer = 0;
    {
        for (const auto &term : fibonacci_sequence)
        {
            if (term % 2 == 0)
            {
                answer += term;
            }
        }  // for term
    }
    std::cout << "Answer is " << answer << std::endl;
    return 0;
}

ソースコード（アルゴリズム）説明

n個のフィボナッチ数列を求める関数

一般的なフィボナッチ数列は

$$ 1, 1, 2, 3, 5, …$$

である．

一般的なフィボナッチ数列を求める関数は，以下である．

std::vector<unsigned long> CreateFibonacciSequence(const unsigned long &num_request_terms)
{
    const unsigned long first_value  = 1;
    const unsigned long second_value = 1;
    std::vector<unsigned long> fibonacci_sequence;
    fibonacci_sequence.push_back(first_value);
    fibonacci_sequence.push_back(second_value);
    for (unsigned long i_term = 2; i_term < num_request_terms; i_term++)
    {
        fibonacci_sequence.push_back(fibonacci_sequence[i_term - 2]
                                     + fibonacci_sequence[i_term - 1]);
    }
    return fibonacci_sequence;
}

問題のフィボナッチ数列は，第1，２項はそれぞれ1, 2であると定義しているため，CreateFibonacciSequenceから得られた一般的なフィボナッチ数の第１項を削除している．

std::vector<unsigned long> fibonacci_sequence;
{  // the first term should be stashed.
    fibonacci_sequence = CreateFibonacciSequence(maximum_term);
    fibonacci_sequence.erase(fibonacci_sequence.begin());
}

フィボナッチ数列の第n項の値を求める関数

第n項フィボナッチ数を求める関数は，以下のようである．

unsigned long CreateNthTermOfFibonacciSequence(const unsigned long &num_request_terms)
{
    const double sqrt5 = std::sqrt(5.0e0);
    const double n     = static_cast<double>(num_request_terms);
    double value =
        (std::pow((1.0e0 + sqrt5) * 0.5e0, n) - std::pow((1.0e0 - sqrt5) * 0.5e0, n)) / sqrt5;
    return static_cast<unsigned long>(std::lround(value));
}