Generarea șirurilor de numere

Introducere

De multe ori în problemele de informatică, apar șiruri de numere naturale care trebuie fie știute, cum va fi cazul unor șiruri consacrate precum șirul lui Fibonacci sau alte șiruri matematice precum cel al pătratelor sau cuburilor perfecte.

Deși la acest nivel, cele mai frecvent întâlnite aplicații sunt cele în care trebuie generate șirurile sau descoperite diverse reguli, aceste tehnici sunt foarte importante și trebuie însușite deoarece reprezintă un punct de plecare în vederea multor tehnici ce apar ulterior, în special când veți ajunge să învățați algoritmi mai avansați care duc cunoștințele de aici la un alt nivel.

Șiruri recurente

În general, când vom vorbi de șiruri de numere, ne vom concentra mai ales pe cele ai căror termeni se leagă unii de alții prin intermediul unor formule sau relații de recurență. Aceste șiruri se numesc recurente.

În general, ne va interesa să putem genera aceste șiruri și să găsim regulile de generare pentru diverse șiruri de numere naturale. Vom continua prin a prezenta unele șiruri foarte întâlnite în probleme.

Progresii aritmetice

În general, putem defini o progresie aritmetică folosind primul termen și diferența între termeni consecutivi.

Astfel, dacă primul termen este $x$ și rația este $r$, termenii progresiei aritmetice sunt $x, x + r, x + 2 \cdot r, \dots$

În general, pentru a afla suma primilor $n$ termeni ai unei progresii aritmetice, putem folosi formula următoare:

$S = n \cdot x + \frac{(n-1) \cdot n}{2} \cdot r$

Fiecare dintre cei $n$ termeni conține $x$, iar apoi următorii termeni au și $r,2 \cdot r, \dots, (n-1) \cdot r$.

Problemă exemplu - progresie3 - pbinfo

Pentru a afla în mod eficient dacă toate valorile aparțin aceleiași progresii aritmetice, trebuie să ținem un vector de frecvență în care memorăm aceste valori, iar mai apoi să verificăm dacă diferențele între oricare două valori distincte consecutive sunt egale.

--8 < --"usor/gen_sir/progresie3.cpp"

Problemă rezolvată - sir1 pbinfo

Pentru a rezolva această problemă, ne folosim de proprietățile sumei lui Gauss (progresie aritmetică cu rația 1). Astfel, aflăm câte grupe complete de valori există în șir și apoi aflăm valoarea corespunzătoare ultimei grupe rămase.

--8 < --"usor/gen_sir/sir1.cpp"

Progresii geometrice

În general, putem defini o progresie geometrică folosind primul termen și raportul între termeni consecutivi.

Astfel, dacă primul termen este $x$ și raportul este $r$, termenii progresiei aritmetice sunt $x, x \cdot r, x \cdot r^2, \dots$

În general, pentru a afla suma primilor $n$ termeni ai unei progresii geometrice, putem folosi formula următoare:

$S = x \cdot \frac{r^n - 1}{r - 1}$

În mod particular, dacă $r = 1$, suma primilor $n$ termeni este $n \cdot x$, deoarece toți termenii sunt constanți.

Această formulă se poate obține ușor dând factor comun pe $x$ și demonstrând suma prin inducție.

Șirul factorialelor numerelor naturale

Factorialul unui număr oarecare $n$ indică numărul de permutări (numărul de posibilități de rearanjare) ale unei mulțimi finite având $n$ elemente.

Primele câteva valori ale lui $n!$ sunt următoarele:

• $0! = 1$
• $1! = 1$
• $2! = 2$
• $3! = 6$
• $4! = 24$
• $5! = 120$
• $6! = 720$

Se poate remarca faptul că valorile factorialelor cresc foarte repede:

• $10! = 3 \ 628 \ 800$
• $13! = 6 \ 227 \ 020 \ 800$ (deja depășește valoarea maximă pe care o putem stoca într-o variabilă de tip int)
• $21! = 51 \ 090 \ 942 \ 171 \ 709 \ 440 \ 000$ (deja depășește valoarea maximă pe care o putem stoca într-o variabilă de tip long long)

De asemenea, valorile factorialelor, începând de la $5!$ se termină toate cu 0.

În mod particular, putem afla numărul de zerouri de la sfârșitul lui $n!$ ținând cont de faptul că pentru a obține un zero, trebuie să avem un factor de 2 și unul de 5 ($2 \cdot 5 = 10$), iar factorii de 5 apar mult mai rar decât cei de 2.

În general, pe lângă aplicațiile ce implică noțiuni mai simple, factorialele se vor dovedi a fi esențiale în ceea ce privește combinatorica, unde apar în multe formule, începând de la noțiunile legate de permutări.

Problemă exemplu - Trailing Zeroes

Această problemă ne cere fix cerința de mai sus, aflarea numărului de 0 de la sfârșitul factorialului pentru un număr $n$ dat. Deoarece știm că avem un număr suficient de factori de 2 în acest produs, trebuie să analizăm de câte ori apare 5 în reprezentarea în factori primi a factorialului.

În primul rând, fiecare număr divizibil cu 5 adaugă un zero la acest produs. Dar acest lucru nu este suficient deoarece numerele multiplu de $25 = 5^2$ adaugă încă un zero, la fel și cele multiplu de $125 = 5^3$ ș.a.m.d.

Astfel, numărul de zerouri de la finalul scrierii lui $n!$ este dat de formula

$\left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \dots + \left\lfloor \frac{n}{5^k} \right\rfloor$

unde $\lfloor x \rfloor$ reprezintă partea întreagă a lui $x$, iar $5^k$ este cea mai mare putere a lui 5 mai mică sau egală cu $n$.

--8 < --"usor/gen_sir/trailing_zeroes.cpp"

Șirul lui Fibonacci

Așa cum s-a menționat și în definiție, vom nota $F_n$ ca fiind cel de-al $n$-lea număr Fibonacci, iar aceste numere pot fi definite astfel:

• $F_0 = 0$
• $F_1 = 1$
• $F_n = F_{n-1} + F_{n-2}$

Aceste numere au numeroase proprietăți remarcabile, care au fost studiate de matematicieni și diverși alți oameni de știință, una dintre ele reprezintă faptul că pe măsură ce scriem numere fibonacci mai mari, raportul dintre două valori consecutive Fibonacci se apropie de numărul de aur.

Datorită acestui fapt, numerele Fibonacci cresc destul de repede, deja cel de-al 100-lea număr Fibonacci se apropie de limita maximă a long long, aici putând fi găsită o asemenea listă.

În informatică ne vom concentra mai ales pe găsirea acestor termeni și generalizarea unor proprietăți pe care le au numerele Fibonacci.

Pentru a afla cel de-al $n$-lea număr Fibonacci, putem folosi un algoritm destul de simplu, care se bazează pe un for sau un while.

--8 < --"usor/gen_sir/fibonacci.cpp"

Problema exemplu - fibosum

View Problem

PBInfo

Deschide

Pentru a rezolva această problemă, trebuie să aflăm toate valorile Fibonacci mai mici sau egale cu $n$, iar mai apoi să construim suma folosind termeni în ordine descrescătoare.

--8 < --"usor/gen_sir/fibosum.cpp"

Concluzii

Șirurile de numere naturale sunt foarte importante deoarece apar în multe probleme algoritmice și leagă cunoștințele obținute la matematică cu aplicarea lor algoritmică.

Fie că e vorba de șiruri precum cel al lui Fibonacci sau diferitele șiruri matematice discutate, cunoașterea acestor noțiuni va deveni foarte importantă pentru orice programator începător și nu numai.

Probleme suplimentare

• Probleme în care se generează șiruri de pe pbinfo
• pbinfo fiboverif
• pbinfo generare
• pbinfo sirk
• pbinfo sumapatrate
• pbinfo regula
• OJI 2006 factori
• ONI 2019 fibofrac
• Lot Juniori 2010 fibo

Resurse suplimentare

• Generarea sirurilor recurente - CPPI Sync
• Factorial - wikipedia
• Sirul lui Fibonacci - pbinfo
• Sirul lui Fibonacci - wikipedia
• Progresie aritmetica - wikipedia
• Progresie geometrica - wikipedia
• Factorial - pbinfo