De ce contează?
Urci scări și pui o monedă pe fiecare treaptă, dar mereu cu una mai mult decât pe treapta de dedesubt: 1, 2, 3, 4... Sau dublezi: 1, 2, 4, 8... Fiecare șir urmează o regulă. Dacă o cunoști, poți genera oricâți termeni vrei, fără să-i memorezi pe toți.
Două feluri de reguli
Un șir e o succesiune de valori a₁, a₂, a₃, .... Regula care le leagă poate fi:
- Explicită — termenul direct din poziție:
aₙ = 2n + 1→ 3, 5, 7, 9, ... - Recurentă — termenul din precedenți:
aₙ = aₙ₋₁ + 3, cua₁ = 3→ 3, 6, 9, 12, ...
Ambele descriu un șir, dar le calculezi diferit. Explicită: sari direct la orice termen. Recurentă: trebuie să construiești pas cu pas din cazul de bază. Alegi forma care se potrivește problemei.
Algoritm pas cu pas: regula recurentă aₙ = aₙ₋₁ + 3
Pornim de la a₁ = 3 și aplicăm regula:
| aₙ | 3 | 6 | 9 | 12 | 15 |
| n | 1 | 2 | 3 | 4 | 5 |
| n | calcul | aₙ |
|---|---|---|
| 1 | (start) | 3 |
| 2 | 3 + 3 | 6 |
| 3 | 6 + 3 | 9 |
| 4 | 9 + 3 | 12 |
Implementare: generare cu regulă recurentă
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long termen = 3; // a1, cazul de baza
cout << termen << " ";
for (int i = 2; i <= n; i++) {
termen = termen + 3; // regula recurenta
cout << termen << " ";
}
return 0;
}Pentru n = 5 → 3 6 9 12 15. Reținem un singur termen — nu tot vectorul.
Implementare: generare cu regulă explicită
Când termenul se calculează direct, nici nu ai nevoie de istoric:
for (int n = 1; n <= 5; n++) {
long long termen = 2 * n + 1; // formula directa
cout << termen << " "; // 3 5 7 9 11
}La regula explicită nu te interesează termenii anteriori — sari direct la oricare. E ideal când vrei „al 1000-lea termen" fără să-i calculezi pe primii 999.
Complexitate
| Vrei | Timp | Spațiu |
|---|---|---|
| primii n termeni | O(n) | O(1) dacă reții doar ce trebuie |
| al n-lea termen (formulă explicită) | O(1) | O(1) |
Capcane reale la generarea șirurilor:
- Uiți cazul de bază: la regula recurentă, fără termenul de start nu poți porni, sau pornești de la 0/gunoi → tot șirul iese greșit.
- Off-by-one la indici: confunzi
a₁cua₀și generezi un termen în plus sau în minus. Fixează clar de unde începe numerotarea. - Overflow: șirurile cresc repede (mai ales cele multiplicative); folosește
long long. - Reții tot șirul inutil: dacă regula depinde doar de ultimul termen, două variabile ajung — nu aloca un vector de un milion.
De reținut
- Regulă explicită = termen direct din n; recurentă = din termenii anteriori (+ caz de bază).
- Generezi pas cu pas din cazul de bază; reții doar termenii de care depinde regula.
- Explicită → al n-lea termen în O(1); recurentă → O(n) pentru primii n.