ヒマワリの種を眺めてフィボナッチ。

息抜きに、コマンドライン引数に正の整数 n を与えると、n 番目のフィボナッチ数を表示するプログラムを書いてみます。

$ ./fib 0
0
$ ./fib 1
1
$ ./fib 2
1
$ ./fib 3
2
$ ./fib 4
3
$ ./fib 5
5
$ ./fib 6
8
$ ./fib 7
13
$ ./fib 8
21
$ ./fib 9
34
$ ./fib 10
55
$ ./fib 100
354224848179261915075
$ ./fib 365
8531073606282249384383143963212896619394786170594625964346924608389878465365

フィボナッチ数の計算方法に様々ある中で、 今回は一回計算して表示して終わりということで、 小さな方から順番に求めていき、一つ前と二つ前を覚えておくことにします。 n0 が 2 つ前、 n1 が 1 つ前、 m が次の数です。 m を求めてから、 n0 の内容を捨てて n1 から移し、m を n1 に移していきます。桁数を気にしないで済ますため、符号なし整数は 10 進数の数字列の文字列で表すことにします。

#include <string>
#include <utility>
#include <iostream>

class fibonacci_number {
public:
    fibonacci_number () {}
    std::string operator () (int n);
    std::string plus (std::string const& m0, std::string const& m1);
};

std::string
fibonacci_number::operator () (int n)
{
    if (0 == n)
        return "0";
    if (1 == n)
        return "1";
    std::string n0 = "0";
    std::string n1 = "1";
    for (int i = 1; i < n; ++i) {
        std::string m = plus (n0, n1);
        std::swap (n0, n1);
        std::swap (n1, m);
    }
    return n1;
}

int
main (int argc, char* argv[])
{
    int n = 100;
    if (argc >= 2) {
        n = std::stoi (argv[1]);
        if (n < 0) {
            std::cerr << "usage: " << argv[0] << " [n]" << std::endl;
            exit (EXIT_FAILURE);
        }
    }
    fibonacci_number fib;
    std::cout << fib (n) << std::endl;
    return EXIT_SUCCESS;
}

10 進数文字列同士の符号なし加算は、 計算さえできれば良い速度不問のプログラムなので、 10 進一桁ごとに桁上がりを考慮しつつ計算していきます。 下の桁から上の桁へ向けて一桁ずつ足し算をしていきます。各桁に入っているのは数字なので、整数にしてから足して、数字にして書き込みます。最後に桁上がりがゼロでないときは、桁を追加します。

std::string
fibonacci_number::plus (std::string const& m0, std::string const& m1)
{
    if (m0.size () > m1.size ())
        return plus (m1, m0);
    std::string m (m1.size (), '0');
    int carry = 0;
    std::size_t j = m1.size ();
    for (std::size_t i = m0.size (); i > 0; --i, --j) {
        int const x = (m0[i - 1] - '0') + (m1[j - 1] - '0') + carry;
        if (x >= 10) {
            carry = 1;
            m[j - 1] = x - 10 + '0';
        }
        else {
            carry = 0;
            m[j - 1] = x + '0';
        }
    }
    for (; j > 0; --j) {
        int const x = (m1[j - 1] - '0') + carry;
        if (x >= 10) {
            carry = 1;
            m[j - 1] = x - 10 + '0';
        }
        else {
            carry = 0;
            m[j - 1] = x + '0';
        }
    }
    if (carry > 0)
        m.insert (0, 1, carry + '0');
    return std::move (m);
}