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

Șirul lui Fibonacci în C++

Ce este șirul lui Fibonacci?

Șirul Fibonacci este un șir de numere descoperit de matematicianul Leonardo Pisano, unde fiecare element se generează pe baza ultimelor două numere. Astfel:

  • Primele două numere ale șirului sunt egale cu 1: f1 = 1, f2 = 1;
  • Pentru celelalte numere: fn = fn - 1 + fn - 2 (n ≥ 3).

Unele persoane consideră și elementul 0 ca fiind elementul f0 al șirului.

Astfel, primele 20 de numere ale șirului sunt 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, …, care verifică condiția fn = fn-1 + fn-2:

Imagine Șirul lui Fibonacci

Șirul lui Fibonacci în C++

Pentru a implementa șirul Fibonacci în C++, ne vom folosi de trei variabile, a, b și c, cu următorul algoritm:

  • La început, a și b sunt egale cu 1 (primele două elemente Fibonacci);
  • La fiecare pas, c primește a + b (devenind astfel noul termen Fibonacci generat), iar a devine b și b devine c (ca să generăm următorul element, care ar fi fost egal cu b + c)

Atenție: doar primii 45 de termeni ai șirului încap în tipul de date int!

Următorul cod C++ afișează pe ecran primele n elemente ale șirului lui Fibonacci (n ≥ 2):

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n; //Numărul de elemente de afișat

    int a = 1, b = 1, c;
    cout << a << " " << b << " "; //Afișăm primii 2 termeni
    for(int i = 3; i <= n; i++) { //Afișăm restul de termeni, de la 3 la n
        c = a + b; //Conform algoritmului descris mai sus
        a = b;
        b = c;

        cout << c << " "; //Afișăm noul element generat
    }
    return 0;
}

Exerciții propuse

Să se completeze următoarele secvențe de cod:

Să se afișeze termenii Fibonacci mai mici sau egali cu un număr x:

int a = 1, b = 1, c, x;
cin >> x;
cout << a << " " << ??? << " ";
while(a + b <= ???) {
    c = a + b;
    a = b;
    b = c;
    cout << c << " ";
}

Să se inițializeze variabilele a, b, c pentru a afișa primii 60 de termeni Fibonacci:

??? a = 1, b = 1, c;
cout << a << " " << b << " ";
for(int i = 3; i <= 60; i++) {
    c = a + b;
    a = b;
    b = c;

    cout << c << " ";
}

Probleme propuse

# Problemă Dificultate
28. Fibonacci Ușoară (2 )
207. Toti sunt termeni Fibonacci Medie (4 )
31. Verificare Fibonacci Medie (4 )
29. Fibonacci 2 Ușoară (2 )
30. Fibonacci generalizat Ușoară (2 )

Alte resurse sau 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

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