Lecție-punte: formulă, simulare și recurență

De ce contează?

Vrei suma 1 + 2 + ... + 100. Poți aduna pe rând (100 de pași) sau poți folosi formula n(n+1)/2 și obții 5050 dintr-un singur calcul. Aceeași problemă, două drumuri. A ști când alegi formula, simularea sau recurența e jumătate din rezolvare.

Trei unelte pentru aceeași clasă de probleme

Formula închisă — o expresie directă în funcție de n. Răspuns în O(1).
Recurența — o regulă care leagă termenul de precedenți (Fibonacci, Tribonacci).
Simularea — aplici regula/procesul pas cu pas, de la start, până ajungi unde vrei.

Observația-cheie

Recurența și simularea sunt fețe ale aceluiași lucru: recurența e regula, simularea e derularea ei. Formula închisă e scurtătura — când există și o cunoști, sare peste toți pașii intermediari.

Cum alegi: arborele de decizie

Există o formulă directă și o știi? → folosește-o (O(1)), mai ales dacă n e uriaș.
Nu, dar poți lega termenul de precedenți? → recurență + simulare iterativă (O(n)).
Nici regula nu e clară? → simulează procesul direct, urmărind starea pas cu pas.

Același exemplu, trei abordări

Suma primelor n numere naturale:

// 1. FORMULA inchisa: O(1)
long long suma = (long long)n * (n + 1) / 2;

// 2. SIMULARE (derularea recurentei aₙ = aₙ₋₁ + n): O(n)
long long suma = 0;
for (int i = 1; i <= n; i++) {
    suma += i;
}

Ambele dau 5050 pentru n = 100. Pentru n = 10⁹, formula răspunde instant; simularea ar face un miliard de pași.

Observația-cheie

Dacă nu vezi formula, simularea îți dă oricum răspunsul corect — doar mai lent. De multe ori în concurs scrii întâi simularea (sigură), apoi, dacă n e prea mare, cauți formula închisă.

Când simularea e singura opțiune

Multe procese nu au formulă închisă simplă: cifrele lui n!, pașii lui Collatz, o simulare fizică. Acolo derulezi pas cu pas — nu există scurtătură.

Limita lui `n` decide

`n` până la	Abordare permisă
~10⁷	simulare O(n) e ok
~10⁹ și mai mult	ai nevoie de formulă O(1) sau O(log n)

Greșeli frecvente

Capcane reale la alegerea abordării:

Simulezi când n e uriaș: derulezi O(n) pași pentru n = 10¹² → depășești timpul. Dacă există formulă, folosește-o.
Cauți formulă unde nu există: pierzi timp pe o formulă închisă pentru un proces haotic; simularea ar fi dat răspunsul direct.
Formulă cu overflow: n(n+1)/2 pentru n mare se sparge în int chiar dacă rezultatul ar încăpea. Calculează în long long.
Confuzi recurența cu formula: o recurență nu e răspuns în O(1) — trebuie derulată (simulată), deci tot O(n), dacă nu o transformi într-o formulă închisă.

De reținut

Formulă închisă = O(1) (când există); recurență/simulare = O(n), aplicabile mereu.
Recurența e regula, simularea e derularea ei; formula e scurtătura.
Limita lui n decide: n mic → simulează; n uriaș → caută formula. Calculează în long long.