Generarea șirurilor

Generarea unui șir înseamnă calculul termenilor săi după o regulă, pornind de la date inițiale. Un exemplu: pornești de la 2 și adaugi de fiecare dată 3. Obții 2, apoi 5, apoi 8, apoi 11. Pentru a produce următorul termen trebuie să cunoști termenul curent și regula. Termenii se calculează în ordine, unul după altul: nu poți afla al cincilea termen fără să-l fi cunoscut pe al patrulea, dacă regula folosește termenul precedent.

Exemplu rezolvat — patru termeni. Primul termen este 2, iar regula este „adaug 3 la termenul precedent”. Vrei primii patru termeni.

1. Scrii primul termen, 2, și îl păstrezi ca termen curent.
2. Calculezi termenul următor: $2+3=5$. Acum termenul curent este 5.
3. Calculezi $5+3=8$; termenul curent este 8.
4. Calculezi $8+3=11$; termenul curent este 11. Ai scris patru termeni și te oprești.

Șirul obținut este $2,5,8,11$. Pentru patru termeni afișezi întâi valoarea inițială și faci doar trei actualizări, nu patru: o actualizare în plus ar calcula un al cincilea termen, 14, care nu mai este cerut.

Regula poate fi și altfel. Dacă pornești de la 1 și dublezi, obții 1, 2, 4, 8. Dacă pornești de la 1 și aplici regula „dublez și adaug 1”, obții 1, 3, 7, 15. În toate cazurile ai nevoie de trei lucruri: primul termen, regula și numărul de termeni care se afișează. Dacă lipsește unul dintre ele, șirul nu este stabilit. Când urmărești un astfel de algoritm, scrie pe rând termenul curent și numărul de termeni deja afișați; astfel vezi dacă te oprești la timp.

În unele șiruri regula folosește pozițiile, nu termenul precedent: dacă al $k$-lea termen este $3k$, poți calcula direct al 7-lea termen, 21, fără să-i cunoști pe ceilalți. Alegerea între cele două feluri de reguli depinde de enunț, iar în ambele cazuri trebuie să știi câți termeni se cer.

Un șir generat după o recurență are forma: se dă primul termen (sau primii câțiva) și o regulă care calculează fiecare termen din cei precedenți. Pentru o progresie aritmetică cu $a_1=3$ și rația $4$, recurența este $a_{k+1}=a_k+4$, iar formula directă este $a_n=3+4(n-1)$. Algoritmul păstrează într-o variabilă termenul curent, îl afișează și apoi îl actualizează; numărul de repetări este numărul de termeni.

Exemplul 1 — progresia aritmetică.

n = int(input())
termen = 3
for _ in range(n):
    print(termen, end=" ")
    termen += 4

La intrarea 4, ieșirea este 3 7 11 15 , inclusiv spațiul de la sfârșit. Înaintea iterațiilor, termen are pe rând valorile 3, 7, 11, 15. După ultima afișare, actualizarea îl schimbă în 19, dar acesta nu apare la ieșire. Pentru n = 0 nu se afișează niciun termen. Invariantul este: înaintea iterației cu indicele $i$ pornit de la zero, termen este $a_{i+1}=3+4i$. Formula directă confirmă ultimul termen: $a_4=3+4\cdot 3=15$.

Exemplul 2 — o recurență neliniară. Șirul cu $a_1=1$ și $a_{k+1}=2a_k+1$ are termenii $1,3,7,15,31$. Se observă că $a_k=2^k-1$: $2^5-1=31$. Programul care îl generează este același, cu altă actualizare:

termen = 1
for _ in range(5):
    print(termen, end=" ")
    termen = 2 * termen + 1

El afișează 1 3 7 15 31 . Ordinea instrucțiunilor din corp contează: dacă actualizarea ar fi scrisă înainte de afișare, primul termen afișat ar fi 3, iar 1 nu ar mai apărea.

Exemplul 3 — recurența și formula directă. Pentru a afla al zecelea termen al progresiei din primul exemplu există două căi: se repetă actualizarea de nouă ori, sau se aplică formula $a_{10}=3+4\cdot 9=39$. Cele două rezultate coincid. Formula este mai rapidă, pentru că cere un număr constant de operații, pe când generarea cere $n$ pași. În schimb, dacă sunt necesari toți termenii, generarea îi produce pe măsură ce îi calculează, în timp $O(n)$ și cu memorie auxiliară constantă. Dacă enunțul cere un singur termen, formula este de preferat.

Exemplul 4 — regula cu doi termeni anteriori. Dacă fiecare termen este suma celor doi precedenți, sunt necesari doi termeni inițiali. Pentru $a_1=1$, $a_2=1$ și $a_{k+2}=a_{k+1}+a_k$ se obține șirul $1,1,2,3,5,8,13,21$. Se păstrează în două variabile ultimii doi termeni, iar la fiecare pas ei „alunecă” cu o poziție: a, b = b, a + b atribuie simultan noile valori, deci nu se pierde vechea valoare a lui a.

a, b = 1, 1
for _ in range(8):
    print(a, end=" ")
    a, b = b, a + b

Programul afișează 1 1 2 3 5 8 13 21 . Ciclul afișează primul termen din pereche și apoi avansează perechea. Numărul de termeni afișați este numărul de repetări, indiferent de valorile calculate.

Exemplul 5 — generare până la o condiție. Uneori nu se cunoaște numărul de termeni, ci o condiție de oprire. Se dublează de la 3 până când termenul depășește 100 și se numără pașii:

t = 3
pasi = 0
while t <= 100:
    t *= 2
    pasi += 1
print(t, pasi)

Valorile lui t sunt 3, 6, 12, 24, 48, 96 și 192. Condiția t <= 100 este adevărată pentru primele șase, deci corpul se execută de 6 ori, iar bucla se oprește la 192. Se afișează 192 6. Numărul de pași este proporțional cu ${\log }_2$ din raportul dintre pragul 100 și valoarea de start, fiindcă termenul se dublează la fiecare pas; condiția de oprire trebuie să se schimbe în corpul buclei, altfel ciclul nu se termină.

Greșeli frecvente

• Greșit: pentru patru termeni se fac patru actualizări înainte de prima afișare.
  Corect: se afișează primul termen, apoi se fac trei actualizări.
• Greșit: regula se aplică poziției termenului, nu valorii precedente.
  Corect: depinde de definiție; într-o recurență regula folosește termenul precedent.
• Greșit: ordinea dintre afișare și actualizare nu contează.
  Corect: dacă actualizezi înaintea afișării, primul termen nu mai apare.

Înainte și după