Grade 12 · Big numbersCitește în română

The n-th Fibonacci term (big number)

Original: Termenul n din șirul lui Fibonacci (număr mare)

O(n²)C++1765 lines3 examples

The idea

The sequence is F(1) = F(2) = 1 and F(i) = F(i - 1) + F(i - 2). The terms grow exponentially (F(93) no longer fits in long long), so we keep them as big numbers. We keep only the last two terms, a and b; at every step we compute c = a + b by addition with carry, then a becomes b and b becomes c. The term F(n) has about 0.21 * n digits.

Original description (Romanian)

Șirul este F(1) = F(2) = 1 și F(i) = F(i - 1) + F(i - 2). Termenii cresc exponențial (F(93) nu mai încape în long long), deci îi ținem ca numere mari. Păstrăm doar ultimii doi termeni, a și b; la fiecare pas calculăm c = a + b prin adunare cu transport, apoi a devine b și b devine c. Termenul F(n) are aproximativ 0,21 * n cifre.

Complexity
O(n * L), where L is the number of digits of F(n)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

100

Expected output

354224848179261915075
Example 2

Input

1

Expected output

1
Example 3

Input

10

Expected output

55

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

fibonacci-numar-mare.cpp
/*
 * Titlu: Termenul n din șirul lui Fibonacci (număr mare)
 * Clasa: 12
 * Capitol: Numere mari
 * Descriere: Șirul este F(1) = F(2) = 1 și F(i) = F(i - 1) + F(i - 2). Termenii
 *            cresc exponențial (F(93) nu mai încape în long long), deci îi ținem
 *            ca numere mari. Păstrăm doar ultimii doi termeni, a și b; la fiecare
 *            pas calculăm c = a + b prin adunare cu transport, apoi a devine b și
 *            b devine c. Termenul F(n) are aproximativ 0,21 * n cifre.
 * Complexitate: O(n * L), unde L este numărul de cifre al lui F(n)
 *
 * Exemplu
 * Intrare: 100
 * Ieșire: 354224848179261915075
 *
 * Exemplu
 * Intrare: 1
 * Ieșire: 1
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 55
 */
#include <iostream>
#include <vector>
using namespace std;

vector<int> aduna(const vector<int> &a, const vector<int> &b)
{
    vector<int> c;
    int transport = 0;
    int k = max(a.size(), b.size());
    for (int i = 0; i < k; i++)
    {
        int s = transport;
        if (i < (int)a.size())
            s += a[i];
        if (i < (int)b.size())
            s += b[i];
        c.push_back(s % 10);
        transport = s / 10;
    }
    if (transport > 0)
        c.push_back(transport);
    return c;
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(1, 1), b(1, 1); // F(1) și F(2)
    for (int i = 3; i <= n; i++)
    {
        vector<int> c = aduna(a, b);
        a = b;
        b = c;
    }
    // Pentru n = 1 sau n = 2 rezultatul este b = 1.
    for (int i = (int)b.size() - 1; i >= 0; i--)
        cout << b[i];
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.