Generarea șirurilor și Fibonacci în C++

Un șir de numere este o succesiune ale cărei poziții au o ordine. Uneori poți calcula direct termenul de pe o poziție; alteori termenul nou se obține din termenii anteriori. În ambele cazuri trebuie să precizezi valorile de început și câți termeni dorești.

Lecția folosește variabile și bucle. Vei genera un șir cu diferență constantă și primii termeni Fibonacci, folosind doar câteva variabile.

Șir cu diferență constantă

Pornim de la valoarea a, iar pentru fiecare termen următor adunăm pas. Citim n, a, pas, cu 0 <= n <= 100, iar a și pas între -1000000 și 1000000.

#include <iostream>

int main() {
    int n = 0;
    long long a = 0, pas = 0;
    std::cin >> n >> a >> pas;
    long long termen = a;
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            std::cout << ' ';
        }
        std::cout << termen;
        termen += pas;
    }
    std::cout << '\n';
    return 0;
}

Pentru intrarea 5 3 4, programul afișează:

3 7 11 15 19

Afișăm termenul curent înainte să îl modificăm. Dacă ai aduna pasul înaintea afișării, primul termen ar deveni 7, iar șirul ar fi deplasat cu o poziție.

Condiția i > 0 adaugă un spațiu înaintea tuturor termenilor în afară de primul. Astfel obții exact separatorii dintre valori. Pentru n = 0, nu se afișează niciun termen, doar linia nouă finală.

Pasul poate fi negativ sau zero. Pentru 4 10 -3, obții 10 7 4 1. Pentru 3 5 0, obții 5 5 5. Nu presupune că orice șir trebuie să fie crescător.

Calculul direct al unui termen

Dacă pozițiile sunt numerotate de la zero, termenul de pe poziția k este a + k * pas. Pentru șirul anterior, poziția 0 conține 3, iar poziția 4 conține 19.

Dacă problema numerotează pozițiile de la unu, formula devine a + (k - 1) * pas. Notează convenția înainte să scrii programul. Multe rezultate greșite provin din folosirea unei formule corecte pentru altă numerotare.

Șirul Fibonacci

Folosim convenția F0 = 0, F1 = 1, iar fiecare termen următor este suma celor doi anteriori. Primele valori sunt 0, 1, 1, 2, 3, 5, 8.

#include <iostream>

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

Presupunem 0 <= n <= 90. În aceste limite, și termenii intermediari calculați de program încap în long long. Nu extinde limita fără să verifici creșterea valorilor: termenii Fibonacci cresc repede.

La început, perechea este (0, 1). După afișarea lui 0, calculăm urmator = 1 și perechea devine (1, 1). După următorul pas devine (1, 2), apoi (2, 3). Variabila auxiliară păstrează suma înainte de modificarea operanzilor.

Dacă scrii mai întâi a = b și apoi calculezi b = a + b, folosești deja noua valoare a lui a. Nu mai construiești șirul dorit. Ordinea atribuirilor este parte din algoritm.

Cost și verificare

Pentru afișarea a n termeni, ambele programe execută n pași, deci au timp O(n). Păstrează un număr fix de variabile, deci folosesc memorie suplimentară O(1), fără a număra ieșirea afișată.

Testează n = 0, 1, 2, un pas negativ și un pas nul pentru primul program. La Fibonacci, verifică explicit începutul șirului; două convenții diferite pot produce secvențe deplasate, ambele întâlnite în enunțuri.

Primii patru pași ai programului Fibonacci, cu a și b urmărite separat.

Exersează

1. Ce afișează primul program pentru 4 2 5?
2. Care este termenul de pe poziția 3, numerotată de la zero, dacă a = 10 și pas = -2?
3. Ce afișează al doilea program pentru n = 6?
4. De ce este necesară variabila urmator în ordinea de atribuire folosită?

Răspunsuri: 2 7 12 17; valoarea 4; 0 1 1 2 3 5; salvează suma celor două valori vechi înainte ca ele să fie înlocuite.

Încheie capitolul introductiv cu bazele de numerație.

Întrebări frecvente

Cum se generează șirul Fibonacci?

După stabilirea primilor doi termeni, fiecare termen este suma celor doi precedenți. Convenția de indexare trebuie precizată înainte de calcul.

Trebuie să păstrez toți termenii?

Pentru calcularea unui singur termen Fibonacci, două valori precedente sunt suficiente. Pentru întrebări despre întregul șir poate fi necesară memorarea lor.

De ce contează ordinea actualizărilor?

Dacă suprascrii primul termen înainte de calculul celui nou, poți pierde o valoare necesară. Calculează întâi următorul termen într-o variabilă temporară.

Termenii Fibonacci încap mereu în long long?

Nu. Șirul crește rapid și depășește orice tip întreg fix. Limitează indicele sau folosește aritmetică modulară ori numere mari conform cerinței.

Cum verific o recurență implementată?

Scrie manual primii termeni și compară-i cu programul. Testează separat valorile inițiale, prima aplicare a formulei și cea mai mare intrare admisă.