Fibonacci iterativ la BAC: C++, indici și limite

Calculul iterativ al unui termen Fibonacci folosește doar ultimii doi termeni, nu întregul șir. La fiecare pas calculezi suma, apoi deplasezi perechea. Într-o problemă de BAC, partea importantă este să legi variabilele de indici, să tratezi valorile inițiale și să alegi un tip numeric suficient pentru limita cerută.

Această lecție urmărește implementarea și verificarea algoritmului. Folosim convenția în care termenul de indice zero este zero, termenul de indice unu este unu, iar fiecare termen următor este suma celor doi precedenți. Convenția trebuie citită atent și în subiectele de BAC, deoarece o numerotare diferită poate deplasa răspunsul.

Ce trebuie să păstrezi între două etape

Pentru a calcula termenul de indice șase, ai nevoie de termenii de indici patru și cinci. Nu ai nevoie direct de termenul de indice trei, dacă valorile următoare au fost deja calculate. Această dependență locală permite folosirea a două variabile de stare.

Vom numi prima variabilă termenul mai vechi, iar a doua termenul mai nou. Înainte de calcularea termenului curent, ele trebuie să reprezinte exact cei doi predecesori ai lui. O variabilă temporară păstrează suma până când ambele variabile de stare pot fi actualizate corect.

Indice calculat	Termen mai vechi	Termen mai nou	Suma nouă
2	0	1	1
3	1	1	2
4	1	2	3
5	2	3	5
6	3	5	8

Tabelul descrie valorile înaintea fiecărei actualizări. După ultima linie, perechea păstrată devine cinci și opt. Dacă enunțul cere termenul de indice șase, afișezi valoarea mai nouă, adică opt.

De ce ordinea atribuirilor contează

O implementare greșită înlocuiește mai întâi termenul vechi cu cel nou, apoi adună cele două variabile. În acel moment, ambele pot conține aceeași valoare, deci suma nu mai folosește cei doi termeni inițiali.

Pentru perechea trei și cinci, suma corectă este opt. Dacă scrii întâi că prima variabilă devine cinci, apoi aduni prima și a doua variabilă, obții zece. Programul poate produce primele valori aparent plauzibile și apoi să se îndepărteze de șirul cerut.

Soluția clară folosește un temporar: calculezi suma, muți termenul mai nou în locul celui vechi și pui suma în locul termenului mai nou. Explică această succesiune în cuvinte înainte să o scrii în cod. Este un exemplu concret pentru diferența dintre memorare și înțelegere.

Program C++ pentru un indice dat

Programul următor acceptă un indice natural între zero și 92. Folosește tipul întreg semnat long long, care poate reprezenta toate valorile necesare în acest interval pe implementările conforme cu minimul de 64 de biți al acestui tip.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0;
        return 0;
    }
    long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b;
    return 0;
}

Cazul zero este tratat înaintea buclei. Pentru indicele unu, bucla nu se execută, iar valoarea afișată este cea inițială a celei de-a doua variabile. Pentru indicele doi, bucla se execută o singură dată. Aceste trei teste verifică imediat limitele parcurgerii.

Pentru indicele 92, rezultatul este 7540113804746346429. Termenul următor depășește valoarea maximă a unui întreg semnat pe 64 de biți. De aceea, limita nu este un detaliu decorativ: același cod nu trebuie prezentat ca soluție pentru orice indice natural.

Justificarea prin semnificația variabilelor

La începutul unui pas cu indicele curent, prima variabilă reprezintă termenul cu două poziții înainte, iar a doua reprezintă termenul imediat precedent. Suma lor este termenul curent, conform definiției șirului.

După actualizare, perechea conține termenul precedent și termenul curent. Aceștia sunt exact cei doi predecesori necesari la pasul următor. Prin urmare, semnificația variabilelor se păstrează pe durata întregii parcurgeri.

Această propoziție este invariantul buclei. Ea justifică algoritmul pentru toate intrările din domeniu, în timp ce câteva exemple îl verifică doar pe cazurile alese. La explicarea unei soluții, combină cele două: o regulă generală și un tabel scurt pentru a face actualizările vizibile.

Timp și memorie

Pentru un indice mai mare decât unu, bucla execută un număr de pași egal cu indicele minus unu. Fiecare pas folosește un număr constant de operații pe valori care încap în tipul ales. În acest model, timpul este liniar în indice.

Memoria suplimentară este constantă. Variabilele nu se înmulțesc odată cu indicele, iar programul nu reține un vector cu toți termenii. Dacă cerința solicită afișarea întregii secvențe, poți afișa fiecare termen pe măsură ce îl construiești, păstrând aceeași memorie constantă.

Dacă trebuie să răspunzi multor întrebări despre termeni diferiți, situația se schimbă. Păstrarea valorilor într-un tablou poate evita recalculările. Alegerea structurii depinde de cerință, nu de regula că un vector ar fi întotdeauna bun sau întotdeauna inutil.

De ce recursia directă repetă calcule

O funcție care calculează un termen apelând separat cei doi termeni precedenți urmează fidel definiția matematică, dar poate repeta aceleași calcule. Pentru un termen de indice cinci, ramurile pentru indicii patru și trei solicită din nou valori comune.

Fără memorarea rezultatelor, numărul apelurilor crește rapid, de ordin exponențial. Varianta iterativă calculează fiecare termen necesar o singură dată. Nu deduce eficiența numai din numărul liniilor de cod: o funcție scurtă poate declanșa foarte multe apeluri.

Recursia cu memorare poate elimina repetările, însă introduce o structură pentru rezultate. Pentru calcularea unui singur termen în domeniul de mai sus, bucla cu două variabile este o soluție directă și ușor de justificat.

Când cerința oferă un prag, nu un indice

Dacă trebuie să găsești primul termen mai mare decât un prag, condiția de oprire privește valoarea termenului, nu numărul de pași. Nu transforma automat pragul în limita indicelui. Un prag de o sută nu înseamnă că trebuie să calculezi termenul de indice o sută.

Pentru pragul o sută, valorile relevante din final sunt 55, 89 și 144. Primul termen strict mai mare decât pragul este 144. Dacă enunțul cere cel mai mare termen cel mult egal cu pragul, răspunsul este 89. Diferența dintre cele două cerințe privește ce valoare păstrezi și afișezi după depășire.

Și aici trebuie să protejezi adunarea față de depășirea tipului numeric, folosind limitele enunțului. O condiție de buclă corectă nu repară o sumă care nu mai încape în variabila destinată rezultatului.

Exerciții de control

Ce se afișează pentru indicele șapte? Rezultatul este treisprezece. Perechea dinaintea ultimei actualizări este cinci și opt, iar perechea de după este opt și treisprezece.

De câte ori rulează bucla pentru indicele patru? De trei ori, pentru indicii doi, trei și patru. Dacă ai numărat patru execuții, verifică de unde începe contorul.

Este suficient tipul întreg semnat pe 32 de biți pentru indicele 47? Nu. Termenul este 2971215073, mai mare decât maximul acelui tip. Alegerea long long este necesară pentru domeniul programului nostru.

Ce se schimbă dacă primele două valori sunt doi și trei? Regula de actualizare poate rămâne aceeași, dar obții un alt șir. Trebuie modificate valorile inițiale și tratamentul indicelui zero, nu doar mesajul explicativ.

Întrebări frecvente

Pot afișa direct suma după buclă?

Numai dacă variabila respectivă este definită și corectă pentru toate intrările. Pentru indici mici, bucla poate să nu ruleze. Programul prezentat afișează variabila de stare potrivită și tratează separat zero.

De ce apar două valori unu consecutive?

Termenul de indice unu este o valoare inițială, iar cel de indice doi este suma dintre zero și unu. Sunt poziții diferite, chiar dacă au aceeași valoare.

Cum verific rapid o soluție proprie?

Testează indicii zero, unu, doi și un indice mai mare, apoi urmărește ordinea atribuirilor și limita tipului numeric. Dacă justificarea rămâne neclară, poți cere o analiză pas cu pas la meditații de informatică.