Ce vei învăța astăzi?
După această lecție vei învăța să combini generarea de secvențe cu sortarea (să produci valorile după o regulă, apoi să le ordonezi) într-o singură problemă: să generezi datele după o regulă, să le ordonezi și să obții rezultatul cerut.
Modelul problemei combinate
Definiție: O problemă combinată cere două tipuri de prelucrări: mai întâi generăm o listă de valori după o regulă (o formulă, o condiție, o recurență), apoi sortăm lista și, la final, afișăm sau prelucrăm rezultatul.
Ordinea pașilor este esențială: nu putem sorta valori pe care nu le-am generat încă. De aceea, întâi construim lista completă, apoi o ordonăm.
De ce ne folosim?
Este ca organizarea unui concurs: întâi se adună toate punctajele (generarea), apoi se ordonează în clasament (sortarea), apoi se afișează rezultatele. Fiecare etapă are datele ei gata pregătite de etapa anterioară.
Producem valorile după regulă, una câte una
Ordonăm lista produsă, cu una din metode
Scriem rezultatul în formatul cerut
Exemplu: generăm resturi, apoi le sortăm
n = int(input())
valori = []
for i in range(1, n + 1):
valori.append((i * i) % 100)
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if valori[j] < valori[p]:
p = j
valori[i], valori[p] = valori[p], valori[i]
for x in valori:
print(x, end=" ")
Observă: pentru n = 5 valorile generate sunt 1, 4, 9, 16, 25, deja sortate; pentru n = 20 apar resturi care se repetă, iar sortarea le ordonează corect.
Cifrele unui număr: generare, sortare, reconstrucție
O problemă clasică de examen: se citește un număr n și se cere cel mai mare număr care se poate forma cu cifrele lui. Pașii sunt: extragem cifrele (generare cu % 10 și // 10), le sortăm descrescător, apoi reconstruim numărul (reasamblăm cifrele într-un singur număr, cu rezultat * 10 + c).
Observăm că cifrele se extrag în ordine inversă; de aceea sortarea este obligatorie înainte de reconstrucție.
Exemplu: cel mai mare număr din cifrele lui 25031
n = int(input())
cifre = []
while n > 0:
cifre.append(n % 10)
n = n // 10
for i in range(len(cifre) - 1):
p = i
for j in range(i + 1, len(cifre)):
if cifre[j] > cifre[p]:
p = j
cifre[i], cifre[p] = cifre[p], cifre[i]
rezultat = 0
for c in cifre:
rezultat = rezultat * 10 + c
print(rezultat)
Observă: pentru n = 25031, cifrele generate sunt 1, 3, 0, 5, 2; sortate descrescător devin 5, 3, 2, 1, 0, iar reconstrucția dă 53210 - cel mai mare număr posibil.
Divizorii unui număr, generați eficient și sortați
Generarea eficientă a divizorilor parcurge i doar până la rădăcina pătrată a lui n (valoarea r cu r * r = n): dacă i divide n, atunci și n // i este divizor. Avantajul este viteză: pentru n = 1000000 parcurgem doar 1000 de valori. Dezavantajul: divizorii apar în dezordine, deci este nevoie de o sortare.
Exemplu: divizorii lui 12 în ordine crescătoare
n = int(input())
divizori = []
i = 1
while i * i <= n:
if n % i == 0:
divizori.append(i)
if i != n // i:
divizori.append(n // i)
i = i + 1
for i in range(len(divizori) - 1):
p = i
for j in range(i + 1, len(divizori)):
if divizori[j] < divizori[p]:
p = j
divizori[i], divizori[p] = divizori[p], divizori[i]
for d in divizori:
print(d, end=" ")
Observă: pentru n = 12 se generează 1, 12, 2, 6, 3, 4 (în dezordine), iar sortarea produce 1 2 3 4 6 12. Condiția i != n // i evită dublarea rădăcinii pătrate perfecte.
Exercițiu de completare
Completează modelul problemei combinate:
Într-o problemă combinată, întâi ______ valorile după o regulă, apoi le ______ și la final afișăm rezultatul. Cifrele unui număr se extrag cu ______ 10 și // 10. Dacă i divide pe n, atunci și ______ este divizor.
Bancă de cuvinte:
Exercițiu de completare
Completează despre reconstrucția numărului:
Pentru a forma numărul din cifrele sortate, folosim rezultat = rezultat * ______ + c. Cifrele se extrag cu bucla ______, cât timp n este pozitiv. La divizori, bucla merge cât timp i * i ______ n. Verificarea i != n // i evită ______ rădăcinii.
Bancă de cuvinte:
Test de înțelegere
Test rapid - probleme combinate:
1. Ordinea corectă a pașilor într-o problemă combinată este:
2. Cifrele unui număr se extrag cu:
3. La generarea eficientă a divizorilor, bucla merge cât timp:
% 10 și // 10 în ordine inversă; fără o sortare înainte de reconstrucție, numărul format este greșit. La divizori, bucla merge doar până la i * i <= n.Aprofundare
Uneori, sortarea poate fi evitată: dacă regula de generare produce valorile deja în ordine, sortarea ar fi o muncă inutilă. Pătratele perfecte cresc odată cu indicele, la fel termenii Fibonacci și multiplii unui număr. Analizează regula înainte de a sorta.
- Costul sortării: generarea parcurge lista o dată (O(n)), dar sortarea prin selecție adaugă O(n²); pentru liste mari, această diferență contează enorm.
- Frecvențele după generare: dacă valorile generate sunt într-un interval mic (de exemplu resturi modulo k), sortăm cu lista de frecvențe în loc de O(n²).
- Reconstrucția numărului din cifre: formula
rezultat = rezultat * 10 + cfuncționează pentru orice număr de cifre și păstrează exactitatea, spre deosebire de concatenarea de texte. - Cifra 0 în față: dacă sortăm crescător și prima cifră este 0, numărul format are un zero conducător; la reconstrucție numărul rămâne corect matematic, dar cerința poate interzice acest caz.
- Divizorii cu perechi: tehnica i * i <= n reduce parcurgerea de la n la rădăcina pătrată a lui n - un câștig uriaș pentru n mare, cu prețul unei sortări obligatorii.
- Verificarea completă: numărul de divizori afișați și suma lor pot fi verificate pe hârtie pentru n mic (de exemplu 12 are 6 divizori).
PbInfo - Cel mai mare număr din cifre
Enunț:
Cerință: Se citește un număr natural n. Să se afișeze cel mai mare număr care se poate forma cu cifrele lui n, folosind o singură dată fiecare cifră.
Date de intrare:
Programul citește de la tastatură numărul natural n.
Date de ieșire:
Programul va afișa pe ecran numărul maxim care se poate forma cu cifrele lui n.
Restricții și precizări:
n este un număr natural cu cel mult 9 cifre, iar cifra 0 poate apărea în componența lui n.
Exemplu:
Intrare:
25031
Ieșire:
53210
Cum gândim soluția:
- Extragem cifrele cu
n % 10șin // 10, până când n devine 0 - Sortăm cifrele descrescător cu selecția minimului (căutăm maximul)
- Reconstruim numărul cu
rezultat = rezultat * 10 + c - Afișăm rezultatul cu
print()
Scrie soluția în Python:
Soluție corectă:
n = int(input())
cifre = []
while n > 0:
cifre.append(n % 10)
n = n // 10
for i in range(len(cifre) - 1):
p = i
for j in range(i + 1, len(cifre)):
if cifre[j] > cifre[p]:
p = j
cifre[i], cifre[p] = cifre[p], cifre[i]
rezultat = 0
for c in cifre:
rezultat = rezultat * 10 + c
print(rezultat)
Ce învățăm: generarea cifrelor cu buclă while, sortarea lor descrescătoare și reconstrucția numerică - trei tehnici într-o singură problemă.
PbInfo - Divizorii în ordine crescătoare
Enunț:
Cerință: Se citește un număr natural n. Să se afișeze toți divizorii lui n în ordine crescătoare, separați prin spații, folosind generarea eficientă a divizorilor.
Date de intrare:
Programul citește de la tastatură numărul natural n.
Date de ieșire:
Programul va afișa pe o singură linie divizorii lui n în ordine crescătoare, separați prin spații.
Restricții și precizări:
1 <= n <= 1000000, iar divizorii se pot afișa după generarea eficientă (i * i <= n) urmată de sortare.
Exemplu:
Intrare:
12
Ieșire:
1 2 3 4 6 12
Cum gândim soluția:
- Generăm divizorii cu bucla
while i * i <= n, adăugând i și n // i - Evităm dublarea rădăcinii cu verificarea
i != n // i - Sortăm lista crescător cu selecția minimului
- Afișăm divizorii pe o singură linie
Scrie soluția în Python:
Soluție corectă:
n = int(input())
divizori = []
i = 1
while i * i <= n:
if n % i == 0:
divizori.append(i)
if i != n // i:
divizori.append(n // i)
i = i + 1
for i in range(len(divizori) - 1):
p = i
for j in range(i + 1, len(divizori)):
if divizori[j] < divizori[p]:
p = j
divizori[i], divizori[p] = divizori[p], divizori[i]
for d in divizori:
print(d, end=" ")
Ce învățăm: generarea eficientă produce divizorii în dezordine, deci sortarea nu este un lux, ci o etapă obligatorie a problemei.
Exercițiul Practic: Generare și sortare combinate
Sarcini de lucru
Rezolvă probleme complete care combină generarea de secvențe cu sortarea.
Sarcina 1: Resturi generate și sortate
Cerință: Scrie un program care citește n și k, generează valorile (i * k) % 10 pentru i de la 1 la n, apoi le afișează sortate crescător.
Soluție:
n = int(input())
k = int(input())
valori = []
for i in range(1, n + 1):
valori.append((i * k) % 10)
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if valori[j] < valori[p]:
p = j
valori[i], valori[p] = valori[p], valori[i]
for x in valori:
print(x, end=" ")
Verifică: pentru n = 7 și k = 3, resturile generate sunt 3 6 9 2 5 8 1, iar după sortare: 1 2 3 5 6 8 9.
Sarcina 2: Cel mai mic număr din cifre
Cerință: Scrie un program care citește un număr n, extrage cifrele, le sortează crescător și afișează cel mai mic număr care se poate forma cu ele (fără zero conducător dacă există altă cifră).
Soluție:
n = int(input())
cifre = []
while n > 0:
cifre.append(n % 10)
n = n // 10
cifre.sort()
if cifre[0] == 0:
for i in range(1, len(cifre)):
if cifre[i] != 0:
cifre[0], cifre[i] = cifre[i], cifre[0]
break
rezultat = 0
for c in cifre:
rezultat = rezultat * 10 + c
print(rezultat)
Verifică: pentru n = 25031, cifrele sortate sunt 0 1 2 3 5; mutăm 1 în fața lui 0 și obținem 10235, cel mai mic număr valid.