MINISTERUL EDUCAȚIEI NAȚIONALE Emanuela Cerchez Marinei Șerban imliti Profilul real Specializarea: matematicâ-informatică, științe ale naturii Manual pentru clasa a IX - a EDITURA DIDACTICA Șl PEDAGOGICA RA 4 NOȚIUNI INTRODUCTIVE - sistemul de operare reprezintă al doilea nivel al sistemului software și este constituit dintr-un ansamblu de programe care coordonează toate activitățile calculatorului; - programele de aplicații reprezintă nivelul superior, cel mai apropiat de utilizator, constituit din totalitatea programelor destinate rezolvării unor probleme specifice. 1.2. Informatica și societatea Prin inventarea calculatorului electronic s-a produs o adevărată revoluție a societății contemporane, care poate fi comparată, prin impactul produs, cu Revolu- ția Industrială. Astăzi nu există nici un domeniu al activității umane în care să nu fie utilizat calculatorul. Calculatorul a devenit nu doar o unealtă indispensabilă activității cotidiene, ci instrumentul care permite dezvoltarea în orice domeniu de activitate a unor tehnici avansate, inițiatoare ale progresului în domeniu. Primele calculatoare aveau putere mică de calcul, erau extrem de mari și extrem de costisitoare. Din acest motiv, au fost folosite inițial doar în institute de cercetare și universități. Dar chiar dacă, privite din perspectiva mileniului III, acele calcula- toare par ridicole, încă de la început s-au dovedit a fi instrumente utile, motiv pentru care au fost investite fonduri enorme pentru dezvoltarea acestui domeniu, industria calculatoarelor devenind domeniul cu cea mai rapidă evoluție. Dezvoltarea industriei calculatoarelor a fost însoțită de dezvoltarea unei noi industrii - cea a producătorilor de software. S-au înființat mari companii producă- toare de programe pentru diverse domenii de activitate, din ce în ce mai mulți oameni fiind implicați în activități legate de programare, de testare a programelor, de utilizare a acestora în domeniul propriu de activitate. O analiză, chiar sumară, a ofertelor de pe piața mondială a locurilor de muncă reflectă proporția dominantă în care sunt solicitați specialiști în informatică, precum și specialiști în alte domenii, dar cu solide cunoștințe de utilizare a calculatoarelor. Practic, de la apariția calcula- toarelor s-au înregistrat transformări treptate în specificul muncii umane. Omul este eliberat în mare măsură de muncile care necesită un efort fizic mare, de activitățile de rutină, devenind predominant rolul său creator. Pentru a ilustra aceste afirmații, să urmărim modul în care calculatorul este utilizat astăzi în diverse domenii ale activității umane. Cercetarea fundamentală în fizică, chimie, biologie s-a dezvoltat extrem de rapid în ultimele decenii, în principal datorită dezvoltării tehnologiei. In fizică un impact deosebit au avut dezvoltarea electronicii și a calculatoarelor, aplicațiile energiei nucleare și acceleratoarele de particule de mare energie. Fizicienii au fost primii care au utilizat calculatorul, la Los Alamos National Laboratory, un institut de cercetări înființat de Departamentul de Energie al S.U.A. Aici, în timpul celui de al II-lea război mondial, John von Neumann, INFORMATICA 5 creatorul arhitecturii actuale a calculatoarelor electronice, a fost cooptat consultant în proiectul bombei atomice. In chimie, sintetizarea unor substanțe chimice, prepararea unor noi compuși precum și predicția efectelor lor se realizează cu ajutorul calculatorului și al unor programe complexe de modelare. Faptul că astăzi pot fi sintetizați hormoni, enzime, material genetic identic cu cel al ființelor vii se datorează în cea mai mare măsură puternicelor facilități de modelare oferite de calculatoarele și programele modeme. Analizele chimice și medicale de mare precizie se realizează numai cu ajutorul calculatorului. în plus, în domeniul medicinei s-au dezvoltat noi tehnici chirurgicale asistate de calculator, precum și noi tehnici de investigație medicală, cum ar fi tomografiile computerizate. Au fost dezvoltate sistemele expert, programe complexe care au rolul de a lua decizii și de a rezolva probleme într-un domeniu specific, cum ar fi medicina sau contabilitatea, pe baza unor reguli și informații furnizate de specialiști în domeniu. Aceste programe acționează într-un mod similar experților umani și au două componente principale: o bază de cunoștințe (date și legi) specifice domeniului la care se aplică și un motor de inferență logică, ce reprezintă mecanismul prin care sistemul expert „raționează”, deci formulează concluzii sau ia decizii pe baza cunoștințelor de care dispune. Totuși, pentru a fi asemenea unui expert uman, aceste programe ar trebui să aibă o calitate în plus, aceea de a învăța. Acest aspect constituie una dintre cele mai importante preocupări ale unui domeniu de vârf în informatică, Inteligența Artificială¹. Dar cercetarea fundamentală nu este singurul domeniu în care este utilizat calcula- torul, ci toate aspectele activității umane sunt influențate de acesta. în producția industrială, procesul tehnologic este controlat de calculatoare speciale, denumite calculatoare de proces. Acestea sunt calculatoare analogice, care preiau ca date de intrare rezultatele măsurătorilor unor mărimi caracteristice procesului tehnologic (temperatură, presiune etc.) și iau deciziile necesare pentru reglarea și desfășurarea procesului tehno- logic în condiții optime. Calculatoarele nu sunt implicate numai în controlul producției indus- triale, ci chiar în producția propriu-zisă. Există mașini complexe, denumite roboți, care sunt coordonate de calculatoare și care au rolul de a executa un set de operații specifice, mult mai rapid, mai ieftin și mai precis decât un om. în plus, roboții pot lucra în zone care sunt Acest robot este capabil să țină un ou, fără să îl spargă. 1. Inteligența Artificială este un concept care definește capacitatea unui obiect artificial de a îndeplini funcții caracteristice gândirii umane. 6 NOȚIUNI INTRODUCTIVE periculoase pentru sănătatea oamenilor, în zone toxice, în adâncul oceanelor sau în spațiul cosmic. Roboții preiau prin intermediul unor senzori informații din mediul înconjurător și sunt programați pentru a fi capabili să își adapteze activitatea în funcție de variabilele de mediu. Activitatea de proiectare, fie că se referă la șuruburi, case, rochii, mașini sau nave spațiale, se realizează de asemenea cu ajutorul calculatorului. Există pachete de programe specializate pentru aceasta, care constituie un domeniu al informaticii denumit CAD (Computer Aided Design - Proiectare Asistată de Calculator). Acestea sunt însă exemple mult prea îndepărtate, pentru unii dintre noi, de viața de zi cu zi. Calculatoarele sunt implicate în orice activitate a noastră. Urmărim un film? Cu maximă probabilitate scenele cele mai spectaculoase din film sunt realizate pe calculator. De exemplu, scena cea mai dramatică a filmului „Titanic⁴⁴, scufundarea vaporului, când sute de oameni sar cu disperare de la mare înălțime, a fost realizată pe calculator, fără ca nimeni să își riște viața. Regizorul filmului a pus actorii să acționeze în diverse situații, preluând mișcările lor prin intermediul unor senzori. Mișcările au fost transferate asupra unor creaturi artifici- ale, fiecare reprezentare digitală fiind coordonată în mod individual pe calculator. Ascultăm o reclamă? Mixajul a fost cu siguranță realizat pe calculator. Vrem să știm cum va fi vremea? Predicția vremii este posibilă numai cu ajutorul calculatorului. O parte din informațiile necesare pentru prevederea vremii, de exemplu cele preluate din straturile superioare ale atmosferei, sunt înregistrate direct de către calculatoare specializate. Modelarea datelor înregistrate presupune efectuarea rapidă a unor calcule complexe, bazate pe ecuații matematice. Interpre- tarea cu cât mai multă acuratețe a datelor se realizează, de asemenea, cu programe specializate, deci tot cu ajutorul calculatorului. Vrem să plătim impozitele? La Administrația Financiară se lucrează pe calcula- tor, existând baze de date de evidență a locuințelor, automobilelor etc. Vrem să ne schimbăm buletinul? începând cu fotografia care va fi preluată cu ajutorul unei camere digitale, până la înregistrarea în evidențele computerizate ale Poliției, totul se realizează pe calculator. Ar fi mai greu să dăm un exemplu unde nu se utilizează calculatorul sau, mai exact, unde nu trebuie să se utilizeze calculatorul. în domeniul educației, calculatorul este o adevărată provocare pentru învăță- mântul tradițional. Informatica nu reprezintă doar o nouă disciplină de învățământ, ci produce un puternic impact asupra metodelor de învățare de la orice disciplină, din orice arie curriculară. De exemplu, accesul la Internet sau o enciclopedie multimedia reprezintă o importantă resursă educațională, oferind un spațiu informațional vast pentru toate domeniile de studiu. Calculatorul este privit ca un instrument indispensabil oricărei discipline, noile tehnologii multimedia INFORMATICA 7 reprezentând calea de a comunica idei, de a sistematiza informații, de a dezvolta proiecte. Pentru orice disciplină școlară există programe educaționale, care permit individualizarea învățării. CAI (Computer Assisted Instruction - învățarea Asistată de Calculator) reprezintă o nouă metodă de învățare, prin care profesorul pune la dispoziția elevului, pe calculator, materiale de curs, programe de învățare, teme de lucru, teste. Elevii studiază individual, în ritmul propriu, materialele respective. Acum calculatorul reprezintă sursa principală de informații, nu profesorul, rolul acestuia fiind de a coordona activitatea elevilor. Studiile realizate în legătură cu învățarea asistată de calculator au demonstrat că productivitatea învățării crește, elevii dobândesc o cantitate mai mare de informații într-un timp mai scurt, se dezvoltă curiozitatea științifică, se structurează mult mai bine motivațiile și aspira- țiile individuale și, nu în ultimul rând, elevilor le place să utilizeze calculatorul. Noi probleme în era informațională Utilizarea calculatorului în orice domeniu de activitate a produs o adevărată revoluție informațională. Așa cum era de așteptat, apar alte „puncte de fugă” în relațiile sociale, apar noi probleme, de o importanță deosebită. O astfel de problemă ar fi posibilele atentate la dreptul fiecăruia la intimitate, prin accesarea neautorizată a unor informații personale sau prin monitorizarea permanentă a spațiilor publice. O altă problemă, de maximă importanță, este reprezentată de asigurarea drepturilor de autor asupra programelor sau asupra informațiilor de pe Internet. Copyright-\x\ (drepturile de autor) este un sistem prin care sunt protejate valorile intelectuale. Copyright-\x\ reprezintă drepturile de proprietate care derivă automat la crearea unei opere, în orice domeniu - literar, muzical, plastic, software etc. Durata de valabilitate a drepturilor de autor variază de la un sistem legislativ Ia altul, dar în general este egală cu durata vieții + 50 ani. în România, conform legii nr. 8/26.03.1996 privind dreptul de autor și drepturile conexe, drepturile de autor sunt valabile pe întreaga durată a vieții autorului, iar după moartea acestuia se transmit prin moștenire, pe o durată de 70 de ani (art.25). Capitolul IX (art. 72-81) din legea nr. 8/26.03.1996 stipulează dispoziții speciale referitoare la programele pe calculator. Conform prevederilor din acest capitol, autorul unui program (indiferent dacă este program de aplicație sau sistem de operare, cod sursă sau cod obiect) are dreptul exclusiv de a realiza sau autoriza reproducerea integrală sau parțială a programului, traducerea, adaptarea, precum și difuzarea originalului sau a copiilor acestuia, sub orice formă, inclusiv închiriere. Utilizatorii autorizați ai programului nu au dreptul de a transmite altor persoane dreptul de utilizare a programului². Toate informațiile pe care un utilizator le dobândește prin studierea 2. Pentru o prezentare detaliată a tuturor aspectelor legate de drepturile de autor asupra programelor pe calculator, studiați Legea copyright-ului pentru toți, Editura „Soluții Informaționale”, București, 1996. 8 NOȚIUNI INTRODUCTIVE și testarea funcționalității unui program nu pot fi utilizate pentru producerea sau comercializarea unui alt program, pe principii fundamental similare. Din păcate, legea copyright-\xhxi nu este întotdeauna respectată, pirateria fiind un fenomen frecvent, în special în țările slab dezvoltate. în multe țări, chiar dacă acestea au semnat convenții internaționale referitoare la respectarea drepturilor de autor, sunt difuzate, fie în formă tipărită, fie în format digital (înregistrate pe CD-uri), copii neautorizate ale unor opere de referință (literare, științifice, muzică sau film). Copierea programelor sau a unor lucrări în format digital este facilă, rapidă și practic imposibil de detectat. Deși creatorii de programe folosesc sisteme de protecție din ce în ce mai sofisticate, există specialiști în „spargerea” acestor sisteme de protecție, denumiți crackerĂ, utilizarea ^^//-ufui fără licență fiind o adevărată epidemie. La ora actuală, legislația și contractele conțin prevederi clare referitoare la modul de utilizare a sq/Z-ului, dar nu există un sistem perfecționat de control al respectării acestor prevederi. Atât în Europa, cât și în S.U.A. se derulează diverse proiecte de dezvoltare a unor sisteme electronice care să permită controlul utilizării autorizate a programelor și informațiilor în format digital. Evoluții viitoare Impactul utilizării calculatoarelor asupra societății s-a dovedit a fi deosebit de profund. în mod evident, informatica joacă un rol esențial în îmbunătățirea situației economice și a calității vieții oricărei națiuni și din acest motiv pentru multe guverne aceasta reprezintă o prioritate națională. Includerea informaticii ca disciplină de studiu în învățământ asigură pregătirea specialiștilor de care este nevoie pentru a aplica ceea ce ne învață istoria ultimelor decenii: soluția supravie- țuirii și a succesului constă în dezvoltarea tehnologiilor informaționale modeme și aplicarea lor în toate domeniile activității umane. întrebări recapitulative 1. Dați exemple de domenii în care este utilizat calculatorul și descrieți modul lui de utilizare! 2. Ce este un robot? Care sunt avantajele utilizării roboților? Scrieți un scurt eseu despre evoluția roboților! Analizați modul în care calculatorul a influențat specificul muncii umane, precum și dinamica structurii ofertelor de pe piața locurilor de muncă! 3. Ce înțelegeți prin Copyright? Este legală utilizarea unui program fără licență? Ce sisteme de protecție a produselor soft ați întâlnit? 4. Descrieți modul în care calculatorul influențează viața voastră personală! 5. Descrieți într-un eseu modul în care calculatorul influențează comunicarea interumană! INFORMATICA 9 2. NOȚIUNEA DE ALGORITM 9 2.1. Ce este un algoritm? Despre algoritmi auzim astăzi din ce în ce mai des, în contexte diferite. Conceptul de algoritm nu este nou. Termenul algoritm derivă din numele unui matematician persan, Abu Ja'far Mohammed ibn Musa al Khowarizm? (cca. 825 e.n.), care a scris o carte cunoscută sub denumirea latină de „Liber algorithmif Matematicienii Evului Mediu înțelegeau prin algoritm o regulă pe baza căreia se efectuau calcule aritmetice. Ulterior, termenul de algoritm a circulat într-un sens restrâns, exclusiv în domeniul matematicii. O dată cu dezvoltarea calculatoarelor cuvântul algoritm a dobândit o semnificație aparte, astfel încât astăzi gândirea algoritmică s-a transformat, dintr-un instrument specific matematicii, într-o modalitate fundamentală de abordare a problemelor în diverse domenii. Un algoritm reprezintă o metodă de rezolvare a problemelor de un anumit tip. A rezolva o problemă înseamnă a obține, pentru anumite date de intrare, rezultatul problemei {date de ieșire): Algoritmul este constituit dintr-o succesiune de operații care descriu, pas cu pas, modul de obținere a datelor de ieșire, plecând de la datele de intrare. Se pot descrie algoritmi pentru rezolvarea problemelor din orice domeniu de activitate. De exemplu, orice rețetă de bucătărie poate fi considerată un algoritm prin care, plecând de la materiile prime, obținem printr-o succesiune finită de operații produsul finit. Exemplul 1 Presupunând că dispunem de un aragaz, o tigaie, 2 ouă, sare și 200 ml ulei, să pregătim ochiuri. „ Date ” de intrare: ouă, ulei, sare. „Date " de ieșire: ochiuri. 1. în traducere exactă, „al Khowarizmi” înseamnă „din orașul Khowarizm”. Astăzi acest oraș se numește Khiva și se găsește în Uzbekistan. 2. Abu Ja'far Mohammed ibn Musa al Khowarizmi este cunoscut și datorită cărții „Kitab al-jabr wa'l muqabala”, o carte de exerciții matematice, din denumirea căreia provine termenul algebră. 10 NOȚIUNEA DE ALGORITM Pas 1: Se pune tigaia pe foc. Pas 2: Se toarnă uleiul în tigaie. Pas 3: Așteptăm până când se încinge uleiul. Pas 4: Spargem cu îndemânare ouăle în tigaie. Pas 5: Așteptăm până când ouăle se rumenesc. Pas 6: Dacă nu ținem regim, adăugăm sare. Observați că am descris o succesiune de pași, prin care, pentru orice „date” de intrare (ulei, sare, ouă), obținem rezultatul dorit (ochiuri). Fiecare pas constă din operații culinare specifice, care se execută în ordinea în care sunt specificate. Exemplul 2 Să analizăm un alt exemplu, cu care sunteți de asemenea familiarizați: să se rezolve o ecuație de forma ax+b=0, cu a, beR. Date de intrare: a, beR Date de ieșire: xeR, soluția ecuației, sau un mesaj adecvat Pas 1: Citește datele de intrare a și b Pas 2: Dacă a^O atunci Scrie Soluția ecuației este x= -b/a altfel Dacă b=0 atunci Scrie Ecuația este nedeterminată altfel Scrie Ecuația este imposibilă Această succesiune de pași rezolvă ecuația de forma specificată, pentru orice valori ale datelor de intrare, prin urmare este un algoritm. La matematică, ați învățat numeroși alți algoritmi, chiar dacă nu i-ați denumit astfel: algoritmul de adunare a două numere, algoritmul de extragere a rădăcinii pătrate dintr-un număr real, algoritmul de determinare a celui mai mare divizor comun a două numere naturale etc. Exerciții 1. Descrieți, punând în evidență succesiunea pașilor, algoritmul de tratare a gripei! 2. Descrieți, punând în evidență succesiunea pașilor, algoritmul de rezolvare a unei ecuații de forma ax²+bx+c=0, cu a, b, c numere reale date. 3. Descrieți, punând în evidență succesiunea pașilor, algoritmul de calcul al mediei semestriale a unui elev la un obiect la care se susține teză. 4. Descrieți, punând în evidență succesiunea pașilor, un algoritm de copiere a unei zone de text dintr-un document Word într-un alt document Word. 5. Descrieți, punând în evidență succesiunea pașilor, algoritmul pe care l-ați aplicat la ultima experiență efectuată în laboratorul de chimie. INFORMATICA 11 2.2. Proprietăți caracteristice ale algoritmilor Exemplele precedente generează în mod firesc două întrebări: • Pentru orice problemă există un algoritm de rezolvare? Răspunsul este NU! Există probleme pentru care se poate demonstra (lucru dificil!) că nu există algoritmi de rezolvare, dar și probleme pentru care nici nu s-a demonstrat că nu admit o metodă de rezolvare algoritmică, dar nici nu s-a descoperit (încă!) soluția algoritmică. • Orice succesiune de pași reprezintă un algoritm? Din nou, răspunsul este NU! Pentru a fi un algoritm, secvența trebuie să îndeplinească trei condiții: 1. Claritate - la fiecare moment, operația care urmează a fi executată este unic determinată, definită și realizabilă (adică poate fi efectuată la momentul respectiv, cu mijloacele disponibile). De exemplu, secvența „Dacă plouă stau acasă sau merg la cinema” nu este clară, deoarece, în cazul în care plouă, operația care se execută nu este unic determinată. Sau să presupunem că dorim să obținem un număr natural, care se poate scrie ca sumă de pătrate. Secvența de mai jos „scrie x²+y²” nu este clară, deoarece nu putem calcula valoarea x²+y², deoarece nu cunoaștem valorile lui x și y. 2. Generalitate (universalitate) - o secvență de pași reprezintă un algoritm de rezolvare a unei probleme dacă obține date de ieșire (rezultate) pentru orice date de intrare specifice problemei. Secvența de pași prezentată în exemplul 2 este generală, deoarece conduce la rezolvarea ecuației ax+b=0 pentru orice valori reale ale coeficienților a și b. Dar, dacă am fi descris o secvență de pași care să rezolve numai ecuația x+2=0, aceasta nu ar fi fost un algoritm! 3. Finitudine - rezultatele problemei se obțin după un număr finit de pași. De exemplu, problema „Să se determine toate zecimalele numărului tP nu are o soluție algoritmică, deoarece ti este un număr irațional, care are o infinitate de zecimale. Dar dacă am enunța problema astfel: „fie n un număr natural dat. Să se determine primele n zecimale ale numărului această problemă admite o soluție algoritmică, deoarece primele n zecimale se pot obține după un număr finit de pași. în concluzie, deși nu putem defini cu rigurozitate noțiunea de algoritm, putem descrie mai detaliat această noțiune astfel : Un algoritm este constituit dintr-o succesiune clara de operații realiza- bile, care au ca scop dbțiperea într-un timp finit a rezultatelor unei probleme, pentru orice set de date de intrareț 1 i 12 NOȚIUNEA DE ALGORITM 2.3. Etapele rezolvării unei probleme Rezolvarea unei probleme constituie un proces complex, care comportă mai multe etape. 1. Analiza problemei în scopul stabilirii datelor de intrare, precum și a rezultatelor pe care trebuie să le obținem prin rezolvarea problemei. 2. Elaborarea unui algoritm de rezolvare a problemei. 3. Implementarea algoritmului într-un limbaj de programare. 4. Verificarea corectitudinii algoritmului propus. Un prim pas constă în testarea programului pe diverse seturi de date de test. Seturile de date de test trebuie elaborate cu atenție, astfel încât să acopere, pe cât posibil, toate variantele de execuție a algoritmului, inclusiv situații de excep- ție, și să verifice dacă fiecare subproblemă a problemei date este rezolvată corect (dacă este posibil, se va testa separat fiecare modul de program). Testarea poate pune în evidență, eventual, omisiuni sau erori de concepție a algoritmilor, dar nu garantează corectitudinea algoritmului. Pentru aceasta ar trebui să testăm algoritmul pe toate seturile posibile de date de intrare, ceea ce este practic imposibil. Din acest motiv, se impune utilizarea unor metode formale de demonstrare a corectitudinii algoritmului, etapă de obicei deosebit de laborioasă, necesitând un aparat matematic complex. 5. Analiza complexității algoritmului. în general, există mai mulți algoritmi de rezolvare a unei probleme date. Pentru a alege cel mai bun algoritm, trebuie să analizăm acești algoritmi în scopul determinării eficienței lor și, pe cât posibil, a optimalității lor. Eficiența unui algoritm se evaluează din două puncte de vedere: 1. din punctul de vedere al spațiului de memorie necesar pentru memorarea valorilor variabilelor care intervin în algoritm (complexitate spațiu); 2. din punctul de vedere al timpului de execuție (complexitate timp). Complexitatea spațiu o vom analiza cu precădere atunci când vom transpune algoritmul într-un limbaj de programare. Pentru a estima complexitatea timp vom presupune că se lucrează pe un calculator „clasic”, în sensul că o singură instrucțiune este executată la un moment dat. Astfel, timpul necesar execuției programului depinde de numărul de operații elementare efectuate de algoritm. Observație Elaborarea algoritmilor nu este un proces liniar, adeseori este necesar să revenim la o anumită etapă și să o repetăm. De exemplu, după ce am demonstrat INFORMATICA 13 corectitudinea algoritmului și am analizat eficiența sa, ne putem pune problema de a optimiza algoritmul sau numai implementarea sa, caz în care trebuie să revenim la cea de a doua etapă, de proiectare a algoritmilor și de scriere a codului, etapă urmată în mod necesar de teste de corectitudine, eliminare a erorilor (Zmg-urilor), demonstrații de corectitudine, teste de determinare a complexității, analiza teoretică a complexității etc. 2.4. Date Orice algoritm lucrează cu date: date de intrare (datele pe care trebuie să le primească un algoritm din exterior), date de ieșire (datele pe care trebuie să le furnizeze algoritmul în exterior), precum și date de manevră (date temporare, necesare algoritmului pentru a obține datele de ieșire pe baza datelor de intrare). Datele cu care lucrează algoritmii pot fi clasificate din mai multe puncte de vedere. O primă clasificare a datelor, în funcție de posibilitatea de a-și modifica valoarea, este: 1. Constante - date care nu își modifică valoarea; de exemplu: 10, 3.14, "sir de caractere", ’A',fals. 2. Variabile - date care își modifică valoarea. O variabilă poate fi referită printr-un nume (o succesiune de litere și cifre, primul caracter fiind obligatoriu literă) și are asociată o valoare. Numele unei variabile nu se schimbă pe parcursul algoritmului, dar valoarea acesteia se poate modifica. De exemplu, pentru rezolvarea ecuației de forma ax+b=0, am utilizat două variabile a și b. Prin operația „Citește datele de intrare a și b”, acestora li se asocia câte o valoare reală, introdusă de la tastatură. Utilizarea acestor două variabile era strict necesară, pentru a respecta generalitatea algoritmului. Dacă am fi utilizat două valori constante (de exemplu, 2 și 3.5), secvența de operații ar fi rezolvat numai ecuația 2x+3.5=0, deci nu ar fi avut utilitate. Observați că la începutul algoritmului am specificat (am declarat) faptul că a și b sunt numere reale. Această declarație este necesară, pentru a cunoaște natura valorilor care pot fi asociate celor două variabile și, ca urmare, operațiile permise cu acestea. Spunem că am declarat tipul variabilei respective. O variabilă poate reține numai valori de tipul declarat. în funcție de valoarea lor, datele pot fi clasificate astfel: 1. Date numerice - au ca valori numere (naturale, întregi sau reale); 2. Date alfabetice - au ca valori caractere sau șiruri de caractere; 3. Date logice - au valoarea adevărat sau fals. 14 NOȚIUNEA DE ALGORITM 2.5. Expresii O expresie este constituită dintr-o succesiune de operanzi, conectați prin operatori. Un operand poate fi o constantă, o variabilă, sau o expresie încadrată între paranteze rotunde. Operatorii desemnează operațiile care se execută asupra operanzilor. Operatorii care pot fi utilizați într-o expresie depind de tipul operanzi- lor (numerici întregi, numerici reali, caractere, șiruri de caractere sau logici). Evaluarea unei expresii presupune calculul valorii expresiei, prin înlocuirea valorilor variabilelor care intervin ca operanzi în expresie și efectuarea operațiilor specificate de operatori. Vom prezenta trei categorii de operatori. Operatori aritmetici Operatorii aritmetici definesc o operație aritmetică și pot fi clasificați astfel: I. operatori aritmetici multiplicativi: * (înmulțire), /(împărțire), % (restul împărțirii întregi). Operatorul de împărțire (/) are un efect diferit, în funcție de tipul operanzilor. Dacă ambii operanzi sunt întregi, se face împărțire întreagă (se obține ca rezultat un număr întreg, care este câtul împărțirii primului operand la cel de-al doilea). Mai exact, fie a și b două variabile întregi. Expresia a/b are ca valoare câtul împărțirii întregi a lui a la b. Dacă, de exemplu, a are valoarea 7 și b are valoarea 2, expresia a/b are valoarea 3. Dacă cel puțin unul dintre operanzi este real, se face împărțire reală (se obține ca rezultat un număr real). De exemplu, dacă a și b sunt două variabile reale, iar a are valoarea 7 și b are valoarea 2, expresia a/b are valoarea 3.5. Operatorul % se poate aplica numai asupra operanzilor întregi. 2. operatori aritmetici aditivi: + (adunare) și - (scădere). Operatorii aritmetici aditivi și multiplicativi sunt binari (acționează asupra a doi operanzi). Operatorii aritmetici se pot aplica numai operanzilor numerici. Rezultatul evaluării unei expresii aritmetice este numeric (întreg sau real, în funcție de operanzi și operatori). Operatori relaționali Operatorii relaționali descriu relația de ordine sau de egalitate dintre cei doi operanzi: < (mai mic), > (mai mare), < (mai mic sau egal), > (mai mare sau egal), = (egal), (diferit). INFORMATICA 15 Operatorii relaționali sunt operatori binari și se pot aplica numai operanzilor numerici, logici (fals < adevărat) și caractere (ordinea caracterelor fiind determinată de codurile lor ASCII³). Valoarea unei expresii relaționale este întotdeauna de tip logic (deci poate fi adevărat sau fals). Operatori logici Operatorii logici definesc o operație logică: negație logică - !; conjuncție logică - și; disjuncție logică - sau. Operatorul ! este unar, operatorii și, sau sunt operatori binari. Efectul acestor operatori este cel uzual, învățat la logică matematică. îl reamintim în tabelul următor: X y ! x x sau y x și y fals fals adevărat fals fals fals adevărat adevărat adevărat fals adevărat fals fals adevărat fals adevărat adevărat fals adevărat adevărat Operatorii logici se pot aplica operanzilor logici. Valoarea unei expresii logice este de tip logic. Greșeli frecvente în scrierea expresiilor 1. O greșeală frecventă în utilizarea operatorilor relaționali este utilizarea înlănțuită a acestora. De exemplu, să presupunem că este necesară o expresie care să aibă valoarea adevărat dacă valorile a trei variabile întregi a, b, c sunt egale. Este greșit să scriem a=b=c. Corect ar fi, de exemplu, a=b și b=c. 2. Frecvent sunt „uitate” paranteze, de exemplu pentru a calcula media aritmetică a variabilelor a și b, este scris a+b/2 în loc de (a+b)/2. 3. O greșeală des întâlnită este omiterea operatorul de înmulțire De exemplu, este scris a+2b în loc de a+2*b. Evaluarea unei expresii în procesul de evaluare a unei expresii se respectă regulile de bază, învățate la matematică (în primul rând se evaluează expresiile dintre parantezele rotunde; apoi se execută operațiile în ordinea priorității lor; dacă există mai multe operații cu aceeași prioritate, se execută în ordine, în funcție de asociativitatea lor). Prioritatea operatorilor este (1 fiind considerată prioritatea maximă): 3. Vezi anexai. 16 NOȚIUNEA DE ALGORITM Prioritate Operatori Simbol Asociativitate 1 Negația logică 1 de la dreapta la stânga 2 Aritmetici multiplicativi *, /, % de la stânga la dreapta 3 Aritmetici aditivi + , - de la stânga la dreapta 4 Relaționali >, =/ de la stânga la dreapta 5 Conjuncție logică Și de la stânga la dreapta 6 Disjuncție logică sau de la stânga la dreapta Exemple 1. Fie x un număr natural. Expresia x%10 are ca valoare restul împărțirii numărului x la 10 (care este de fapt ultima cifră a lui x). 2. Fie n un număr natural. Expresia n*(n+l)/2 reprezintă suma numerelor naturale mai mici sau egale cu n. 3. Să presupunem că în variabila R memorăm raza unui cerc, iar constanta k o aproximăm⁴ la valoarea 3.14. Expresia aritmetică 2 * 3.14 *R are ca valoare lungimea cercului de rază R (cu aproximație). Expresia aritmetică 3.14*R*R are ca valoare aproximativă aria cercului de rază R. 4. Fie x un număr natural. Expresia x<3 are valoarea adevărat dacă x este 0, 1 sau 2 și fals, dacă x^3. 5. Să scriem o expresie logică a cărei valoare să fie adevărat dacă și numai dacă numărul întreg memorat într-o variabilă x este un număr par. Un număr întreg este par dacă el este divizibil cu 2, adică restul împărțirii numărului la 2 este 0. Prin urmare, expresia x%2 = 0 are valoarea adevărat dacă și numai dacă x este par. 6. Să scriem o expresie logică a cărei valoare să fie adevărat dacă și numai dacă valorile întregi ale variabilelor x și y sunt strict pozitive: x>0 și y>0. 2.6. Probleme propuse 1. Să considerăm a, b și c trei variabile întregi, având valorile 4, 6 și respectiv 2. Evaluați expresia (l+2*a/b+a+2*b/3*c) /2+a. 2. Fie n o variabilă întreagă cu valoarea 32 7 35. Evaluați expresia n%10+n/10%10+n/100%10. 4. Numerele iraționale, care au o infinitate de zecimale, nu pot fi reprezentate în memoria unui calculator decât cu aproximație (reținând un număr convenabil de zecimale exacte). INFORMATICA 17 3. Să considerăm a, b și c trei variabile întregi, având valorile 5, 7 și respectiv 8. Evaluați expresia a<=b și b0 C. !x%2=0 și !x^0 b. ! (x%2=0 sau x^0) d. x>0 sau x%2 = l 18 REPREZENTAREA ALGORITMILOR 3. REPREZENTAREA ALGORITMILOR 3.1. Principiile programării structurate Creșterea complexității aplicațiilor a impus la începutul anilor ‘70 apariția unei noi paradigme în programare: programarea structurată. Scopul era de a dezvolta noi tehnici de programare, care să permită dezvoltarea unor programe fiabile, ușor de elaborat în echipă, ușor de depanat, de întreținut și de reutilizat. Un prim principiu al programării structurate este modularizarea. Pentru proiectarea unor aplicații complexe, este necesară descompunerea problemei care trebuie rezolvată în subprobleme relativ independente, pentru fiecare dintre aceste subprobleme scriindu-se module de program mai simple. Fiecare modul¹ efectuează un set de prelucrări specifice și este relativ independent de celelalte module, cu care comunică prin intermediul unui set de parametri, care constituie interfața. Avantajele sunt multiple. Cum la orice firmă se lucrează în echipă, modulele de program pot fi implementate de mai mulți programatori. Modificarea unui modul nu afectează celelalte module. Fiecare modul poate fi implementat, testat, depanat, modificat, independent de celelalte. Un alt principiu fundamental este structurarea datelor și a prelucrărilor. Programatorul are posibilitatea de a-și grupa datele în colecții, organizate după anumite reguli, denumite structuri de date¹ ². Prelucrările asupra datelor sunt structurate separat. Conform teoremei de structură Bohm-Jacopini, orice prelucrare poate fi descrisă prin compunerea a trei structuri fundamentale: structura liniară (secvențială), structura alternativă și structura repetitivă. 3.2. Reprezentarea algoritmilor în pseudocod Pentru ca o secvență de operații să constituie un algoritm, ea trebuie să fie clară, adică la orice moment operația care urmează a fi executată trebuie să fie unic determinată, definită și realizabilă (să poată fi efectuată la momentul respectiv, eu mijloacele disponibile). Apare întrebarea: care sunt operațiile definite, cu ajutorul cărora să putem descrie algoritmi? 1. Proiectarea modulară a aplicațiilor va fi studiată în detaliu în clasa a X-a. 2. în capitolul 10 vom studia câteva structuri de date fundamentale. în clasele a X-a și a Xl-a vom studia și alte structuri de date (de exemplu, stiva, coada, lista). INFORMATICA 19 Un răspuns posibil ar fi: operațiile definite sunt instrucțiunile limbajului de programare X! Este un răspuns acceptabil pentru toți cei care cunosc acest limbaj de programare. Dar pentru ceilalți? Nu putem impune nimănui să învețe un anumit limbaj de programare, numai pentru a înțelege algoritmii pe care îi scriem noi. în plus, experiența celor 5 decenii care s-au scurs de la apariția limbajelor de programare, ne învață că nici un limbaj nu este veșnic, nici unul nu a avut supremația, nici în timp, nici ca număr de utilizatori. Prin urmare, este nevoie de o metodă universală de reprezentare a algoritmilor, ulterior fiecare programator având posibilitatea de a implementa algoritmii în limbajul pe care îl preferă. De-a lungul timpului s-au impus două modalități de reprezentare a algoritmilor: schemele logice și limbajele de tip pseudocod. Schemele logice constituie o metodă de reprezentare grafică, foarte sugestivă, dar cu o serie de dezavantaje: se dă o egală importanță componentelor principale ca și detaliului, prin urmare schemele logice devin deosebit de stufoase și greu de urmărit; pentru aplicațiile mai complexe, când este necesară modularizarea, este practic imposibil de pus în evidență legăturile dintre module în cadrul schemei logice. Din acest motiv, treptat s-a impus o altă metodă de reprezentare a algoritmilor: pseudocodul. Un limbaj de tip pseudocod este un ansamblu de convenții, respectate în mod sistematic, care definesc operațiile permise (denumite și instrucțiuni) pentru reprezentarea algoritmilor. Vom prezenta în continuare un limbaj pseudocod, cu ajutorul căruia vom reprezenta algoritmii. 3.3. Structura secvențială Declararea datelor | variabila tip; La începutul oricărui algoritm, vom preciza datele de intrare, datele de ieșire, eventualele date de manevră, precum și tipul acestora. înainte de a utiliza orice variabilă, o vom declara, precizând numele și tipul ei. O variabilă nu poate fi declarată de mai multe ori în același algoritm. Exemple x real; c caracter; i întreg; Operația de citire | Citește variabila!, variabila₂, . variabilaₙ; 20 REPREZENTAREA ALGORITMILOR Efect: Prin operația de citire (denumită și operație de intrare) se preiau succesiv valori de la tastatură și se asociază, în ordine, variabilelor specificate. Operația de scriere | Scrie expresieₗz expresie₂, . expresieₙ; Efect: Operația de scriere (denumită și operație de ieșire) presupune evaluarea în ordine a expresiilor specificate și afișarea pe ecran a valorilor lor pe aceeași linie. Operația de atribuire I variabila <— expresie; Efect: se evaluează expresia, apoi se atribuie valoarea expresiei variabilei din membrul stâng. Instrucțiune compusă instrucțiune_l instrucțiune_2 instrucțiune_n } Efect: se efectuează în ordine instrucțiunile specificate. Instrucțiunea compusă este utilă atunci când sintaxa permite executarea unei singure instrucțiuni, dar este necesară efectuarea mai multor operații. Observații 1. Orice instrucțiune se termină cu caracterul '; '. 2. Pentru claritate, putem insera într-un algoritm comentarii, mici texte explicative. începutul unui comentariu este marcat de succesiunea de caractere /*, iar sfârșitul comentariului este marcat de * / . Parcurgerea instrucțiunii^^ secvență, în. ordinea INFORMATICA 21 3.4. Aplicații Cub Fie a un număr real, citit de la tastatură, care reprezintă lungimea laturii unui cub. Să se scrie un algoritm care să calculeze și să afișeze volumul și suprafața totală a cubului. Soluție Date de intrare: a real; Date de ieșire: V real; /*volumul cubului */ S real; /*suprafața totală */ Citește a; V<—a*a*a; Scrie "Volumul cubului este ", V; S<—6*a*a; Scrie "Suprafața totală a cubului este ", S; Compus chimic Un grup de cercetători studiază un compus chimic descoperit pe planeta Marte. în urma analizelor efectuate, au dedus că o moleculă din acest compus este formată din nC atomi de carbon, nO atomi de oxigen și nH atomi de hidrogen. Știind că masa atomului de carbon este 12, masa atomului de oxigen este 16, iar masa atomului de hidrogen este 1, să se scrie un algoritm care să calculeze și să afișeze masa moleculară a acestui compus. Soluție Date de intrare: nC natural nO natural nH natural m natural; nO, nH; Date de ieșire: Citește nC, m<-nc*12+nO*16+nH; /*numărul de atomi de carbon */ /*numărul de atomi de oxigen */ /*numărul de atomi de hidrogen */ /*masa moleculară a compusului */ Scrie "Masa moleculară a compusului este ", m; înghețată De ziua lui, Ionel a primit de la bunica S lei și ar vrea să invite Ia înghețată cât mai mulți colegi. Știind că o înghețată costă P lei, să se scrie un algoritm care să calculeze și să afișeze numărul maxim de colegi pe care Ionel îi poate invita și suma de bani care îi mai rămâne lui Ionel. 22 REPREZENTAREA ALGORITMILOR Soluție Date de intrare: S natural; /* suma */ P natural; /* prețul unei înghețate */ Date de ieșire: nrc natural; /* numărul maxim de invitați */ rest natural; /* suma rămasă */ Citește S, P; nrc<-S/(P+l) ;/* P+l pentru că și Ionel mănâncă înghețată */ rest<— S% (P+l) ; Scrie "Numărul maxim de invitati este ”, nrC; Scrie "Suma rămasă este ”, rest; Triunghi Fie x un număr natural format din 5 cifre (x₄x₃x₂x₁x₀). Să se afișeze un triunghi format din cifrele numărului x astfel: - pe prima linie (în vârful triunghiului) se va afla cifra din mijloc (x₂) - pe linia a doua se vor afla cifrele x₃x₂xi - pe a treia linie se vor afla toate cifrele lui x. De exemplu, dacă x=152 8 9, triunghiul va arăta astfel: 2 528 15289 Soluție Problema constă în „spargerea” numărului x în cifre. în acest scop am numerotat cifrele numărului x de la dreapta la stânga începând cu 0, astfel încât numărul cifrei să corespundă puterii corespunzătoare a bazei (în cazul nostru baza 10): x₀ este cifra unităților (deci corespunde lui 10°), Xi este cifra zecilor (deci corespunde puterii 10¹), x₂ este cifra sutelor (corespunde lui IO²) ș.a.m.d. Devine astfel evident că pentru a extrage cifrele numărului x trebuie să efectuăm împărțiri la 10. Pentru a obține ultima cifră din x vom împărți pe x la 10 și vom reține restul în x₀. Eliminăm apoi ultima cifră din x (împărțind pe x la 10, x devine x₄x₃x₂xi) acum Xi a devenit cifra unităților și continuăm extragerea cifrelor numărului x în același mod. Date de intrare: x natural; Date de manevră: xO, xl, x2, x3 naturale; Citește x; x0<—x%10; /* rețin cifra unităților */ x<—x/10; /*elimin cifra unităților */ xl<—x%10; /* rețin cifra zecilor */ x<—x/10; /*elimin cifra zecilor */ x2<—x%10; /* rețin cifra sutelor */ INFORMATICA 23 x<--- x/10; /*elimin cifra sutelor */ x3<---x%10 ; /* rețin cifra miilor */ x<---x/10; /*elimin cifra miilor, în x române cifra zecilor de mii */ Scrie ” ”, x2; Scrie " ", x3,x2,xl; Scrie x,x3,x2,xl,xO; Exercițiu Modificați algoritmul precedent astfel încât să afișeze un triunghi format din cifrele unui număr de 6 cifre. De exemplu pentru 1234 5 6 algoritmul va afișa: 34 2345 123456 Schimb Se introduc de la tastatură numerele reale a și b. Să se interschimbe valorile variabilelor a și b, apoi să se afișeze. Soluție Să ne imaginăm că variabila a este un pahar cu vin alb, iar variabila b un pahar cu vin roșu. Trebuie să schimbăm conținuturile celor două pahare. Singura soluție fără „pierderi” este de a utiliza un pahar auxiliar (variabila aux). Vom turna vinul alb în paharul auxiliar (atribuim variabilei aux valoarea variabilei a). Acum paharul de vin alb este gol, turnăm în el vinul roșu (atribuim variabilei a valoarea variabilei b). Paharul de vin roșu (variabila b) a devenit disponibil, turnăm în el vinul alb din paharul auxiliar (atribuim variabilei b valoarea variabilei aux). Această metodă este denumită sugestiv „regula celor trei pahare”, deși analogia nu este absolut perfectă (când atribuim unei variabile valoarea altei variabile, această valoare se va găsi după atribuire în ambele, în timp ce atunci când turnăm conținutul unui pahar de vin în alt pahar de vin ...). Date de intrare/ieșire: a real; b real; Date de manevră: aux real; Citește a, b; /* 1 */ aux<-a; /* 2 */ a<—b; /* 3 */ b<—aux; /* 4 */ Scrie "a= ", a, "b= ", b; /* 5 */ 24 REPREZENTAREA ALGORITMILOR Pentru a înțelege mai bine acest algoritm să urmărim execuția lui pentru un set particular de date de intrare. în acest scop, am numerotat instrucțiunile de la 1 la 5. De exemplu, să presupunem că de la tastatură se introduc valorile 3 și 7. Linia a b aux Explicație 1 3 7 ? Se citesc de la tastatură valorile 3 și 7 și se atribuie în ordine variabilelor a și b. Variabila aux are deocamdată o valoare necunoscută. 2 3 7 3 Se copiază valoarea variabilei a în variabila aux. 3 7 7 3 Variabilei a i se atribuie valoarea variabilei b. 4 7 3 3 Variabilei b i se atribuie valoarea variabilei aux (în care am „salvat” valoarea inițială a variabilei a). 5 7 3 3 Scriem valorile variabilelor a și b însoțite de mesaje explicative (pe ecran va apărea a= 7 b= 3). 3.5. Probleme propuse 1. Ce va afișa următorul algoritm, dacă se citesc valorile 7 și 23? Date de intrare/ieșire: a natural; b natural; Citește a, b; a<-a+b; b<—a-b; a<—a-b; Scrie "a= ", a, " b= ", b; 2. Ce va afișa următorul algoritm, dacă se citește valoarea 12 34? Date de intrare: a natural; Date de manevră: b natural; Date de ieșire: c natural; Citește a; b<—a%100; a<—a /10 0; c<-b*100+a; Scrie c; 3. Ce valoare va avea variabila a la sfârșitul următoarei secvențe de instrucțiuni? a, b întregi; a <— 3; b <— 7; b <— a+b/2; a <— a-b/2*a; 4. Fie a, b, c și d patru variabile reale. Care dintre următoarele instrucțiuni atribuie variabilei d media aritmetică a valorilor variabilelor a, b și c? a. d (a+b+c) 12.; c. d <--- a+b+c/3; b. d <--- a/3+b/3+c/3; d. d <--- (a+b+c) /4-1; INFORMATICA 25 5. Fie xl, x2, x3, x4, x5 cinci valori reale. Scrieți un algoritm care să folosească o singură variabilă suplimentară pentru a permuta circular valorile celor cinci variabile (adică în final xl să aibă valoarea inițială a variabilei x2, x2 valoarea inițială a variabilei x3, x3 valoarea inițială a variabilei x4, x4 valoarea inițială a variabilei x5, iar x5 valoarea inițială a variabilei xl). 6. Fie a, b și c trei numere reale, care reprezintă lungimile laturilor unui triunghi. Să se scrie un algoritm care să calculeze și să afișeze perimetrul și aria triunghiului. 7. O broască țestoasă parcurge o distanță de D kilometri în H ore. Să se scrie un algoritm care să calculeze și să afișeze viteza cu care se deplasează broasca țestoasă (exprimată în metri/secundă). 8. Doi colegi (Vasilică și Ionică) pleacă simultan din orașele în care locuiesc, unul către celălalt. Știind că distanța dintre cele două orașe este D, că Vasilică merge cu viteza vl, iar Ionică merge cu viteza v2 (D, vl, v2 numere reale), scrieți un algoritm care calculează după cât timp se întâlnesc cei doi colegi și la ce distanță de orașul în care locuiește Vasilică. 9. Fie A și B două puncte în plan, specificate prin coordonatele lor carteziene. Să se scrie un algoritm care să calculeze și să afișeze lungimea segmentului AB. 10. A fost odată un balaur cu 6 capete. într-o zi Făt-Frumos s-a supărat și i-a tăiat un cap. Peste noapte i-au crescut alte 6 capete în loc. Pe același gât! A doua zi, Făt-Frumos i-a tăiat iar un cap, dar peste noapte balaurului i-au crescut în loc alte 6 capete ... și tot așa timp de n zile. în cea de-a (n+l)-a zi, Făt-Frumos s-a plictisit și a plecat acasă! Scrieți un algoritm care citește de la tastatură n, numărul de zile, și care afișează pe ecran câte capete avea balaurul după n zile. De exemplu, pentru n=3, algoritmul va afișa: După 3 zile balaurul are 15 capete. (Olimpiada Județeană pentru Gimnaziu, clasa a V-a, 2002) 3.6. Structura alternativă Daca expresie atunci instrucțiune_l altfel instrucțiune_2 Efect: Se evaluează expresia. Dacă valoarea expresiei este adevărat, atunci se execută instrucțiune_l. Dacă valoarea expresiei este fals, se execută instrucțiune_2. 26 REPREZENTAREA ALGORITMILOR Observații 1. Atât pe ramura atunci, cât și pe ramura altfel este permisă executarea unei singure instrucțiuni. în cazul în care este necesară efectuarea mai multor operații, acestea se grupează într-o singură instrucțiune compusă. 2. Dacă pe ramura altfel nu este necesară efectuarea nici unei operații, această ramură poate lipsi. 3. Instrucțiunea Dacă permite executarea unei singure instrucțiuni, în funcție de valoarea unei expresii, deci permite selectarea condiționată a unei alternative. Această instrucțiune implementează în pseudocodul nostru structura alternativă. 4. Instrucțiune_l și Instrucțiune_2 sunt subordonate instrucțiunii de decizie. în cazul în care o instrucțiune este subordonată unei alte instrucțiuni, aceasta se scrie de obicei indentat față de instrucțiunea care o subordonează. Modul de spațiere sau de scriere pe linii nu este predefinit, dar este important ca modul de redactare să facă programele ușor de urmărit și de întreținut. 3.7. Aplicații * x, dacă x>0 l-x, dacăx<§ Modul Se introduce de la tastatură un număr întreg x. Scrieți un algoritm care calculează și afișează modulul numărului x. Soluție Funcția modul este definită astfel: |x| = Date de intrare: x întreg; Date de ieșire: m întreg; /*modulul */ Citește x; Dacă x<0 atunci —x; altfel m<—x; Scrie "Modulul este ", m; Observație Observați că nu am testat decât condiția x<0. Evident, este suficient. Dacă am pus întrebarea „Moneda a căzut cu stema în sus?” și ni s-a răspuns „Nul”, este inutil să mai întrebăm dacă a căzut cu cealaltă față în sus. INFORMATICA 27 Paritate Se introduce de la tastatură un număr întreg x. Scrieți un algoritm care testează dacă x este un număr par. Soluție Numărul x este par dacă este divizibil cu 2 (adică restul împărțirii lui x la 2 este 0). Date de intrare: x întreg; Date de ieșire: Rezultatul testului Citește x; Dacă x%2=0 atunci Scrie x, ’ este par"; altfel Scrie x, ’ nu este par"; Ecuația de gradul al II-lea Fie o ecuație de gradul al II-lea cu coeficienți reali ax²+bx+c=0 (a/0). Scrieți un algoritm care să rezolve ecuația în mulțimea numerelor reale. Soluție Se calculează mai întâi discriminantul ecuației. Dacă acesta este negativ, ecuația nu are rădăcini reale. Dacă acesta este egal cu 0, ecuația are două rădăcini reale egale (confundate). Dacă discriminantul este mai mare decât 0, ecuația are două rădăcini reale distincte. Date de intrare: a, b, c reale; /* coeficienții ecuației */ Date de manevră: d real; /* discriminantul */ Date de ieșire: Soluția Citește a, b, c; d<—b*b-4*a*c; /* calculam discriminantul */ Dacă d<0 atunci Scrie "Ecuația nu are rădăcini reale"; altfel Dacă d=0 atunci Scrie "xl=x2=", -b/(2*a) ; altfel /*d este >0 */ Scrie "xl=", (-b+^d)/(2*a), "x2=", (-b-^/d) / (2*a) Exercițiu Modificați algoritmul pentru cazul în care ecuația are gradul cel mult II (caz în care a poate fi 0). 28 REPREZENTAREA ALGORITMILOR Funcție Fie x un număr real. Să se calculeze valoarea funcției: F(x)=max {| 2x-l |, 9-x²} Soluție Date de intrare: x real; Date de ieșire: f real; /* F(x) */ Citește x; f <--- 9-x*x; Dacă 2*x-l>=0 atunci {Dacă 2*x-l > f atunci f /* |2x-l|=2x-l */ altfel 2*x-l;} {Dacă 1-2*x > f atunci f /* |2x-l|=l-2x */ Scrie f; <- 1- 2*x;} Sumă Orice sumă de bani S (S>7) poate fi plătită numai cu monede de 3 lei și de 5 lei. Dat fiind S>7, scrieți un algoritm care să determine o modalitate de plată a sumei S numai cu monede de 3 lei și de 5 lei. Soluție Problema cere de fapt să găsim două numere naturale x și y astfel încât S să poată fi scris sub forma S=3*x+5*y. Vom analiza următoarele trei cazuri: 1. S%3 (restul împărțirii lui S la 3) este 0. în acest caz x=S/3, iar y=0. 2. S%3 este 1. Deoarece S>7, vom considera x=S/3-3, și y=2, pentru că S=3*S/3+l=3*(S/3-3)+3*3+l=3*(S/3-3)+10=3*(S/3-3)+5*2. 3. S%3 este 2. în acest caz vom considera x=S/3-l și y=l, deoarece S=3*S/3+2=3*(S/3-1)+3+2=3*(S/3-1)+5. Date de intrare: S natural; Date de ieșire: xᵣ y naturale; Date de manevră: r natural; Citește S; r <- S%3; Daca r=0 atunci {x <— S/3; y <— 0; } altfel Dacă r=l atunci { x <- S/3-3; y <— 2; } altfel { x <- S/3-1; y <- 1;} Scrie S,"=3*",x,"+5*",y; INFORMATICA 29 3.8. Probleme propuse 1. Care este efectul următoarei secvențe de instrucțiuni? a, b, cᵣ x întregi; a<—3; b<—5; —7; Dacă a-b/2<0 atunci x<—1; altfel Dacă a+b-c/2b atunci x<—3; altfel x<— 4; Scrie x; 2. Ce valoare inițială ar putea avea variabila x, astfel încât la sfârșitul execuției următoarei secvențe de instrucțiuni variabila y să aibă valoarea 2? IDacă x>3 atunci Dacă x<7 atunci Dacă x%2=0 atunci y<—1; altfel y<—2; altfel y<—3; altfel y<—4 . 3. Fie a și b două numere întregi. Scrieți un algoritm care să verifice dacă a și b sunt numere consecutive. 4. Fie ecuația cu coeficienți reali ax²+bx+c=0 (a^O). Scrieți un algoritm care, fără a calcula rădăcinile ecuației, să determine natura și semnul acestora. 5. Fie x un număr natural de trei cifre. Scrieți un algoritm care să elimine una dintre cifrele numărului astfel încât numărul de două cifre rămas să fie maxim. 6. Scrieți un algoritm care să citească 3 caractere și să determine câte caractere distincte s-au citit. 7. Fie a și b două unghiuri, ale căror măsuri sunt exprimate în grade, minute și secunde. Să se scrie un algoritm care să calculeze și să afișeze măsura sumei celor două unghiuri. 8. Se citesc de la tastatură a, b și c trei numere reale pozitive. Scrieți un algoritm care să verifice dacă numerele citite pot constitui laturile unui triunghi dreptunghic. în caz afirmativ, calculați și afișați aria triunghiului. 9. Fie x și y două numere reale, citite de la tastatură. Scrieți un algoritm care calculează și afișează valoarea funcției: x + y dacă x, y> 0 f(x,y) = < 2xy max(x, y), dacă x = 0 sau y = 0 fl 1Y1 1 o 2 2^ , altfel yAx y ) 10. Scrieți un algoritm care citește de la trei numere întregi strict pozitive a, b și c, numere cu cel mult trei cifre fiecare. Valoarea variabilei a reprezintă 30 REPREZENTAREA ALGORITMILOR distanța în km dintre orașul A și orașul B, b distanța în km dintre orașul B și orașul C, iar c reprezintă distanța în km dintre orașul C și orașul A. Știind că un călător își planifică o vizită a celor trei orașe pornind din oricare dintre orașele A sau B și ajungând în final în oricare dintre orașele B sau C cu trecere prin cel de-al treilea oraș, să se determine un traseu de lungime minimă care respectă aceste condiții. Algoritmul va afișa cele trei litere corespunzătoare celor trei orașe, în ordinea în care sunt vizitate. Se va alege o metodă cât mai eficientă din punctul de vedere al gestionării memoriei. De exemplu, pentru a=58, b=140, c=125, se va afișa BAC. (Bacalaureat 2002, sesiune specială) 11. Să se scrie un algoritm care să rezolve sistemul de două ecuații de gradul I, cu două necunoscute și coeficienți reali: aix+biy=Ci a₂x+b₂y=c₂ 12. Un elev este declarat promovat la bacalaureat dacă la fiecare dintre cele 5 probe de examen a luat cel puțin nota 5, iar media sa generală este cel puțin 6. Date fiind cele 5 note pe care elevul le-a obținut la bacalaureat, scrieți un algoritm care să verifice dacă elevul a promovat sau nu examenul de bacalaureat. 13. Ionel are HI cm, Gigei are H2 cm, iar Dănuț are H3 cm. Scrieți un algoritm care să afișeze numele celor 3 copii în ordinea crescătoare a înălțimii. 3.9. Structura repetitivă Instrucțiunea repetitivă condiționată anterior I Cât-timp expresie execută instrucțiune Efect: Pas 1: se evaluează expresia; Pas 2: dacă valoarea expresiei este fals, se iese din instrucțiunea cât-timp; dacă valoarea expresiei este adevărat, se execută instrucțiunea, apoi se revine la Pas 1. Observații 1. Instrucțiunea se execută repetat, cât timp valoarea expresiei este adevărat. Pentru ca ciclul să nu fie infinit, este obligatoriu ca instrucțiunea care se execută să modifice cel puțin una dintre variabilele care intervin în expresie, astfel încât aceasta să poată lua valoarea fals. 2. Dacă expresia are de la început valoarea fals, instrucțiunea nu se execută nici măcar o dată. INFORMATICA 31 Instrucțiunea repetitivă condiționată posterior Execută instrucțiune cât-timp expresie; Efect: Pas 1: se execută instrucțiunea; Pas 2: se evaluează expresia; Pas 3: dacă valoarea expresiei este fals se iese din instrucțiunea repetitivă; dacă valoarea expresiei este adevărat, se revine la Pas 1. Observații 1. Instrucțiunea se execută repetat, cât timp valoarea expresiei este adevărat. Pentru ca ciclul să nu fie infinit, este obligatoriu ca instrucțiunea care se execută să modifice cel puțin una dintre variabilele care intervin în expresie, astfel încât aceasta să poată lua valoarea fals. Deoarece evaluarea expresiei se face după execuția instrucțiunii, instrucțiunea se execută cel puțin o dată. 2. Instrucțiunea repetitivă condiționată posterior (Execută cât-timp) poate fi simulată cu ajutorul instrucțiunii repetitive condiționate anterior (Cât-timp) și reciproc. Simularea instrucțiunii Cât-timp cu ajutorul instrucțiunii Execută cât- timp: Dacă expresie atunci Execută instrucțiune cât-timp expresie; Observați că a fost necesară testarea inițială a expresiei deoarece, spre deosebire de instrucțiunea Cât-timp, instrucțiunea Execută cât-timp efectuează o dată instrucțiune înainte de a testa expresia. Simularea instrucțiunii Execută cât-timp cu ajutorul instrucțiunii Cât- timp: instrucțiune; Cât-timp expresie execută instrucțiune Observați că în acest caz a fost necesar să executăm o dată instrucțiunea în afara ciclului. Deducem că nu este necesară existența ambelor instrucțiuni, dar în funcție de problemă, vom alege instrucțiunea repetitivă adecvată, pentru care descrierea algoritmului este mai concisă. 32 REPREZENTAREA ALGORITMILOR Instrucțiunea repetitivă cu număr cunoscut de pași I Pentru contor*-expresie_l, expresie_2 execută instrucțiune Efect: Pas 1: Se evaluează expresie_l. Pas 2: Se atribuie variabilei contor valoarea expresiei expresie_l. Pas 3. Se evaluează expresie_2. Pas 4: Dacă valoarea variabilei contor este mai mare decât valoarea expresiei expresie_2, atunci se iese din instrucțiunea repetitivă. Dacă valoarea variabilei contor este mai mică sau egală cu valoarea expresiei expresie_2, atunci se execută instrucțiune și apoi se incrementează (se mărește cu 1) valoarea variabilei contor, după care se revine la Pas 3. Observații 1. Dacă inițial valoarea expresiei expresie_l este mai mare decât valoarea expresiei_2, instrucțiune nu se execută nici o dată. In caz contrar, și dacă instrucțiune nu modifică valorile variabilelor care intervin în expresie_2, instrucțiune se execută de (expresie_2- expresie_l + l) ori. 2. Instrucțiunea repetitivă cu număr cunoscut de pași poate fi simulată cu ajutorul celorlalte două instrucțiuni repetitive. Cu ajutorul instrucțiunii repetitive condiționată anterior (Cât-timp), instrucți- unea Pentru poate fi simulată astfel: contor <— expresie_l Cât_timp contor expresie_2 execută { instrucțiune; contor <— contor+1; } Cu ajutorul instrucțiunii repetitive condiționată posterior (Execută cât-timp), instrucțiunea Pentru poate fi simulată astfel: contor *- expresie_l Dacă contor expresie_2 atunci Execută { instrucțiune ; contor <— contor+1; } cât-timp contor expresie_2; ' ‘ cdntrolâță de INFORMATICA 33 3.10. Aplicații Secvență 9 Se consideră următorul algoritm descris în pseudocod Date de intrare: n, a, b naturale; Date de ieșire: nr natural; Date de manevră: i natural ; Citește n; /* 1 */ Citește a; /* 2 */ i<---1; nr^O; /* 3 */ Cât_timp i valoarea variabilei n se iese din ciclu și se continuă cu instrucțiunea de pe linia 4. 4 3 256 4 Se afișează valoarea 256. b. Trebuie să transformăm structura repetitivă Pentru într-o structură repetitivă Cât-timp: Date de intrare: n natural; Date de intrare/ieșire: x natural; Date de manevră: i natural; Citește n, x; Cât-timp i valoarea variabilei b se iese din instrucțiunea repetitivă și se continuă cu instrucțiunea de pe linia 5. 3 5 8 2 9 Se afișează valoarea variabilei nr (2). b. Va trebui să simulăm instrucțiunea Pentru cu ajutorul instrucțiunii Execută cât-timp: Date de intrare: Date de ieșire: Date de manevră: Citește a, b; a, b naturale nr natural; i natural; nr <— 0; i <— a; Dacă i < b atunci Execută { Dacă i%2=0 atunci nr nr+1 i <- i + 1; Cât-timp (i^b); Scrie nr; Observați că a fost necesar să testăm separat, înainte de a intra în instrucțiunea repetitivă Execută cât-timp, dacă i0, iar 0 ! =1. Observăm că n ! se obține înmulțind succesiv toate numerele naturale mai mici sau egale cu n. Pentru a calcula acest produs, vom utiliza o variabilă f. Inițial variabila f va fi 1 (pentru că 1 este elementul neutru la înmulțire), apoi vom parcurge numerele natu- rale de la 2 la n, înmulțind succesiv variabila f cu fiecare dintre aceste numere. Date de intrare: n natural; Date de ieșire: f natural; Date de manevră: i natural; Citește n; f <- 1; Pentru i <--- 1, n execută f <- f * i; Scrie f; Exerciții 1. Urmăriți pas cu pas execuția acestui algoritm pentru n=6. 2. Scrieți un algoritm echivalent care să utilizeze instrucțiunea Cât-timp. Putere Fie n un număr natural și x un număr real. Scrieți un algoritm care calculează pe xⁿ. Soluție xⁿ=x*x* . . . *x= (x*x* . . . *x) *x = xⁿ⁻¹*x V Y J v---y---; de n ori de n-1 ori Evident, x°=l. Vom utiliza o variabilă p în care vom calcula puterea. La fiecare pas i (i=l, n) vom înmulți valoarea variabilei p cu x. Date de intrare: n natural; x real; Date de ieșire: p real; Date de manevră: i natural; Citește n, x; n execută p <--- p * x; P <- 1; Pentru i <- 1, Scrie p; 42 REPREZENTAREA ALGORITMILOR Observație Acest algoritm efectuează exact n înmulțiri. Dobândă Să presupunem că dorim să depunem la bancă o sumă S, cu o dobândă anuală de d%. Presupunând că timp de n ani nu intenționăm să scoatem bani din bancă și știind că dobânda se calculează și se cumulează în cont anual, elaborați un algoritm care să determine ce sumă vom avea în cont după n ani. De exemplu, să presupunem că am depus 100 de lei, cu o dobândă de 5%. După 3 ani vom avea 115.7625 lei. Mai exact: Suma Dobânda Total Inițial 100 0 100 După 1 an 100 5 105 După 2 ani 105 5.25 110.25 După 3 ani 110.25 5.5125 115.7625 Soluție Vom simula „trecerea anilor”, calculând după fiecare an dobânda și cumulând-o la suma existentă. n Date de intrare: Date de intrare/ieșire: S Date de manevră: Citește S, n, Pentru i <— 1 Scrie S; natural; d real; real ; natural; d; n execută S <— S+S*d/100; Exercițiu Urmăriți pas cu pas execuția acestui algoritm pentru S=1000, d=10%, n=5. Maxim I. Fie a și b două numere reale, citite de la tastatură. Scrieți un algoritm care determină și afișează pe ecran cea mai mare valoare citită. Soluție Compar valorile celor două variabile citite și o afișez pe cea mai mare: Date de intrare: a real; b real; Date de ieșire: maximul dintre a și b Citește a, b; Dacă a < b atunci Scrie ”max= ", b; altfel Scrie "max= ", a; INFORMATICA 43 O altă soluție, care are avantajul că o vom putea generaliza pentru oricâte elemente, este de a reține maximul într-o variabilă (să o numim max). Inițializăm variabila max cu a (inițial pot considera că a este „cel mai bun”). Apoi compar maximul cu valoarea variabilei b și, dacă max este mai mic, îl schimb. Date de intrare: a real; b real; Date de ieșire: max real; /* maximul dintre a și b */ Citește a, b; maxea; /* inițializare */ Dacă max < b atunci max<-b; Scrie "max= ", max; II. Fie a, b și c trei numere reale, citite de la tastatură. Scrieți un algoritm care determină și afișează cea mai mare valoare citită. Soluție Ideea, utilizată în cea de a doua variantă a algoritmului precedent, o putem utiliza și pentru trei variabile: Date de intrare: a real; b real; c real; Date de ieșire: max real; /* maximul dintre a, b și c */ Citește a, b, o; max<—a; /* inițializare */ Dacă max < b atunci max<—b; /* compar cu b */ Dacă max < c atunci max<—c; /* compar cu c */ Scrie "max= ", max; III. Se citește de la tastatură un număr natural nenul n, apoi se citesc succesiv n valori reale. Scrieți un algoritm care determină și afișează cea mai mare valoare reală citită. Soluție O primă problemă este declararea datelor de intrare: ni se dau n valori reale, numai că de data aceasta n nu este constant, ci variabil (citit de la tastatură). Cum să declarăm un număr variabil de variabile? Nu putem și nici nu este necesar, pentru că nu este nevoie să citim fiecare număr într-o variabilă separată! Vom citi numerele succesiv în aceeași variabilă (să o numim a) și imediat ce le-am citit le vom compara cu elementul maxim. Pentru a intui mai bine algoritmul de calcul al maximului, să ne imaginăm un șir de elevi, care intră în clasă unul câte unul. Am dori ca pe măsură ce intră să reținem care este cel mai înalt. Evident, primul care intră poate fi considerat cel mai înalt (de altfel, este singurul pe care l-am văzut până acum). Când intră pe ușă un nou elev, compar înălțimea lui cu înălțimea celui pe care eu îl consider cel mai înalt de până acum. Dacă noul elev este mai înalt, rețin înălțimea lui ca etalon pentru viitoarele comparații (el este cel mai înalt de până acum). Prin urmare, noi reținem permanent maximul dintre cei intrați deja. 44 REPREZENTAREA ALGORITMILOR Această idee o vom utiliza în continuare: în variabila max vom reține la fiecare moment cea mai mare valoare citită până la momentul respectiv. Date de intrare: n natural; a real; Date de ieșire: max real; /* maximul dintre valorile citite */ Date de manevră: i natural; /*în i reținem câte valori am citit până la un moment dat*/ Citește n; Citește max; /* inițializăm max cu primul element citit */ i<-l; /* i indică numărul de valori citite */ Cât-timp i2 atunci Dacă n%2 =0 atunci prim <— 0; altfel {d <- 3; Cât-timp d^n și prim=l execută Dacă n%d=0 atunci prim=0; altfel d<—d+2; } Dacă prim=l atunci Scrie n, " este prim"; altfel Scrie n, " nu este prim"; 3. La matematică ați demonstrat o teoremă conform căreia dacă un număr nu are nici un divizor până la radicalul său, atunci el este prim. INFORMATICA 49 Exerciții 1. Urmăriți pas cu pas execuția acestui algoritm pentru n=13, n=8 și n=4 9. 2. Modificați algoritmul astfel încât să afișeze toate numerele naturale prime < n. Descompunere în factori primi Fie n un număr natural (n>l), citit de la tastatură. Scrieți un program care să afișeze descompunerea numărului natural n în factori primi. De exemplu, pentru n=720 programul va afișa 2A4*3A2*5A1, ceea ce înseamnă că divizorii primi sunt 2, 3 și 5, având respectiv multiplicitățile 4, 2 și 1. Soluție Vom aplica algoritmul învățat la matematică: considerăm toate numerele naturale începând cu 2. Pentru fiecare număr, verificăm dacă este divizor al lui n. în caz afirmativ, calculăm multiplicitatea acestui divizor în n, împărțind succesiv pe n la divizor și calculând numărul de împărțiri efectuate, după care afișăm atât divizorul găsit, cât și multiplicitatea sa. Procedeul se repetă cât timp n mai are divizori (n>l). Date de intrare: n natural; Date de manevră: d, m naturale; n, m, d naturale; Citește n; d <— 2; Cât-timp n>l execută Dacă n%d=0 atunci /* d divide n */ { /* calculez multiplicitatea lui d în n */ m <— 0 ; Cât-timp n%d=0 execută { m <— m+1; n <— n/d; } Scrie "divizorul ", d," multiplicitatea ", m; } Exerciții 1. Urmăriți pas cu pas execuția acestui algoritm pentru n=2500. 2. Observați că nu am testat nicăieri dacă d este prim. Nu este necesar, deoarece, datorită faptului că atunci când găsim un divizor al lui n, îl împărțim pe n la divizor ori de câte ori este posibil, orice divizor nou găsit este prim. Demonstrați această afirmație prin reducere la absurd. 3. Modificați programul astfel încât să afișeze numai cel mai mare divizor prim. 4. Modificați programul astfel încât să calculeze numărul total de divizori ai lui n. 50 REPREZENTAREA ALGORITMILOR Cel mai mare divizor comun Fie n și m două numere naturale, citite de la tastatură. Scrieți un program care să calculeze și să afișeze c.m.m.d.c. (n, m). Soluție Vom aplica algoritmul lui Euclid, învățat la matematică. Cât timp m^O, împărțim n la m și calculăm restul; la pasul următor împărțitorul devine deîmpărțit, iar restul devine împărțitor. Ultimul rest 0 este c.m.m.d.c. De exemplu, pentru a=4 95 și b=72 0, cel mai mare divizor comun prin algoritmul lui Euclid se obține astfel: Deîmpărțit împărțitor Rest 495 = 720 • 0 + 495 720 = 495 • 1 + 225 495 = 225 • 2+45 225 45 • 5 + 0 => c.m.m.d.c. (495,720) =45 Date de intrare/ieșire: n, m naturale; Date de manevră: rest natural; Citește n, m; /* calculez restul Cât-timp m^O execută { rest<-n%m; */ n<---m; /* împărțitorul devine deîmpărțit */ m<---rest; } /* restul devine împărțitor */ Scrie "cmmdc=" , n; /* ultimul rest diferit de 0 */ Exerciții 1. Urmăriți pas cu pas execuția acestui algoritm pentru n=121 și m=4950. 2. Observați că nu am testat nicăieri dacă inițial n>m. Nu este necesar, deoarece, dacă inițial n ar fi mai mic decât m, după prima executare a instrucțiunii compuse subordonate instrucțiunii Cât-timp valorile variabilelor n și m vor fi interschimbate. 3. Scrieți un algoritm echivalent care să utilizeze instrucțiunea repetitivă Execută cât-timp. 4. Modificați acest algoritm astfel încât să simplifice fracția n/m și să afișeze fracția ireductibilă obținută. 5. Modificați acest algoritm astfel încât să verifice dacă numerele n și m sunt prime între ele. 6. Modificați acest algoritm astfel încât să calculeze c.m.m.m.c.(n, m) (cel mai mic multiplu comun al numerelor n și m). INFORMATICA 51 7. Modificați acest algoritm astfel încât să determine O(n) (indicatorul lui Euler⁴). Prin definiție, O(n) este numărul de numere naturale mai mici decât n, relativ prime cu n. Două numere sunt relativ prime dacă cel mai mare divizor comun al lor este 1. Termen Fibonacci Fie șirul Fibonacci⁵ 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Observați că primii doi termeni sunt egali cu 1, fiecare termen următor fiind egal cu suma celor doi termeni care îl preced. Fie n un număr natural citit de la tastatură. Scrieți un program care afișează cel de-al n-lea termen din șirul Fibonacci. Soluție Observăm că pentru a calcula un termen al șirului Fibonacci avem nevoie de doi termeni precedenți. Vom utiliza trei variabile fO, fl, și f2. în fO și fl vom reține doi termeni Fibonacci consecutivi, iar în f 2 vom calcula termenul următor. Variabilele f 0 și f 1 vor fi inițializate cu 1 (primii doi termeni din șirul Fibonacci). Următorii termeni (de la al doilea până la al n-lea) îi vom calcula succesiv. La fiecare pas i, în f 2 vom calcula al i-Iea termen din șirul Fibonacci (f 2<—f 1 + f 0), apoi ne pregătim pentru pasul următor (f 0<—f 1, f 1<—f 2): Date de intrare: n natural ; Date de manevră: i, fO, fl, f2 naturale; fO <- 1; fl <- 1; f2 1; Citește n; Pentru i<—2, n execută { f2 <— fl+fO; /* calculez termenul curent */ fO <— fl; /* ma deplasez in sir */ fl <- f2; } Scrie "Cel de-al ", n, "-lea termen Fibonacci este: ", f2; Exerciții 1. Urmăriți pas cu pas execuția acestui program pentru n=l 0. 4. Leonhard Euler (1707-1783) a fost unul dintre cei mai prolifici matematicieni din istorie. A scris 866 de lucrări și a câștigat premiul Academiei Franceze de 12 ori. 5. Acest șir a fost introdus în 1202 de către Leonardus filius Bonaccii Pisanus (Leonardo, fiul lui Bonacci Pisanul), pentru rezolvarea următoarei probleme: Să se determine câte perechi de iepuri se vor naște intr-un an, dintr-o singură pereche de iepuri, știind că flecare pereche de iepuri dă naștere lunar la o nouă pereche de iepuri, o pereche devine fertilă în decurs de o lună, iar iepurii nu mor pe parcursul anului. Șirul Fibonacci are multe aplicații, în variate domenii. De exemplu, numerele Fibonacci sunt utilizate în probleme de sortare și căutare sau în strategii de joc. 52 REPREZENTAREA ALGORITMILOR 2. Modificați algoritmul astfel încât să afișeze cel de-al n-lea termen din șirul Lucas⁶. Primii termeni din șirul Lucas sunt 1, 3, 4, 7, 11, 18, 2 9, 4 7,... 3. Modificați algoritmul astfel încât să calculeze suma primilor n termeni din șirul Fibonacci. 4. Modificați algoritmul astfel încât să calculeze cel mai mare termen din șirul Fibonacci, mai mic sau egal cu n. Existență Se citesc de la tastatură două numere naturale nenul n și p, apoi se citesc succesiv n valori întregi. Scrieți un algoritm care să verifice dacă printre cele n valori citite există multipli ai lui p. Soluție Vom citi succesiv cele n valori întregi în aceeași variabilă a. După fiecare citire vom verifica dacă valoarea citită este divizibilă cu p și, în caz afirmativ, vom reține faptul că există un multiplu al lui p. Rezultatul verificării îl vom reține în variabila exista. Inițial valoarea acestei variabile este 0 (deoarece încă nu am descoperit nici un multiplu al lui p). Dacă pe parcursul citirii vom descoperi un multiplu al lui p, variabila exista va primi valoarea 1. Date de intrare: n, p, a naturale; Date de manevră: i, exista naturale; Date de ieșire: Rezultatul testului; Citește n, p; exista <— 0; Pentru i<—1, n execută { Citește a; /* citesc un nou termen */ Dacă a%p=0 atunci /* am descoperit un multiplu */ exista <— 1; } Dacă exista=l atunci Scrie "Exista un multiplu al lui ", p; altfel Scrie "Nu exista un multiplu al lui ", p; Exercițiu 1. Urmăriți pas cu pas execuția acestui algoritm pentru șirul de valori 6, 3, 7, 4, 1, 12, 4, 5. 2. Modificați algoritmul astfel încât să calculeze numărul de multipli ai lui p existenți în șir. 6. Franțois-Edouard-Anatole Lucas (1842-1891), matematician francez cu importante contribuții în teoria numerelor. INFORMATICA 53 Număr divizori primi Se citește de la tastatură un număr natural nenul n, apoi se citesc succesiv n valori întregi. Scrieți un algoritm care să verifice dacă oricare număr dintre cele n citite are un număr impar de divizori primi. Soluție Vom citi succesiv cele n valori în aceeași variabilă x. Pentru fiecare valoare citită vom determina numărul de divizori primi (folosind un algoritm asemănător cu descompunerea în factori primi, numai că în loc să afișăm divizorii primi și multiplicitățile acestora, vom număra divizorii). Rezultatul verificării îl vom reține în variabila oricare. Inițial, această variabilă are valoarea 1 (deoarece încă nu am găsit un număr care să nu aibă un număr impar de divizori primi). Dacă, pe parcursul citirii, vom întâlni un număr cu număr par de divizori primi, variabilei oricare îi vom atribui valoarea 0. Date de intrare: n, x naturale; Date de manevră: i, d, nr, oricare naturale; Date de ieșire: Rezultatul testului; Citește n; oricare <— 1; Pentru i<—1, n execută {Citește x; /* citesc o noua valoare */ nr <— 0; /*numărul de divizori primi ai lui x este inițial 0 */ d <— 2; /*determin divizorii primi ai lui x ★/ Cât-timp x>l execută {Dacă x%d=0 atunci /* am descoperit un divizor */ {nr <— nr+1; /* număr acest divizor prim, apoi îl elimin din x, prin impartiri repetate */ Cât-timp x%d=0 execută x=x/d; } d <— d+1; } /* caut divizori mai departe */ Dacă nr % 2 = 0 atunci oricare <- 0; /* pentru că am găsit o valoare cu număr par de divizori primi */ } Dacă oricare=l atunci Scrie "DA"; altfel Scrie "NU"; Vocale Se citește de la tastatură o propoziție scrisă cu litere mici, terminată cu ’ . '. Scrieți un algoritm care calculează și afișează numărul de vocale din propoziție. 54 REPREZENTAREA ALGORITMILOR Soluție Citim succesiv caracterele din care este constituită propoziția, până la sfârșit, în aceeași variabilă (să o numim c). Pentru fiecare caracter citit, verificăm dacă este vocală (’ a ', ’ e ’, ’ i ’, ’ o ’ sau ’ u') și dacă da, îl numărăm. Date de intrare: c caracter; /*în c vom citi succesiv caracterele din care este constituită propoziția */ Date de ieșire: nr natural; /* numărul de vocale */ nr<—0; /*inițial numărul de vocale citite este 0 */ Execută { Citește c; /*citim un caracter */ Dacă c=’a’ sau c=’e’ sau c='i’ sau c=’o’ sau c='u’ atunci nr<—nr+1; /* c este vocală, o număr */ } cât-timp c ; Scrie "Numărul de vocale este ", nr; 3.11. Probleme propuse 1. Se consideră următoarea secvență de instrucțiuni, scrisă în pseudocod: Date de intrare/ieșire: n, m naturale; Citește n, m; /* n și m sunt diferite de 0 */ Cât-timp n^m execută Dacă n>m atunci n<—n-m; altfel m<—m-n; Scrie n; a. Ce rezultat se scrie pentru n=7 2 și m=18 0? Dar pentru n=30 și m=30? b. Dați exemple de valori ce ar putea fi introduse pentru n și m astfel încât algoritmul să afișeze valoarea 13. c. Care este efectul acestui algoritm? 2. Se consideră următorul algoritm descris în pseudocod: Date de intrare: a, b naturale; Date de ieșire: c natural; Citește a, b; c<—0; Cât_timp a^O și b^O execută {Dacă a%10>b%10 atunci c<—c*10+a%10; altfel c<-c * 10 +b %10; a<—a/10; b<-b/10; } a. Ce valoare va avea variabila c după execuția acestui algoritm dacă valorile citite pentru variabilele a și b sunt 14 624 și, respectiv, 8632? INFORMATICA 55 b. Dacă se citește valoarea 7 382 pentru variabila a, ce valoare am putea introduce pentru variabila b astfel încât valoarea calculată de algoritm în variabila c să fie 2 9 3 8 ? c. Dați exemplu de două numere naturale de cel puțin două cifre, care ar putea fi introduse pentru variabilele a și b astfel încât valoarea calculată de algoritm în variabila c să fie 1? 3. Se consideră următorul algoritm descris în pseudocod: Date de intrare: n natural; Date de ieșire: d natural; Citește n; d<—2; Cât-timp n>l execută Dacă n%d=0 atunci n<—n/d; altfel d<-d+l; Scrie d; a. Ce valoare va fi afișată dacă valoarea citită pentru variabila n este 7 2 0? b. Dați exemplu de valori (cel puțin două) care ar putea fi introduse pentru variabila n, astfel încât valoarea afișată de algoritm să fie 11. c. Care este efectul acestui algoritm ? 4. Se consideră următorul algoritm descris în pseudocod: Date de intrare: n, b naturale; Date de ieșire: x natural ; Date de manevră: p natural ; Citește n, b; /* 20 execută { x<—x + p*(n %10); p<-p*b; n<—n/10; } Scrie x; a. Ce valoare va fi afișată dacă se citesc valorile 1032 și 4? b. Ce valoare trebuie să introducem pentru variabila b astfel încât pentru n=4 07 să se afișeze valoarea 331? c. Care este efectul acestui algoritm ? 5. Se consideră următorul algoritm descris în pseudocod: Date de intrare: a, b naturale; Date de ieșire: x natural; Date de manevră: i natural; Citește a, b; i<-a; x<—0; Cât-timp i<=b execută { x<-x+i; i«-i+l; } Scrie x; a. Ce valoare va fi afișată pe ecran dacă se introduc valorile 1 și 10? 56 REPREZENTAREA ALGORITMILOR b. Ce valori ar putea fi introduse pentru a și b astfel încât programul să afișeze valoarea 22? c. Dați exemplu de valori distincte care ar putea fi introduse astfel încât algoritmul să afișeze valoarea 0. d. Scrieți un algoritm echivalent mai eficient. Doi algoritmi sunt considerați echivalenți dacă pentru orice date de intrare ei produc aceleași rezultate. 6. Care dintre următoarele secvențe de instrucțiuni atribuie variabilei întregi u valoarea primei cifre a numărului natural reprezentat de variabila x ? a. u<—x/10; b. u<—x; Cât-timp u^lO execută u<—u%10; c. u<— x%10; d. Cât-timp x^lO execută x<— x/10; u<—x; 7. Care dintre următoarele secvențe afișează cel mai mare divizor propriu al numărului natural neprim memorat în variabila x? c. d<—2; Cât-timp x%d=0 execută d<-d+l; Scrie x/d; b. d<—2; Cât-timp x%d/0 execută d<—d+1; Scrie x/d; d. d<—2; Execută d<-d+l; cât-timp x%d^0; Scrie x/d; d<— x/2; Cât-timp x%d/0 execută d<—d-1; Scrie d; 8. Ce valoare inițială ar trebui să aibă variabila x astfel încât după execuția următoarei secvențe de instrucțiuni să se afișeze valoarea 64 0? d<—2; Cât-timp d<50 execută { x<—x*d; d<— d*d; } Scrie x; 9. Fie n un număr natural nenul și p un număr prim. Algoritmul următor trebuie să determine multiplicitatea lui p în n. Ce greșeli conține algoritmul? n, p, m naturale; Citește n, p; Cât-timp n%p=0 execută m<—m+1; n<—n/p; Scrie m; 10. Număr perfect Un număr este perfect dacă el este egal cu suma divizorilor săi (exclusiv el însuși). Scrieți un algoritm care să testeze dacă un număr natural dat este perfect. INFORMATICA 57 11. Numere prietene Două numere naturale a și b se numesc prietene dacă a este egal cu suma divizorilor lui b (exclusiv b), iar b este egal cu suma divizorilor lui a (exclusiv a). De exemplu a=22 0 și b=284 sunt prietene. Scrieți un program care să determine primele trei perechi de numere prietene, cu a2. Scrieți un algoritm care să determine cel mai mare număr prim, mai mic decât x și cel mai mic număr prim, mai mare decât x. 13. Palindrom Fie n un număr natural, citit de la tastatură. Scrieți un algoritm care testează dacă n este palindrom (citit de la stânga la dreapta și de la dreapta la stânga este același). De exemplu 1331, 14541 sunt palindroame. 14. Maxim și minim Se citește de la tastatură un număr naturale nenul n, apoi se citesc succesiv n valori naturale. Scrieți un algoritm care să determine și cel mai mare și cel mai mic element din cele citite. 15. Sumă și produs Se citește de la tastatură un număr natural nenul n, apoi se citesc succesiv n valori întregi. Scrieți un algoritm care determină și afișează suma valorilor pare citite și produsul valorilor nenule. 16. Palindrom prim Se citește de la tastatură un număr naturale nenul n, apoi se citesc succesiv n valori naturale. Să se verifice dacă printre valorile citite există un palindrom prim. 17. Cifre nenule Se citește un număr natural nenul n, apoi se citesc succesiv n valori întregi. Să se verifice dacă oricare dintre cele n valori citite are exact 3 cifre nenule. 18. Cifra 0 Scrieți un algoritm care să citească de la tastatură o succesiune de valori naturale, până la citirea valorii -1 și care să determine de câte ori apare cifra 0 în scrierea numerelor citite. 19. Cifra de control Fie n un număr natural, citit de la tastatură. Scrieți un algoritm care calculează și afișează cifra de control a lui n. Cifra de control a unui număr natural se obține calculând suma cifrelor numărului, apoi suma cifrelor sumei ș.a.m.d. până la obținerea unei singure cifre. 58 REPREZENTAREA ALGORITMILOR De exemplu, pentru n=293 calculăm suma cifrelor 2 + 9+3=14. Cum suma nu este formată dintr-o singură cifră, repetăm procedeul: 1 + 4=5. Deci 5 este cifra de control a lui 2 93. 20. Pătrate perfecte Se citește de la tastatură un număr natural n. Scrieți un algoritm eficient care să afișeze toate pătratele perfecte mai mici decât n. 21. Numere piramidale Numerele piramidale se definesc ca fiind sumele parțiale ale șirului pătratelor perfecte 1, 4, 9, 16, 25.... De exemplu, primele 5 numere piramidale sunt 1, 5, 14, 30, 55. Scrieți un algoritm care să afișeze primele n numere piramidale. 22. Fracții Fie n un număr natural nenul. Scrieți un algoritm care să determine numărul de fracții ireductibile care au numitorul și numărătorul din mulțimea {1, 2, ..., n}. De exemplu, pentru n=3, se pot forma fracțiile ireductibile {1/1, 1/2, 1/3, 2/1, 2/3, 3/1, 3/2}, deci algoritmul va afișa valoarea 7. 23. Șir Să considerăm următorul șir definit prin recurență astfel s₀=l, Si=2, s₂=l, iar Sn⁼Sn-i+2*sₙ-₂-sₙ-3 (pentru n>3). Scrieți un algoritm care să afișeze al n-lea termen din acest șir. 24. Medie semestrială Se citesc n, numărul de note la obținute de un elev la informatică pe parcursul semestrului, apoi se citesc cele n note. Se citește apoi nota obținută de elev la teză. Scrieți un algoritm care să calculeze media semestrială a elevului. 25. C.m.m.d.c. Se citește n, un număr natural n nenul, apoi se citesc n valori naturale. Scrieți un algoritm care să calculeze cel mai mare divizor comun al celor n numere citite. 26. Număr Se citește de la tastatură o succesiune de caractere, terminată cu spațiu (’ ’). Scrieți un algoritm care să verifice dacă succesiunea de caractere citită poate fi considerată un număr natural scris în baza 10. Modificați algoritmul astfel încât să testeze dacă succesiunea de caractere citită poate fi considerată un număr real. 27. Cuvinte Se citește de la tastatură o propoziție constituită din cuvinte separate prin unul sau mai multe spații. Sfârșitul propoziției este marcat de întâlnirea caracterului Scrieți un algoritm care determină și afișează numărul de cuvinte din propoziție. INFORMATICA 59 4. EXEMPLE DE IMPLEMENTARE În capitolul precedent, am descris algoritmii în pseudocod, un ansamblu de convenții ușor de înțeles și de utilizat de către oameni. Din păcate, calculatoarele nu „înțeleg” (deocamdată) un astfel de limbaj. Pentru a rezolva o problemă cu ajutorul calculatorului trebuie să transpunem (să implementăm) algoritmul de rezolvare a problemei într-un limbaj de programare. Descrierea unui algoritm într-un limbaj de programare se numește program. Pentru exemplificare, vom implementa în limbajul de programare Pascal și în limbajul de programare C++ trei algoritmi fundamentali, învățați în capitolul precedent. Algoritmul lui Euclid Algoritmul lui Euclid determină cel mai mare divizor comun al două numere naturale. Limbajul Pascal Limbajul C++ j program Euclid; 1 #include var n, m, r: integer; int main() begin { write(’n= ’); readln(n); int n, m, r; write(’m= ’); readln(m); 1 cout«"n= cin>>n; while m <> 0 do | cout«"m= cin>>m; begin I while (m) r:=n mod m; {r=n%m; n: =m ; n=m; m:=r; m=r; } end; cout<<”cmmdc=”<2. 60 EXEMPLE DE IMPLEMENTARE Limbajul Pascal Limbajul C++ program Fibonacci; #include var n, i, fl, f2, f3: integer; int main() begin { write(’n= '); readln(n); int n, i, fl, f2, f3; f2:=l; f3:=l; cout«"n= cin»n; for i:=2 to n do f2=f3=l; begin for (i=2; i<=n; i++) fl:=f2; {fl=f2; f2:=f3; f2=f3; f3:=fl+f2; f3=fl+f2;} end; cout< var n, i: integer; int main() x, p: real; { begin int n, i; write(’n= ’); readln(n); float x, p=l; write(’x= ’); readln(x); " cout«"n= "; cin>>n; p:=l; cout«"x= "; cin»x; for i:=l to n do for (i=l; i<=n; i++) p : =p * x ; p*=x; writeln (p:10:2); cout<l). Regula de reprezentare a numerelor în baza b > / ₍ \ ₍ \ "vFiecare cifră dințr-un număr valorează de b ori mai mult decât cifrajdin dreapta să, ăeci Jcifeeîe spre stângă^ w pozițional puterilor bâzei sistemului de numerație: . Operații de conversie Conversia numerelor din baza 10 în baza b Pentru a converti un b>l), vom face împărțiri succesiv primul pas deîmpărțitul este tiumăr fiecare pas, catul de la < impa Reprezentarea numărului în bază H i inversă obținerii lor. -4 bază b/(bG^ r b^pană când obțmem obține considerând resturile m ordinea Exemplu Pentru a converti n=12 63 ₍i₀₎ în baza 16 vom face împărțiri succesive Ia 16: deîmpărțit cât rest 1263 =16*78 + 15 78 =16* 4+14 4 =16* 0+4 INFORMATICA 63 Considerând resturile în ordine inversă obținem 1263₍io)=4EF₍₁₆₎. Regula de conversica numerelor realedinintervațuliff,):} f Cpnverșia numerelor su^unitare dinbaza 10 jnfr-g„ba^b'(beN, b>L), se realizează prin înmulțiri succesive cu b, până cânți sp-g^țmp p perioadă sau până când partea fracționară a reriilt^tblui’ deînmulțitul este numărul care se conyerie^ej;,;înx’^^ păs, partea fracționară a rezultatului precedent devine deînmulțit. Reprezentarea numărului în baza b se obține cdhșiderâny^fr^ întreagă a rezultatelor în ordinea obținerii lor. -'; 7- ' \ / Exemplu Să convertim n=0,3125₍io) în baza 2: 0,3125 x 2 = 0,625 0,625 x 2 = 1,25 0,25 x 2 = 0,5 0,5 x 2 = 1,0 Am obținut partea fracționară 0, deci 0,3125₍₁₀)=0,0101₍₂). ' Regula de conversie a n^mbrelor Pentru a converti uh număr real din baza 10 în baza b (beN, b>l), se convertesc separat partea întreagă și partea fracționară, conform regulilor anterioare. De exemplu, 12 63, 3125 ₍i₀₎=10011101111,0101 ₍₂₎ Conversia numerelor din baza b în baza 10. Pentru a converti un număr din baza b (beN, b>l) în baza 10 utilizăm dezvoltarea după puterile bazei sistemului de numerație și efectuăm calculele. Exemple 1. 1AF₍₁₆₎=1-16²+A-16+F=431₍₁O) 2. 11001,101₍2)=2⁴+2³+l+2’¹ + 2‘³=25, 625₍i₀₎ . Conversia numerelor din baza b în baza b¹ Conversia numerelor din baza b în baza b' (b, b' eN, b, b' >1) se realizează prin intermediul bazei 10: realizăm conversia din baza b în baza 10, apoi din baza 10 în b'. Conversii între baze puteri ale lui 2 Datorită faptului că, deocamdată, calculatoarele utilizează informații reprezentate în formă binară, sistemul de numerație binar prezintă pentru informaticieni o importanță deosebită. Calculatoarele par a se descurca foarte ușor cu șiruri de cifre binare, dar oamenii se obișnuiesc mai greu. Frecvent, 64 ANEXE informaticienii apelează la conversia șirurilor binare în valori octale sau hexazecimale¹. Din fericire, operațiile de conversie între bazele 2 și 8, respectiv 2 și 16 se realizează mult mai simplu conversiile între două baze oarecare, datorită faptului că atât 8, cât și 16 sunt puteri ale bazei 2. Regula de conversie a numerelor din baza 8(16) în baza 2 Pentru a converti un număr octal (hexazecimal) în binar vom înlocui fiecare cifră numărului cu reprezentarea sa binară pe 3, respectiv 4 poziții. Exemple 1. 168AF{₁₆₎ = 1 0110 1000 1010 1111 ₍₂₎ 2. 75210,231₍₈₎ = 111 101 010 001 000, 010 011011 ₍₂₎ Regula de conversie a numerelor din baza 2 în baza 8(16) Pentru a converti un număr binar în baza 8 (16) vom asocia cifrele binare în grupe de câte 3, respectiv 4 începând de la dreapta spre stânga pentru partea întreagă și de la stânga spre dreapta pentru partea zecimală, completând, eventual, ultimele grupe cu zerouri nesemnificative. Exemple 1. 110 1010 1110 1010 1000 0010, 1111 0000 0001 11 ₍₂₎ = 6AE82, F01C₍₁₆₎ 2. 1 111 001 010 000 110, 110 101 l₍₂₎=171206, 654₍₈₎ . Pentru aceste conversii este util tabelul următor, care conține reprezentarea binară a valorilor {0, 1, ..., 15}: Sistem Sistem Sistem Sistem Sistem Sistem Sistem Sistem zecimal binar zecimal binar zecimal binar zecimal binar 0 0 4 100 8 1000 12 1100 1 1 5 101 9 1001 13 1101 2 10 6 110 10 1010 14 1110 3 11 7 111 11 1011 15 1111 Sistemul de numerație Fibonacci Cu ajutorul termenilor șirului Fibonacci putem defini un sistem de numerație pozițional foarte interesant. Mulțimea simbolurilor care reprezintă cifrele acestui sistem de numerație este {0, 1}, deci baza sistemului de numerație este 2. Regula de reprezentare a numerelor naturale în sistemul de numerație Fibonacci este de a asocia pozițional cifrelor numărului termeni ai șirului Fibonacci, începând cu fi, și nu puteri ale bazei. aₙaₙ-j...ai aₙ ’fₙ + aₙ-i ’fn-i + ••• ai *fi 1. De exemplu, informaticienii exprimă uzual adresele de memorie în hexazecimal, nu ca un șir de 32 de cifre binare. INFORMATICA 65 Pentru ca reprezentarea numerelor naturale în sistemul Fibonacci să fie unică impunem condiția ca oricare două cifre consecutive să nu fie egale cu 1. Condiția este naturală, deoarece o succesiune de forma ...011... poate fi înlocuită cu ...100... . Exerciții 1. Să se efectueze următoarele conversii din baza 10 în baza specificată: a. 5412, 6553 6, 2 5 6, 65535 în baza 16 b. 32 7 68, 32 7 67, 312, 0.317 5 în baza 2 c. 49, 720, 153 în baza 7. 2. Să se efectueze următoarele conversii din baza specificată în baza 10: a. A015, FFFF, 10 0 din baza 16 b. 1000101, 1000000, 111111, 0.1011 din baza 2 c. 3002, 100, 333 din baza 4 . 3. Să se efectueze următoarele conversii între bazele specificate: a. 110101010101 din baza 2 în baza 16 și în baza 8 b. 7 5 6201 din baza 8 în baza 2 c. a09ce3 din baza 16 în baza 2 d. 5 62 din baza 8 în baza 2, 7, 10, 16. 4. Scrieți un algoritm care să citească un număr natural b (29 și x<100 9. a t=s/v. Cei doi colegi se întâlnesc după același interval de timp, în care primul a parcurs distanța dl, iar cel de al doilea distanța D-dl. Obținem un sistem de ecuații prin rezolvarea căruia determinăm dl și t: Date de intrare: vl real; v2 real; D real; Date de ieșire-, dl real; /*distanța parcursă de primul*/ t real; /* timpul după care se întâlnesc */ ; Citește D, vl, v2; : dl<—vl*D/(vl+v2) ; t<—dl/vl; j Scrie "dl= ”, dl, ”t= ”, t; 9. ■ Date de intrare: xA, yA, xB, yB reale;/*coordonatele punctelor*/ • Date de ieșire: L real; /*lungimea segmentului AB*/ Citește xA, yA, xB, yB; L<—(xA-xB)*(xA-xB)+(yA-yB)*(yA-yB); Scrie ”L= ”, L; 10. Să urmărim „evoluția” capetelor balaurului: Moment Nr. capete Explicație Inițial 6 Ziua 1 5 Avea 6 capete, Făt-Frumos i-a tăiat un cap, deci au rămas 5 ț Noaptea 1 11 în locul capului tăiat au crescut 6, deci în total 6+5, iar în locul capului tăiat au crescut 6, deci în total 16 Ziua 2 10 Avea 11 capete, Făt-Frumos i-a tăiat unul, deci au rămas 10 Noaptea 2 16 în locul capului tăiat au crescut 6, deci în total 6+10 Ziua 3 15 Avea 16 capete, Făt-Frumos i-a tăiat unul, deci au rămas 15 Observăm că în ziua n balaurul are 5*n capete. Date de intrare: n natural; . Date de ieșire-, nr natural; /* numărul de capete */ Citește n; nr<-5*n; Scrie "După ", n, " zile balaurul va avea ", nr, " capete"; 68 ANEXE Structura alternativă 1. Valoarea afișată este 3; 2. 5 3. Date de intrare: a, b întregi; Date de ieșire: rezultatul testului Citește a, b; Dacă a-b=l sau b-a=l atunci Scrie "DA"; altfel Scrie "NU”; 4. Date de intrare: a, b, c reale; Date de manevră: s, p, d reale; Date de ieșire: rezultatul testului Citește a, b, c; s<—b/a; p<—c/a; d<—b*b-4*a*c; Dacă d<0 atunci Scrie "Ecuația nu are rădăcini reale”; altfel {Scrie "Ecuația are rădăcini reale.”; Dacă d=0 atunci Scrie "Rădăcinile sunt egale"; altfel Scrie "Rădăcinile sunt distincte"; Dacă p<0 atunci Scrie "Rădăcinile au semne contrare" altfel {Scrie "Rădăcinile sunt "; Dacă s>0 atunci Scrie "pozitive"; altfel Dacă s<0 atunci Scrie "negative"; altfel Scrie "nule"; } } 5. Date de intrare: x natural; Date de manevră: cl, c2, c3 naturale; Citește x; /* extrag cele 3 cifre ale numărului */ c3<—x%10; c2<—x/10%10; c3<— x/100; Dacă cl60 atunci {cs<—cs-60; cm<—1;} cm<—cm+am+bm; Dacă cm>60 atunci { cm<— cm-60; cg<—1; } cg<—cg+ag+bg; Dacă cg>360 atunci cg<—cg-360; Scrie cg, ’ grade ’,cm, ' minute ’, cs, ’ secunde’; 8. Date de intrare: a, b, c reale; Date de ieșire: rezultatul testului și aria Citește a, b, c; Dacă a*a=b*b+c*c atunci Scrie ”Triunghi dreptunghic cu aria ”, b*c/2; altfel Dacă b*b=c*c+a*a atunci Scrie "Triunghi dreptunghic cu aria ", a*c/2; altfel Dacă c*c=b*b+a*a atunci Scrie "Triunghi dreptunghic cu aria ", b*a/2; altfel Scrie "NU formează un triunghi dreptunghic"; 9. Date de intrare: xf y reale; Citește x, y; Dacă x>0 și y>0 atunci Scrie (x+y)/(2*x*y); altfel Dacă x=0 sau y=0 atunci Dacă x>y atunci Scrie x; altfel Scrie y; altfel Scrie (1/x+l/y)*(l/x-l/y+2*x*y+x*x+y*y) ; 10. Conform restricțiilor problemei există doar 3 variante în care pot fi vizitate cele 3 orașe (ABC, ACB, BAC). Vom calcula lungimea fiecărui traseu posibil și vom afișa traseul cel mai scurt. Date de intrare: a, b, c naturale; Citește a, b, c; Dacă a+bb; d. în variabila x se calculează suma numerelor din intervalul [a, b]; calculul acestei valori se poate realiza direct, astfel: IDacâ a^b atunci x<-b*(b+1)/2-a*(a-1)/2; altfel x<—0; 6. d; 7. c, d; 8. 5 . 9. Variabila m nu a fost inițializată cu 0. Ciclul este infinit deoarece se execută numai instrucțiunea m<-m+l; (dacă am fi dorit să se execute și instrucțiunea n<— n/p; ar fi trebuit să scriem {m<—m+1; n<—n/p;}, formând astfel o instrucțiune compusă). 10. Date de intrare: n natural; Date de manevră: d, s naturale; Citește n; s<—1; /*inițializăm suma divizorilor cu 1, pentru că 1 este întotdeauna divizor */ Pentru d<—2, n/2 execută Dacă n%d=0 atunci /* d este divizor al lui n */ s<-s+d; /* îl adunăm la sumă */ Dacă s=n atunci Scrie "Perfect"; altfel Scrie "Nu este perfect"; 72 ANEXE 11. Date de ieșire: a, b naturale; Date de manevră: nr, sa, sb, d naturale; nr<—0; /*numărul de perechi de numere prietene determinate este inițial 0*/ a<—2 ,* Cât-timp nr<3 execută /* nu am obținut încă 3 perechi */ {sa<—1; /* calculez suma divizorilor lui a */ Pentru d<-2, a/2 execută Dacă a%d=0 atunci /* d este divizor al lui a */ sa<—sa+d; /* îl adunăm la sumă */ b^sa; /* b trebuie să fie egal cu suma divizorilor lui a */ Dacă b>a atunci {sb<—1; /* calculez suma divizorilor lui b */ Pentru d<—2, b/2 execută Dacă b%d=0 atunci /*d divizor al lui b*/ sb<—sb+d; /* îl adunăm la sumă */ Dacă a=sb atunci /*am obtinut o pereche de numere prietene*/ {Scrie a, ’ ’, b; /* o afișez */ nr<—nr+1;} /* si o număr */ } a<—a+1; /* caut în continuare */ } } 12. Date de intrare: x natural; Date de ieșire: mare, mic naturale; Date de manevră: d, prim naturale ; Citește x; mare <— x-1; Execută {prim <— 1; /*testez dacă mare este prim */ Dacă mare>2 atunci Dacă mare%2 =0 atunci prim <- 0; altfel {d <- 3; Cât-timp d^mare și prim=l execută Dacă mare%d=0 atunci prim=0; altfel d<— d+2; } Dacă prim/1 atunci /*caut mai departe */ mare <— mare-1; } cât-timp prim=0; INFORMATICA 73 mic <— x+1; Execută {prim <— 1; /*testez dacă mic este prim */ Dacă mic>2 atunci Dacă mic%2 =0 atunci prim <— 0; altfel {d <- 3; Cât-timp darnic și prim=l execută Dacă mic%d=0 atunci prim=0; altfel d<—d+2; } Dacă primul atunci /*caut mai departe */ mic 0 execută { in<—in*10+n%10; n<—n/10; } Dacă sn=in atunci Scrie "DA"; altfel Scrie "NU"; 14. Date de intrare: n natural; a real; Date de manevră: i natural; Date de ieșire: max, min reale; Citește n; /*citesc numărul de valori */ Citește a; /* citesc prima valoare separat, pentru a inițializa maximul și minimul */ min<—a; maxe-a; Pentru i<-2, n execută {Citește a; /*citesc succesiv celelalte n-1 valori */ /*compar valoarea citită cu maximul și minimul */ Dacă maxa atunci min<-a; } ; Scrie min, ¹ ’, max; 74 ANEXE Observați că, dacă valoarea citită a a fost mai mare decât maximul, nu este necesar să o mai comparăm cu minimul. 15. Date de intrare: n natural; a întreg; Date de manevră: i natural; Date de ieșire: s, p întregi; Citește n; /*citesc numărul de valori */ s<—0; /*inițializez suma cu 0, elementul neutru la adunare */ p<—1; /*inițializez produsul cu 1, elementul neutru la înmulțire */ Pentru i<—l,n execută {Citește a; /*citesc succesiv valorile */ Dacă a%2=0 atunci /*valoarea este pară */ s<-s+a; /*o adaug la sumă */ Dacă a/0 atunci /*valoarea este nenulă */ p<-p*a; /*o înmulțesc cu produsul */ } Scrie ”s= ",s," p=”,p; 16. Date de intrare: n, a naturale; Date de manevră: i, exista, prim, r, sa naturale; Date de ieșire: Rezultatul testului Citește n; /*citesc numărul de valori */ ■ exista«-0; /*inițial nu am găsit nici un palindrom prim */ Pentru i<—l,n execută {Citește a; /*citesc succesiv valorile */ prim <— 1; /*testez dacă a este prim */ Dacă a>2 atunci Dacă a%2 =0 atunci prim <- 0; altfel { d <— 3; Cât-timp d^a și prim=l execută Dacă a%d=0 atunci prim=0; altfel d<-d+2; } Dacă prim=l atunci /* testez dacă a este palindrom*/ { sa<—a; /*salvez valoarea inițială a lui a */ r<—0; /* în r voi calcula inversul lui a */ Cât-timp a/0 execută {r<—r*10+a%10; /*lipesc la sfârșitul lui r ultima cifră a lui a*/ a<—a/10;} /*elimin ultima cifră a lui a */ Dacă sa=r atunci /* a este și palindrom */ exista<—1 ; } INFORMATICA 75 IDacâ exista=l atunci Scrie "DA"; altfel Scrie "NU"; 17. Date de intrare: n, a naturale; Date de manevră: iᵣ oricare, nr naturale; Date de ieșire: Rezultatul testului Citește n; /*citesc numărul de valori */ oricare^—1 ; /*inițial consider că toate valorile au proprietatea cerută*/ Pentru i<—l,n execută {Citește a; /*citesc succesiv valorile */ /*extrag cifrele numărului a și le număr pe cele nenule */ nr<-0; Cât-timp a>0 execută {Dacă a%10>0 atunci /*ultima cifră din a e nenulă*/ nr<—nr+1; /* o număr */ a<—a/10; } /*elimin ultima cifră a lui a */ Dacă nr^3 atunci /*am găsit un număr care nu are 3 cifre nenule */ oricare <— 0; } Dacă oricare=l atunci Scrie "DA"; altfel Scrie "NU"; 18 .Voi citi succesiv valorile date și pentru fiecare valoare citită voi extrage cifrele numărând în variabila nrO câte cifre egale cu 0 am obținut. Date de intrare: a natural; Date de ieșire: nrO natural; nr0<—0; /*inițial numărul de zerouri existente este 0*/ Execută { Citește a; /* citesc o valoare */ Dacă a^-1 atunci /*extrag cifrele numărului a și le număr pe cele nule */ Execută {Dacă a%10=0 atunci /*ultima cifră a lui a este 0 */ nr0<—nrO+1; /* o număr */ a<—a/10; }/*elimin ultima cifră a lui a */ cât-timp a>0; } cât-timp a/-l; Scrie nrO; 19 .Vom aplica repetat algoritmul de calcul al sumei cifrelor unui număr: | Date de intrare: n natural; 76 ANEXE Date de ieșirez s natural /*cifra de control*/ Citește n; s<-n/ Cât-timp s>9 execută {s<—0; /*calculez suma cifrelor lui n*/ Cât-timp n>0 execută {s<—s+n%10; n<—n/10; } n<—s; } /*suma calculată devine n*/ Scrie "cifra de control este ”, s; 20. Nu vom parcurge toate numerele naturale mai mici decât n testând la fiecare pas dacă numărul curent este sau nu pătrat perfect, ci vom genera direct pătratele perfecte: Date de intrare: n naturale; Date de manevră: i natural; Citește n; i<-l; Cât-timp i*i'0’ și c<’9’) atunci Este <—fals; } cât-timp c^' Dacă Este=adevărat atunci Scrie "DA"; altfel Scrie "NU"; Singura modificare pe care trebuie să o facem pentru ca algoritmul să verifice dacă secvența este un număr întreg se referă la primul caracter din secvență (care ar putea fi și ' + ’ sau ’ -¹). Pentru ca numărul să fie real acceptăm și un singur caracter punct. 27. Citesc propoziția caracter cu caracter, aceeași variabilă c. Date de intrare: c caracter; Date de ieșire: nr natural; nr<— 0; Execută {Execută Citește c; Cât-timp c=' Dacă c^¹.’ atunci {nr<— nr+1; Cât-timp ’ și c^’. } } Cât-timp c^¹.’; Scrie "nr= ", nr; memorând succesiv caracterele citite în /*numărul de cuvinte*/ /*sar peste spații */ /*începe un cuvânt */ /*îl număr */ /*sar peste cuvânt*/ ’ execută Citește c; INFORMATICA 79 BIBLIOGRAFIE 1. Andonie, Răzvan; Gârbacea, Ilie - Algoritmi fundamentali. O perspectivă C++. Editura Libris, Cluj, 1995. 2. Atanasiu, A. - Cum se scrie un algoritm? Simplu. Editura Agni, București, 1993. 3. Atanasiu, A.; Pin tea, R. - Culegere de probleme Pascal. Editura Petrion, București, 1996. 4. Atanasiu, A. - Probleme distractive de logică. Editura Petrion, București, 2001. 5. Bostan, Gh. - Culegere de probleme de informatică. Editura Lumina, Chișinău, 1996. 6. Cerchez, Em.; Șerban, M. - Informatica. Varianta Pascal. Manual pentru clasa a X-a. Editura Polirom, Iași, 2000. 7. Cerchez, Em. - Informatica. Culegere de probleme pentru liceu. Editura Polirom, Iași, 2002. 8. Cormen, Thomas; Leiserson, Charles; Rivest, Ronald - Introduction to Algorithms. The Massachusetts Institute of Technology, 1990. 9. Livovschi, Leon; Georgescu, Horia - Sinteza și analiza algoritmilor. Editura Științifică și Enciclopedică, București, 1986. 10. Lucanu, Dorel - Bazele proiectării programelor și algoritmilor. Editura Universității „Al. I. Cuza”, Iași, 1996. 11. Mitrana, Victor - Provocarea algoritmilor. Editura Agni, București, 1994. 12. Niculescu, St; Cerchez, Em.; Șerban, M. ș.a. - Bacalaureat și atestat în informatică. Editura L&S Infomat, 2000. 13. S.N.E.E. - Subiecte bacalaureat, 2000-2002. 80 ANEXE CUPRINS 1. NOȚIUNI INTRODUCTIVE.......................................3 1.1. Ce este informatica?..................................3 1.2. Informatica și societatea.............................4 2. NOȚIUNEA DE ALGORITM......................................9 2.1 Ce este un algoritm?...................................9 2.2. Proprietăți caracteristice ale algoritmilor..........11 2.3. Etapele rezolvării unei probleme.....................12 2.4. Date.................................................13 2.5. Expresii.............................................14 2.6. Probleme propuse.....................................16 3. REPREZENTAREA ALGORITMILOR...............................18 3.1. Principiile programării structurate..................18 3.2. Reprezentarea algoritmilor în pseudocod..............18 3.3. Structura secvențială................................19 3.4. Aplicații............................................21 3.5. Probleme propuse.....................................24 3.6. Structura alternativă................................25 3.7. Aplicații............................................26 3.8. Probleme propuse.....................................29 3.9. Structura repetitivă ................................30 3.10. Aplicații...........................................33 3.11. Probleme propuse....................................54 4. EXEMPLE DE IMPLEMENTARE..................................59 Algo ritmul lui Euclid....................................59 Șiru l Fibonacci..........................................59 Pute re................................................. 60 ANEXA 1. SISTEME DE NUMERAȚIE................................61 ANEXA 2. SOLUȚII ȘI INDICAȚII................................66 4.1. Noțiunea de algoritm.................................66 4.2. Reprezentarea algoritmilor...........................66 BIBLIOGRAFIE.................................................79