Grade 9 · Number sequences read one at a timeCitește în română

The n-th term of the Fibonacci sequence

Original: Al n-lea termen al șirului lui Fibonacci

O(n)C++1736 lines2 examples

The idea

The Fibonacci sequence starts with 1, 1 and every term is the sum of the two before it: 1, 1, 2, 3, 5, 8, ... We do not need an array: we keep only the last two terms (a and b) and 'shift' them at every step. With long long it works up to n = 92.

Original description (Romanian)

Șirul lui Fibonacci începe cu 1, 1 și fiecare termen este suma celor doi dinaintea lui: 1, 1, 2, 3, 5, 8, ... Nu avem nevoie de vector: păstrăm doar ultimii doi termeni (a și b) și îi „mutăm” la fiecare pas. Cu long long merge până la n = 92.

Complexity
O(n)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

10

Expected output

55
Example 2

Input

1

Expected output

1

The code

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

fibonacci-al-n-lea-termen.cpp
/*
 * Titlu: Al n-lea termen al șirului lui Fibonacci
 * Clasa: 9
 * Capitol: Șiruri de numere citite pe rând
 * Descriere: Șirul lui Fibonacci începe cu 1, 1 și fiecare termen este suma
 *            celor doi dinaintea lui: 1, 1, 2, 3, 5, 8, ... Nu avem nevoie de
 *            vector: păstrăm doar ultimii doi termeni (a și b) și îi „mutăm” la
 *            fiecare pas. Cu long long merge până la n = 92.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 55
 *
 * Exemplu
 * Intrare: 1
 * Ieșire: 1
 */
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long a = 1, b = 1;
    cin >> n;
    for (int i = 3; i <= n; i++)
    {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << '\n';
    return 0;
}

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