De ce contează?
La olimpiadă primești un șir de numere și trebuie să-l continui sau să-l generezi. Cel mai costisitor greșit e să scrii cod pentru tipul greșit. Câteva secunde de diagnostic — diferențe, rapoarte, recurență — îți salvează ore.
Diagnosticul în 3 pași
Pasul 1 — calculezi diferențele consecutive
a[i] - a[i-1] pentru fiecare i- Dacă diferențele sunt toate egale → șir aritmetic. Gata.
- Dacă diferențele variază, treci la pasul 2.
Pasul 2 — calculezi rapoartele consecutive
a[i] / a[i-1] pentru fiecare i- Dacă rapoartele sunt toate egale → șir geometric. Gata.
- Dacă și rapoartele variază, treci la pasul 3.
Pasul 3 — cauți o recurență
Verifici dacă a[i] = a[i-1] + a[i-2] (Fibonacci) sau alte combinații ale termenilor anteriori. Uneori apare o constantă adăugată sau înmulțită.
Dacă niciuna din cele trei strategii nu funcționează, caută o formulă care depinde direct de index: a[i] = i², a[i] = 2^i + i etc. Testează întotdeauna cu cel puțin 3–4 perechi (index, valoare) înainte să scrii cod.
Tabel rapid de recunoaștere
| Ce calculezi | Ce obții | Tipul șirului |
|---|---|---|
a[i] - a[i-1] | Constantă d | Aritmetic |
a[i] / a[i-1] | Constantă r | Geometric |
a[i] - a[i-1] - a[i-2] | Constant 0 | Fibonacci-like |
| Altceva | Depinde | Recurent / formulă directă |
Exemplu pas cu pas
| a | 3 | 5 | 9 | 15 | 23 | 33 |
| i | 0 | 1 | 2 | 3 | 4 | 5 |
Diferențe: 2, 4, 6, 8, 10 — nu constante → nu e aritmetic.
Diferențele diferențelor: 2, 2, 2, 2 — constante!
Diferența crește ea însăși aritmetic → formula este pătratică. Verifici cu a[i] = i² + i + 3: i=0: 3 ✓, i=1: 5 ✓, i=2: 9 ✓, i=3: 15 ✓. Confirmă cu toți termenii înainte să scrii codul.
Greșeala 1: Te grăbești și presupui că orice șir care crește e aritmetic. Verifică mereu cu cel puțin 3-4 perechi consecutive.
Greșeala 2: Împarți la zero când calculezi rapoarte. Dacă orice termen e 0, raportul e nedefinit — tratează separat.
Greșeala 3: Găsești o regulă care funcționează pentru primii 3 termeni și presupui că e corectă. Verifică mereu cu toți termenii dați, nu doar cu primii.