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
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
Intrare
10
Ieșire așteptată
55
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.
/*
* 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.