Clasa a IX-a · Șiruri de numere citite pe rândRead in English

Al n-lea termen al șirului lui Fibonacci în C++

În engleză: The n-th term of the Fibonacci sequence

O(n)C++1736 de linii2 exemple

Ideea

Ș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.

Descrierea în engleză

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.

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

Exemple

Exemplul 1

Intrare

10

Ieșire așteptată

55
Exemplul 2

Intrare

1

Ieșire așteptată

1

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

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;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.