Generarea șirurilor după reguli

De ce contează?

Dobânda bancară crește cu aceeași sumă în fiecare an — șir aritmetic. Populația unei bacterii se dublează la fiecare oră — șir geometric. Ambele urmează o regulă fixă și pot fi generate de un calculator cu câteva linii de cod.

Ce este un șir generat după o regulă?

Un șir este o succesiune de numere. „Generat după o regulă" înseamnă că există o formulă care determină orice termen din șir.

Două tipuri fundamentale:

Șir aritmetic

Fiecare termen = precedentul + o valoare fixă d (rația):

a[0], a[0]+d, a[0]+2d, a[0]+3d, ...

a	2	5	8	11	14
i	0	1	2	3	4

Șir aritmetic: primul termen 2, rație d = 3. Fiecare termen = precedentul + 3.

Șir geometric

Fiecare termen = precedentul × o valoare fixă r (rația):

a[0], a[0]*r, a[0]*r², a[0]*r³, ...

a	3	6	12	24	48
i	0	1	2	3	4

Șir geometric: primul termen 3, rație r = 2. Fiecare termen = precedentul × 2.

Algoritmul de generare

Indiferent de tip, structura e aceeași — o buclă care calculează fiecare termen:

for (int i = 0; i < n; i++) {
    // calculeaza a[i] dupa regula
    cout << a[i] << " ";
}

Implementare C++ — șiruri aritmetice și geometrice

#include <iostream>
using namespace std;

int main() {
    int n, a0, d, r;
    cin >> n;

    // sir aritmetic: primul termen a0, ratie d
    cin >> a0 >> d;
    cout << "Aritmetic: ";
    int termen = a0;
    for (int i = 0; i < n; i++) {
        cout << termen << " ";
        termen += d;             // fiecare termen = precedentul + d
    }
    cout << endl;

    // sir geometric: primul termen a0, ratie r
    cin >> a0 >> r;
    cout << "Geometric: ";
    termen = a0;
    for (int i = 0; i < n; i++) {
        cout << termen << " ";
        termen *= r;             // fiecare termen = precedentul * r
    }
    cout << endl;

    return 0;
}

Exemplu: n=5, aritmetic (2, d=3) → 2 5 8 11 14; geometric (3, r=2) → 3 6 12 24 48

Formula termenului general

Dacă vrei direct al n-lea termen fără să calculezi toți cei dinaintea lui:

Tip	Formula termenului de pe poziția i (de la 0)
Aritmetic	`a[i] = a[0] + i * d`
Geometric	`a[i] = a[0] * pow(r, i)`

Observația-cheie

Formula directă calculează orice termen în O(1), fără să parcurgă toți cei dinaintea lui. Dar pentru șiruri recurente (Fibonacci, de exemplu) nu există o formulă simplă — calculul pas cu pas este singura opțiune practică la concurs.

Complexitate

Caz	Timp	Spațiu
Generare n termeni	O(n)	O(1) dacă afișezi direct

Greșeli frecvente

Greșeala 1: Confunzi rația aritmetică (se adaugă) cu cea geometrică (se înmulțește). Verifică cu 2-3 perechi consecutive: dacă diferența e constantă → aritmetic; dacă raportul e constant → geometric.

Greșeala 2: Overflow la șiruri geometrice cu rație mare. 3 * 2^30 > 3 miliarde — depășește int. Folosește long long pentru orice șir geometric cu mai mulți termeni.

Greșeala 3: Folosești pow(r, i) din <cmath> pentru numere întregi — returnează double și poate da rezultate incorecte (ex. pow(2, 10) poate fi 1023.9999... trunchiat la 1023). Calculează puteri întregi cu înmulțiri, nu cu pow.