Recapitulare Algoritmi

Un algoritm este o secventa finita si bine definita de pasi pentru rezolvarea unei probleme. Gandeste-te la algoritmul ca la o reteta de bucatarie: ai ingrediente (datele de intrare), urmezi pasii in ordine (instructiunile) si obtii un rezultat (datele de iesire). La fel cum o reteta buna poate fi urmata de oricine, un algoritm bun poate fi executat de orice calculator.

Caracteristicile unui algoritm corect:

• Finit: Se termina dupa un numar finit de pasi. Un algoritm care ruleaza la infinit (bucla infinita) este gresit.
• Precis (Deterministic): Fiecare pas este clar definit, fara ambiguitate. Nu exista pasi care pot fi interpretati in mai multe feluri.
• Date de intrare (INPUT): Primeste date pe care le prelucreaza. Datele pot veni de la utilizator (tastatura) sau din alte surse.
• Date de iesire (OUTPUT): Produce rezultate care raspund la problema initiala. Un algoritm fara rezultat nu are sens.
• Eficient: Rezolva problema in timp rezonabil, fara pasi inutili sau redundanti.
• General: Functioneaza pentru orice set valid de date de intrare, nu doar pentru un caz particular.

Algoritmii pot fi reprezentati in mai multe moduri: in limbaj natural (descriere in cuvinte), in pseudocod (un limbaj simplificat, intre limbajul natural si un limbaj de programare) sau prin schema logica (diagrama cu forme geometrice). In aceasta clasa, folosim in principal pseudocodul si schema logica.

Un exemplu simplu de algoritm din viata de zi cu zi: cum traversezi strada la semafor. Pas 1: Te opresti la trecerea de pietoni. Pas 2: Te uiti la semafor. Pas 3: DACA lumina este verde ATUNCI traverseaza. ALTFEL asteapta pana cand devine verde. Acest exemplu include o decizie (DACA-ATUNCI-ALTFEL) si este un algoritm complet, cu intrare (culoarea semaforului), prelucrare (decizia) si iesire (actiunea de a traversa sau de a astepta).

Este important sa intelegi ca un algoritm nu este acelasi lucru cu un program. Algoritmul este ideea , logica de rezolvare, independenta de limbajul de programare. Programul este implementarea algoritmului intr-un limbaj specific (Python, C++, Java). Acelasi algoritm poate fi scris in orice limbaj de programare, dar logica ramane identica.

O variabila este o locatie de memorie care are un nume si stocheaza o valoare . Gandeste-te la variabila ca la o cutie etichetata: eticheta este numele variabilei, iar continutul cutiei este valoarea. Valoarea se poate schimba pe parcursul executiei algoritmului, de aceea se numeste "variabila" (se variaza).

Numele unei variabile trebuie sa fie sugestiv (sa indice ce stocheaza): "varsta", "nota", "suma", "numar" sunt nume bune. "x", "a", "abc" sunt nume acceptabile dar mai putin clare. Numele nu poate contine spatii sau caractere speciale.

Operatii de baza in pseudocod:

Simbolul ← (sageata stanga) este operatorul de atribuire in pseudocod. Citeste-l ca "primeste valoarea" sau "devine". De exemplu, "x ← 5" se citeste "x primeste valoarea 5" sau "x devine 5". Nu confunda atribuirea (←) cu comparatia (=). Atribuirea pune o valoare intr-o variabila, pe cand comparatia verifica daca doua valori sunt egale.

Operatori aritmetici:

• + adunare, - scadere, * inmultire, / impartire
• % (modulo) - restul impartirii. Exemplu: 7 % 3 = 1 (7 impartit la 3 da 2 cu restul 1)
• DIV - catul impartirii intregi. Exemplu: 7 DIV 3 = 2

Operatorul % (modulo) este extrem de util. Il folosesti pentru a verifica daca un numar este par (numar % 2 = 0) sau impar (numar % 2 ≠ 0), pentru a extrage ultima cifra a unui numar (numar % 10) sau pentru a verifica daca un numar este divizibil cu altul (a % b = 0 inseamna ca a este divizibil cu b).

Structura alternativa (sau structura de decizie) permite executarea unor instructiuni doar daca o conditie este adevarata . Este echivalentul in algoritmi al deciziilor pe care le luam zilnic: "DACA plouă ATUNCI iau umbrela, ALTFEL nu iau umbrela."

Forma simpla (fara ALTFEL):

Forma completa (cu ALTFEL):

Structuri DACA imbricate (una in interiorul alteia) se folosesc cand ai mai mult de doua optiuni:

Operatori de comparare: = (egal), ≠ (diferit), < (mai mic), > (mai mare), ≤ (mai mic sau egal), ≥ (mai mare sau egal).

Operatori logici: SI (AND - ambele conditii trebuie adevarate), SAU (OR - cel putin una adevarata), NU (NOT - neaga conditia). Exemplu: "DACA varsta >= 14 SI varsta <= 18 ATUNCI SCRIE 'Adolescent'" - ambele conditii trebuie indeplinite simultan.

O greseala frecventa este sa uiti SFARSIT DACA . Fiecare DACA trebuie sa aiba un SFARSIT DACA corespunzator. Daca ai DACA imbricate, numarul de SFARSIT DACA trebuie sa fie egal cu numarul de DACA. Indentarea (alinierea cu spatii spre dreapta) te ajuta sa vezi clar care SFARSIT DACA corespunde carui DACA.

Structura CAT TIMP (WHILE) repeta un bloc de instructiuni cat timp o conditie este adevarata . Cand conditia devine falsa, repetarea se opreste si algoritmul continua cu urmatoarea instructiune de dupa SFARSIT CAT TIMP.

Exemplu: numara de la 1 la 5

In exemplul de mai sus, variabila i porneste de la 1. La fiecare repetare: se afiseaza valoarea lui i, apoi i creste cu 1. Cand i ajunge la 6, conditia "i <= 5" devine falsa si bucla se opreste. Rezultat: se afiseaza 1, 2, 3, 4, 5.

Atentie la bucla infinita! Daca uiti sa modifici variabila din conditie in interiorul buclei, conditia ramane mereu adevarata si bucla nu se opreste niciodata. In exemplul de mai sus, daca omiți linia "i ← i + 1", variabila i ramane mereu 1, conditia "1 <= 5" este mereu adevarata, si algoritmul afiseaza 1 la infinit. Acesta este un exemplu clasic de bucla infinita - una dintre cele mai frecvente greseli in algoritmi.

CAT TIMP este potrivit cand nu stii dinainte de cate ori se va repeta bucla. De exemplu: "Citeste numere de la utilizator CAT TIMP numarul este pozitiv" - nu stii de la inceput cate numere va introduce utilizatorul. Un alt exemplu: "Imparte numarul la 2 CAT TIMP este par" - nu stii de cate ori va fi impartit.

Un aspect important: in CAT TIMP, conditia se verifica inainte de fiecare executie. Daca conditia este falsa de la inceput, instructiunile din bucla nu se executa niciodata (zero executii). De exemplu, daca i = 10 si conditia este "i <= 5", bucla nu se executa deloc.

Structura PENTRU (FOR) repeta un bloc de instructiuni de un numar cunoscut de ori . Este mai simpla decat CAT TIMP, pentru ca variabila de control (contorul) se incrementeaza automat - nu trebuie sa o incrementezi manual.

Exemplu: afiseaza numerele de la 1 la 5

In PENTRU, variabila i primeste automat valorile de la valoarea initiala la valoarea finala, crescand cu 1 la fiecare pas. Nu trebuie sa scrii "i ← i + 1" - se face automat. Unele variante de pseudocod permit si un pas (step) diferit de 1, de exemplu: "PENTRU i ← 2, 10, PAS 2" parcurge numerele 2, 4, 6, 8, 10.

Cand folosesti PENTRU vs CAT TIMP?

• Foloseste PENTRU cand stii exact de cate ori se repeta bucla: "afiseaza primele 10 numere", "calculeaza suma notelor a 5 elevi", "citeste 20 de valori".
• Foloseste CAT TIMP cand nu stii dinainte numarul de repetari: "citeste numere pana cand utilizatorul introduce 0", "imparte numarul la 2 cat timp este par".

Exemplu practic: suma primelor n numere naturale

In acest exemplu, variabila suma este initializata cu 0 (un acumulator). La fiecare pas, adauga valoarea curenta a lui i la suma. Daca n = 4, suma parcurge valorile: 0+1=1, 1+2=3, 3+3=6, 6+4=10. Rezultat final: suma = 10.

Un concept important: variabila acumulator (cum e "suma" in exemplul de mai sus) trebuie intotdeauna initializata cu 0 inainte de bucla daca acumulezi o suma, sau cu 1 daca acumulezi un produs. Fara initializare, valoarea acumulatorului ar fi nedefinita si rezultatul ar fi gresit.

Un trace table (tabel de urmarire) este un instrument esential pentru a verifica daca un algoritm functioneaza corect. Urmaresti pas cu pas valorile tuturor variabilelor, exact asa cum le-ar calcula un calculator. Este ca o simulare manuala a executiei algoritmului.

Exemplu: calculeaza suma numerelor de la 1 la 3

Trace table:

Rezultat final: suma = 6 (1+2+3 = 6).

Trace table-ul este deosebit de util la evaluari. Cand primesti un algoritm si esti intrebat "Ce afiseaza acest algoritm?" sau "Ce valoare are variabila x dupa executie?", trace table-ul iti da raspunsul sigur. Urmeaza fiecare linie de cod in ordine, actualizeaza valorile variabilelor si noteaza ce se afiseaza.

Sfaturi pentru trace table:

• Scrie toate variabilele in capul tabelului, inclusiv variabilele de control ale buclelor (i, j).
• La fiecare pas, actualizeaza DOAR variabilele care se modifica. Restul pastreaza valoarea anterioara.
• Fii atent la ordinea operatiilor: intai se evalueaza partea dreapta a atribuirii, apoi rezultatul se pune in variabila din stanga.
• La structurile DACA, noteaza daca conditia este adevarata sau falsa si urmeaza ramura corespunzatoare.
• La bucle, verifica conditia la FIECARE iteratie. Nu te opri prea devreme si nu continua dupa ce conditia a devenit falsa.

Schema logica (flowchart) este o reprezentare grafica a unui algoritm, folosind forme geometrice conectate prin sageti. Fiecare forma are un rol precis si trebuie sa le cunosti pe toate pentru evaluare.

Simbolurile din schema logica:

• Oval (elipsa): Marcheaza START si STOP (inceputul si sfarsitul algoritmului). Fiecare schema logica are exact un START si cel putin un STOP.
• Paralelogram: Reprezinta operatiile de Citire (INPUT) si Afisare (OUTPUT) . Scrii "Citeste x" sau "Scrie x" in interiorul paralelogramului.
• Dreptunghi: Reprezinta o instructiune sau un calcul (atribuire, operatii aritmetice). Exemplu: "suma ← suma + i".
• Romb (diamond): Reprezinta o decizie (conditie) . Are doua iesiri : una marcata "DA" (conditia adevarata) si una marcata "NU" (conditia falsa). Aceasta forma corespunde structurii DACA din pseudocod.
• Sageti: Indica directia de executie , ordinea in care se parcurg pasii. Fiecare forma trebuie sa aiba cel putin o sageata de intrare si una de iesire (cu exceptia START care are doar iesire si STOP care are doar intrare).

Schema logica ajuta la vizualizarea fluxului algoritmului . Este deosebit de utila pentru algoritmi cu structuri de decizie si bucle, unde parcursul poate fi diferit in functie de datele de intrare. Un avantaj fata de pseudocod este ca poti vedea imediat toate ramurile posibile si unde se intorc buclele.

Cand desenezi o schema logica, respecta cateva reguli: START este intotdeauna sus, STOP este intotdeauna jos. Fluxul principal merge de sus in jos. Ramurile DA ale deciziilor merg de obicei in dreapta sau in jos, iar ramurile NU merg in stanga. Sagetile de bucla se intorc in sus, creand un ciclu vizibil.

Un exercitiu bun pentru exersare: ia un algoritm scris in pseudocod si transforma-l in schema logica, sau invers - ia o schema logica si scrie pseudocodul corespunzator. Aceasta conversie te ajuta sa intelegi profund logica algoritmului si te pregateste pentru intrebarile de la evaluare.

Exista cativa algoritmi fundamentali care apar frecvent in probleme si la evaluari. Trebuie sa ii cunosti bine si sa poti aplica logica lor in situatii noi.

1. Verificare par/impar:

Logica: daca restul impartirii la 2 este 0, numarul este par. Altfel, este impar. Simplu dar fundamental.

2. Gasirea minimului/maximului din n numere:

Logica: citim primul numar si il consideram maximul. Apoi, pentru fiecare numar urmator, verificam daca este mai mare decat maximul curent. Daca da, actualizam maximul. La sfarsit, "max" contine cel mai mare numar. Pentru minim, schimbi ">" cu "<" si "max" cu "min".

3. Numararea elementelor cu o proprietate:

Logica: variabila "contor" porneste de la 0 si creste cu 1 de fiecare data cand gasim un numar care indeplineste conditia (in acest caz, x > 0). La sfarsit, "contor" contine numarul total de elemente pozitive. Poti schimba conditia pentru a numara orice: numere pare, numere mai mari ca 10, numere negative, etc.

Un tip de problema frecvent in algoritmi este prelucrarea cifrelor unui numar: suma cifrelor, numararea cifrelor, inversarea numarului sau gasirea celei mai mari cifre. Toate aceste probleme folosesc doi operatori cheie: % 10 (extrage ultima cifra) si DIV 10 sau / 10 (elimina ultima cifra).

Operatiile fundamentale:

• numar % 10 - extrage ultima cifra. Exemplu: 325 % 10 = 5.
• numar DIV 10 (sau numar / 10 impartire intreaga) - elimina ultima cifra. Exemplu: 325 DIV 10 = 32.

Exemplu: suma cifrelor unui numar

Trace table pentru n = 325:

Rezultat: suma cifrelor lui 325 este 10 (3+2+5 = 10).

Observa ca folosim CAT TIMP (nu PENTRU), pentru ca nu stim dinainte cate cifre are numarul. Bucla se opreste cand n devine 0 (nu mai sunt cifre de extras). Acest pattern (extrage cifra cu % 10, elimina cifra cu DIV 10, repeta cat timp n > 0) este baza pentru toate problemele cu cifre.

Alte variante ale acestei probleme pe care le poti intalni: numararea cifrelor (folosesti un contor in loc de suma), cifra maxima (folosesti algoritmul de maxim pe fiecare cifra extrasa), inversarea numarului (construiesti un numar nou: invers ← invers * 10 + cifra), sau verificarea daca un numar este palindrom (compari numarul original cu inversul sau).

Orice algoritm, indiferent cat de complex, este construit din trei structuri fundamentale . Intelegerea lor profunda si capacitatea de a le combina este tot ce ai nevoie pentru a rezolva orice problema algoritmica de la acest nivel.

1. Structura secventiala (liniara):

• Instructiunile se executa una dupa alta , in ordine, de sus in jos.
• Include: citire, scriere, atribuire, calcule.
• Este cea mai simpla structura - nu exista ramificari sau repetari.
• Exemplu: citeste doua numere, calculeaza suma, afiseaza rezultatul.

2. Structura alternativa (de decizie):

• Executa instructiuni diferite in functie de o conditie .
• Include: DACA-ATUNCI, DACA-ATUNCI-ALTFEL, DACA imbricate.
• Permite algoritmului sa ia decizii si sa urmeze cai diferite.
• Exemplu: daca nota >= 5 afiseaza "Promovat", altfel afiseaza "Nepromovat".

3. Structura repetitiva (iterativa):

• Repeta un bloc de instructiuni de mai multe ori.
• Include: CAT TIMP (cand nu stii numarul de repetari) si PENTRU (cand stii).
• Permite prelucrarea unor cantitati mari de date fara a scrie aceleasi instructiuni de multe ori.
• Exemplu: calculeaza suma a n numere, gaseste maximul dintr-un sir de valori.

Aceste trei structuri pot fi combinate si imbricate (puse una in interiorul alteia) in orice mod. De exemplu, poti avea un PENTRU care contine un DACA (pentru a numara elementele cu o proprietate), sau un CAT TIMP care contine un alt CAT TIMP (pentru probleme mai complexe).

Lista de verificare pentru evaluare:

• Stiu sa scriu corect operatiile de baza: CITESTE, SCRIE, atribuire (←).
• Stiu sa folosesc DACA-ATUNCI-ALTFEL si DACA imbricate.
• Stiu sa folosesc CAT TIMP si PENTRU si inteleg cand sa folosesc fiecare.
• Stiu sa fac un trace table (urmarirea executiei pas cu pas).
• Stiu simbolurile schemei logice (oval, paralelogram, dreptunghi, romb).
• Stiu algoritmii clasici: par/impar, minim/maxim, suma/numarare, cifre numar.
• Stiu operatorii: aritmetici (+, -, *, /, %), comparare (=, ≠, <, >, ≤, ≥), logici (SI, SAU, NU).

Un sfat final: la evaluare, daca nu esti sigur de raspuns, fa un trace table . Alege valori concrete de test, parcurge algoritmul pas cu pas si noteaza valorile variabilelor. Aceasta metoda iti da intotdeauna raspunsul corect, chiar daca necesita mai mult timp. Nu te baza pe intuitie cand poti verifica matematic.

Pana acum am lucrat cu algoritmi in pseudocod si scheme logice . Acestea sunt reprezentari conceptuale ale solutiei. Conform programei scolare (OMEN 3393/2017), domeniul "Limbaj de programare (introducere)" cere si cunoasterea pasilor urmatori: editarea codului intr-un mediu de programare, rularea programului si depanarea erorilor (competentele VII-1.4 si VII-3.3).

Un mediu de dezvoltare este un program special in care:

• Editezi codul sursa — scrii instructiunile intr-un limbaj de programare real. De exemplu, in Python, pseudocodul DACA devine if , CAT TIMP devine while , PENTRU devine for , iar SCRIE devine print() .
• Rulezi programul — calculatorul executa codul si produce rezultatele in consola. Daca nu exista erori, vei vedea iesirea (output) asteptata.
• Depanezi (debug) erorile — daca programul produce rezultate gresite sau mesaje de eroare, le corectezi. Erorile pot fi de sintaxa (cod scris gresit) sau logice (codul ruleaza dar rezultatul este gresit).

Corespondenta pseudocod — cod Python (exemplu: suma primelor n numere):

Corespondentele directe: pseudocod CITESTE n devine n = int(input()) ; pseudocod PENTRU i ← 1, n EXECUTA devine for i in range(1, n+1): ; pseudocod SCRIE suma devine print(suma) . Logica algoritmului este identica in ambele forme — doar sintaxa difera.

Tipuri de erori frecvente:

• Eroare de sintaxa: ai scris gresit o instructiune. Mediul de programare iti arata linia cu eroarea si o descriere a problemei.
• Eroare logica: programul ruleaza fara mesaje de eroare, dar rezultatul este gresit. De exemplu, ai initializat acumulatorul cu 1 in loc de 0. Depanarea consta in verificarea pas cu pas a valorilor variabilelor — exact ca un trace table!

Concluzie esentiala: pseudocodul si schema logica sunt instrumentele de proiectare a algoritmului. Mediul de programare este instrumentul de implementare si testare . Ambii pasi sunt obligatorii in procesul complet de rezolvare a unei probleme cu calculatorul.