Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Al N-lea termen Fibonacci în C++

Dându-se un număr natural n, să se determine al n-lea termen din șirul Fibonacci.

Exemplu. Pentru n = 9, F(n) = F(9) = 34.

Ce este șirul Fibonacci?

Șirul Fibonacci, cunoscut după matematicianul Leonardo Bonacci, este șirul definit astfel:

  • primii doi termeni ai șirului, F(1) și F(2), sunt egali cu 1.
  • următorii termeni ai șirului sunt definiți după relația F(n) = F(n - 1) + F(n - 2).

Curiozități despre șirul Fibonacci

  • Primii termeni ai șirului sunt 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
  • Doar primii 46 de termeni încap în int — așadar de regulă se lucrează cu variabile de tip long long.

Cum se determină al n-lea termen Fibonacci (cu vector)

Vom crea un vector în care al i-lea element reprezintă al i-lea termen Fibonacci. Vom genera acest vector până la n.

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim variabilele
    int n, fibo[51];
    cin >> n;

    //Generăm șirul
    fibo[1] = fibo[2] = 1;
    for(int i = 3; i <= n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }

    //Afișăm al n-lea termen
    cout << fibo[n];
    return 0;
}

Cum se determină al n-lea termen Fibonacci (recursiv)

Soluția recursivă este foarte ineficientă, deoarece se recalculează aceeași termeni de multe ori. Cu toate acestea, este un exemplu bun de a demonstra recursivitatea:

#include <iostream>

using namespace std;

int fibo(int n) {
    if(n == 1 || n == 2) { //Cazuri particulare
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

int main()
{
    //Declarăm și citim
    int n;
    cin >> n;

    //Afișăm al n-lea termen
    cout << fibo(n);
    return 0;
}

De ce nu este eficientă această soluție?

Să analizăm grafic ce se întâmplă dacă apelăm fibo(5):

https://i.ibb.co/GsyPtJW/image.png

Observăm că în timpul calculării lui fibo(5), apelăm fibo(4) și fibo(3). Când apelăm fibo(4), apelăm din nou fibo(3), pe care l-am calculat deja. Acesta este un exemplu simplu în care se observă faptul că se repetă calcularea anumitor termeni, dar pentru calcularea fibo(30), de exemplu, poate lua până la un minut — operație ce, în fond, doar face 30 de sume.

Alte resurse și bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicMaximul și minimul unui vector în C++Suma divizorilor unui număr în C++Vectori de frecvență (de apariții) în C++Suma numerelor naturale dintr-un interval dat în C++Comentarii în C++Cel mai semnificativ bit în C++Verifică dacă un număr aparține șirului Fibonacci în C++Cel mai mic număr cu suma cifrelor N în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Numărul permutărilor în C++ (formula permutărilor)Instrucțiunea while (structuri repetitive)Aflarea sumei primelor N sume GaussTransformarea unei litere mari în literă mică în C++Aria unui triunghi folosind coordonatele acestora în C++Valoarea absolută (modulul) unui număr în C++Cifra de control a unui numărCifra maximă și minimă a unui număr în C++Cel mai puțin semnificativ bit în C++Verificare dacă șir de caractere este palindrom în C++Ce înseamnă endl în C++?Prima cifră a unui număr în C++Tipul struct în C++. Ce sunt structurile de date neomogeneStructuri repetitive (while, do while, for, etc)Instrucțiunea continue (structuri repetitive)Verificare dacă un număr este palindrom în C++Ce înseamnă variabilă globală și locală în C++?Cel mai frecvent element dintr-un șir în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Verifică dacă trei puncte sunt coliniare C++Numărul de divizori al unui număr în C++Copiuțe: Cifrele unui numărCăutare binară în C++Ce este o funcție void în C++?Câte numere naturale sunt într-un interval dat? (C++)Ciurul lui Eratostene în C++Pointer în C++. Variabile de tipul char * (char steluță)Oglinditul recursiv al unui număr în C++Codul ASCII (tabel complet)Transformarea unui număr din baza 2 în baza 10 în C++Verifică dacă o literă este mică sau mare în C++Maximul și minimul a trei valori în C++Cifra maximă a unui număr recursiv în C++Generarea șirului Fibonacci generalizat în C++Al N-lea termen Fibonacci în C++Distanța dintre două puncte în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Cum să afișezi partea întreagă a unui număr real în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiRadicalul unui număr în C++ (rădăcina pătrată)Indicatorul lui Euler în C++Șiruri de caractere în C++. Tot ce trebuie să știiCombinatorică în C++: permutări, aranjamente, combinări și alteleVerifică dacă o literă este vocală în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Numărul de divizori primi ai unui număr în C++Transformarea unei litere mici în literă mare în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortAplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorTipuri de date în C++: numere întregi, reale, caractere și alteleNumărul combinărilor în C++ (formula combinărilor)Cum să citești și să afișezi în fișiere în C++Numărul de cifre ale factorialului unui numărTransformarea unui număr din baza 10 în baza 2 în C++Recursivitate în C++Inversarea unui șir de caractere în C++Verifică dacă un caracter este literă în C++Instrucțiunea for (structuri repetitive)Vectorii în C++: citire și afișareNumărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă un număr dat este o putere de 2 în C++Mediana unui șir de valori în C++Al N-lea termen dintr-o progresie geometricăRidicarea la putere în timp logaritmic în C++. Exponențiere rapidăAlgoritm recursiv pentru căutare binară (clasa a X-a)Cifrele unui număr. Prelucrarea cifrelor unui număr în C++CMMDC recursiv a două numere naturale în C++Suma 1 + 2 + 3 + ... + N în C++Calculul combinărilor de n luate câte k (nCk) în C++Maximul și minimul a două valori în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Matrice pătratice în C++. Diagonala principală și secundarăVerifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Instrucțiunea de decizie în C++: if, else, switch, caseCitirea și afișarea matricelor în C++Interschimbarea a două variabile în C++ (3 metode)Aria și circumferința unui cerc în C++Afișarea elementelor unui vector recursiv în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Complexitatea unui algoritm (timp și spațiu) în C++Suma elementelor unui vector recursiv în C++Interclasarea a doi vectori în C++Bordarea unei matrice în C++Verificarea unui an bisect în C++Factorialul unui număr în C++Maximul și minimul a n valori în C++Verifică dacă un număr este par sau impar fără modulo în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleInversarea unui vector în C++Rădăcina cubică a unui număr în C++ (cube root)Oglinditul unui număr în C++Vectorii în C++: declarare și parcurgereAflă secolul unui an citit de la tastatură în C++Cea mai lungă secvență de elemente crescătoare în C++Verificare număr prim în C++ (Clasa a IX-a)Numărul aranjamentelor în C++ (formula aranjamentelor)De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Afișarea divizorilor primi ai unui număr în C++Citește un șir de caractere cu spații în C++Numărul minim de peroane pentru o gară în C++Operații cu numere mari în C++ - Toate funcțiile explicateNumărul de apariții al unui număr într-un vector în C++Șirul lui Fibonacci în C++Ce este o variabilă unsigned în C++?Verifică dacă un caracter este cifră în C++Do while vs while în C++ - Care e diferența?Cum să calculezi instant 2 la puterea N în C++Funcții în C++. Ce sunt subprogrameleDivide et Impera (metodă de programare C++)Instrucțiunea do while (structuri repetitive)Instrucțiunea break (structuri repetitive)Numere triunghiulare. Verificarea unui număr triunghiularAl N-lea termen dintr-o progresie aritmetică

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont