NU AU AVUT/ NU AU ACCES LA TEHNOLOGIE
· Disciplina INFORMATIC I TIC – pentru gimnaziu
· Disciplinele TIC i INFORMATIC – pentru liceu
2020
· Profesor Ciochin Luisa, Liceul Tehnologic Forestier, Rm. Vâlcea;
· Profesor Cojocaru Nicoleta, Colegiul Naional de Informatic „Matei Basarab”, Rm. Vâlcea;
· Profesor Farcaanu Maria-Antoanela, Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· Profesor Grecea Violeta, Colegiul Naional de Informatic „Matei Basarab”, Rm. Vâlcea;
· Profesor Ianc Simona, Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea;
· Profesor Merlan Doina Narcisa, Colegiul Economic, Rm. Vâlcea;
· Profesor Mlisan Mirela, Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· Profesor Ptru Laureniu, Colegiul Naional „Gib Mihescu”, Drgani;
· Profesor Tricu Algina Elena, Liceul de Arte „Victor Giuleanu”, Rm. Vâlcea;
COORDONATOR:
COLECTIV DE REDACIE:
· Inspector colar general adjunct - profesor Toma Mirela;
· Inspector colar pentru informatic - profesor Merlan Doina Narcisa;
CUPRINS
FIECREI UNITI DE ÎNVMANT ................................................
7
8
9
4.3. Disciplina TEHNOLOGIA INFORMAIILOR I A COMUNICAIILOR (TIC) – pentru liceu ......................................................................................................
12
MATERIALELOR CTRE ELEVI ............................................................
DIN PARTEA ELEVILOR ............................................................................
A 1 – 1. Operatori i operanzi - clasa a V-a .......................................................
16
A 1 – 2. Structuri repetitive întâlnite într-un algoritm - clasa a VI-a .................
19
25
29
ANEXA 2 - Disciplina Informatic – liceu
A 2 – 1. Test de Evaluare. Algoritmi/ Expresii/ Structuri - clasa a IX-a, matematic-informatic ......................................................................................
33
A 2 – 2. Test de Evaluare. Algoritmi/ Expresii/ Structuri - clasa a IX-a, tiinele naturii ....................................................................................................
34
A 2 – 3. Vector de frecven/ vector caracteristic - clasa a IX-a, matematic-informatic intensiv informatic .........................................................................
35
A 2 – 4. Prelucrri ale secvenelor de elemente dintr-un vector - clasa a IX-a, matematic-informatic intensiv informatic; clasa a X-a matematic-informatic ..........................................................................................................
39
A 2 – 5. Sume pariale în vectori - clasa a IX-a, matematic-informatic/ matematic-informatic intensiv informatic .....................................................
43
A 2 – 6. Vectori caracteristici/de apariii i vectori de frecven –
clasa a IX-a, matematic-informatic/ matematic-informatic intensiv informatic ..........................................................................................................
46
A 2 – 7. Recursivitatea - clasa a XI-a, matematic-informatic, clasa a X-a matematic-informatic intensiv informatic .....................................................
52
clasa a X-a matematic-informatic intensiv informatic ..................................
56
A 2 – 9. Divide et Impera. Aplicaii cu vectori - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic .................................
58
clasa a X-a matematic-informatic intensiv informatic ..................................
68
A 2 – 11. Metoda Backtracking. Probleme rezolvate - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic .............
82
matematic-informatic intensiv informatic ....................................................
A 2 – 13. Aplicaii cu arbori - clasa a XI-a, matematic-informatic/
matematic-informatic intensiv informatic ....................................................
108
A 2 – 14. Arbore parial de cost minim - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic ................................
112
A 2 – 15. Fi de lucru Arbori - clasa a XI-a, matematic-informatic/
matematic-informatic intensiv informatic .....................................................
116
A 2 – 16. Tem vectori de tai - clasa a XI-a, matematic-informatic/
matematic-informatic intensiv informatic .....................................................
A 2 – 17. Test arbori binari - clasa a XI-a, matematic-informatic/
matematic-informatic intensiv informatic .....................................................
A 2 – 18. Variante bacalaureat 2009 informatic intensiv C++. Rezolvri grafuri neorientate - clasa a XII-a, matematic-informatic, clasa a XII-a matematic-informatic intensiv informatic (pregtire bacalaureat) ................
129
A 2 – 19. Model subiect bacalaureat 2019. Rezolvri i explicaii -
clasa a XII-a, matematic-informatic, clasa a XII-a matematic-informatic intensiv informatic (pregtire bacalaureat) .......................................................
138
comunicaiilor (TIC) – liceu
161
A 3 – 2. Test de evaluare reeaua Internet - clasa a IX-a ...................................
169
A 3 – 3. Baze de date. Diagrama „entiti-relaii“ (ERD) - clasa a X-a ............
173
A 3 – 4. Baze de date Microsoft Access - clasa a X-a .......................................
182
A 3 – 5. Test de evaluare baze de date Microsoft Access - clasa a X-a ............
203
A 3 – 6. Baze de date. Maparea ERD-ului - clasa a XI-a ..................................
206
A 3 – 7. Suport didactic competene digitale - clasa a XII-a .............................
210
A 3 – 8. Fi de lucru competene digitale - clasa a XII-a .................................
217
I. ARGUMENT
Având în vedere faptul c o parte din elevii/cadrele didactice din învmântul preuniversitar nu au avut/nu au acces la tehnologie în perioada 11 martie – 12 iunie 2020, prezentul ghid reprezint o modalitate de a veni în sprijinul acestora cu instrumente de lucru i resurse educaionale în vederea reducerii decalajului între ei i elevii care au avut acces la învarea on-line.
Un alt aspect avut în vedere la elaborarea ghidului metodologic îl constituie finalizarea anului colar 2019-2020 prin încheierea situaiei colare pentru toi elevii.
Ghidul conine etapele care trebuie parcurse de ctre unitile de învmânt i cadrele didactice în vederea finalizrii anului colar.
II. IDENTIFICAREA GRUPULUI INT
LA NIVELUL FIECREI UNITI DE ÎNVMANT
Grupul int îl constituie elevii care nu au avut/nu au acces la tehnologie.
III. ANALIZA DE NEVOI
Identificarea mijloacelor de comunicare cu elevii (telefon, pot, voluntari din cadrul unitilor de învmânt, din cadrul ONG-urilor, al autoritilor locale etc.).
Identificarea coninuturilor care nu au fost parcurse de elevii care nu au putut participa la învmântul on-line în perioada 11 martie - 12 iunie 2020, pentru fiecare disciplin/ modul, respectiv pentru fiecare nivel/ clas.
Identificarea instrumentelor de lucru i a resurselor educaionale de care dispune unitatea de învmânt, pentru fiecare disciplin/ modul, respectiv pentru fiecare nivel/ clas.
Identificarea elevilor cu CES integrai în învmântul de mas.
IV. ELABORAREA I UTILIZAREA RESURSELOR EDUCAIONALE
Resursele educaionale vor fi elaborate din materia parcurs on-line, cu ajutorul instrumentelor i platformelor specifice, în perioada 11 martie - 12 iunie 2020, de ctre elevii care au avut acces la tehnologie.
Programa pentru disciplina Informatic i TIC pentru clasele V-VIII identific un set relevant de competene generale i specifice pentru societatea actual, oferind activiti de învare, coninuturi i sugestii metodologice utile pentru realizarea profilului de formare al absolventului de gimnaziu, conform descriptivului competenei digitale.
Pentru disciplina Informatic, programele colare în vigoare evideniaz atât aspectul teoretic, de analiz a problemelor i de proiectare a algoritmilor de rezolvare (specific orelor desfurate în sala de clas, fr tehnologie/ calculator), cât i aspectul practic, de elaborare efectiv a programelor/ aplicaiilor software folosind un anumit mediu (limbaj) de programare (specific orelor desfurate în laboratorul de informatic, utilizând tehnologia/ calculatorul).
Din nota de prezentare a programelor colare în vigoare pentru disciplina Tehnologia informaiei i a comunicaiilor (TIC) se desprinde necesitatea utilizrii tehnologiei/ a calculatorului pe parcursul orelor de instruire, atât individual, cât i în echipe/ grupe de lucru, în scopul realizrii de proiecte/ produse software care s rspund cerinelor specifice domeniului de pregtire/ specializrii elevului.
Elevii claselor a XII-a vor susine examenul naional de bacalaureat, astfel:
· la disciplina TIC – proba de Evaluare a competenelor digitale (proba D) – toate profilurile i specializrile (prob obligatorie);
· la disciplina Informatic – proba la alegere a profilului i specializrii (proba E. d - prob scris) – pentru elevii de la clasele de tiinele naturii, matematic-informatic, matematic-informatic intensiv - Informatic (prob la alegere).
Este clar faptul c, la disciplinele Tehnologia informaiei i a comunicaiilor (TIC), cât i la Informatic (pentru cei de profil), instruirea lor, acas, on-line, sau la coal, se va axa pe pregtirea acestor probe ale examenului de bacalaureat.
În acest sens, pentru realizarea materialelor necesare, profesorul poate folosi subiectele propuse în anii anteriori la probele mai sus menionate, precum i testele de antrenament pentru Bacalaureat 2020:
Se va pune accentul pe pregtirea teoretic, în scopul asimilrii i fixrii noilor noiuni, precum i în scopul pregtirii elevului pentru recuperarea orelor de laborator (pregtirea practic), atunci când va avea acces la tehnologie/ calculator.
O surs de materiale educaionale pentru profesori i elevi o reprezint resursele educaionale deschise (RED) postate pe site-urile inspectoratelor colare. Acestea sunt mijloace de învare adaptate la nevoile specifice ale procesului instructiv-educativ. Din aceast categorie fac parte diferite tipuri de materiale de învare, suporturi de curs, proiecte, experimente i demonstraii, programe colare, ghiduri pentru profesori sau alte materiale educaionale.
4.1. Disciplina INFORMATIC I TIC – pentru gimnaziu
În pregtirea materialelor necesare pentru clasele a V-a, a VI-a i a VII-a, profesorul poate folosi manualele digitale puse la dispoziie de Ministerul Educaiei i Cercetrii pe site-ul cu adresa https://manuale.edu.ro/manuale :
Pentru a veni în sprijinul profesorului, acest ghid îi pune la dispoziie modele de fie de documentare, fie de lucru, fie/teste de evaluare/autoevaluare etc.
Materiale realizate de cadrele didactice din judeul Vâlcea, pentru disciplina Informatic i TIC – gimnaziu (ANEXA 1):
· OPERATORI I OPERANZI - clasa a V-a, material realizat de profesor Farcaanu Maria-Antoanela, de la Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· STRUCTURI REPETITIVE ÎNTÂLNITE ÎNTR-UN ALGORITM - clasa a VI-a, material realizat de profesor Grecea Violeta, de la Colegiul Naional de Informatic „Matei Basarab”, Rm. Vâlcea;
· REELE DE CALCULATOARE - clasa a VI-a, material realizat de profesor Tricu Algina Elena, de la Liceul de Arte „Victor Giuleanu”, Rm. Vâlcea;
· TEST INTERNET - clasa a VI-a, material realizat de profesor Tricu Algina Elena, de la Liceul de Arte „Victor Giuleanu”, Rm. Vâlcea.
4.2. Disciplina INFORMATIC – pentru liceu
Aceast disciplin este prevzut în planul cadru pentru clasele de matematic-informatic, atât intensiv cât i neintensiv (difer numrul de ore pe sptmân i evident c i între coninuturi apar unele diferene), dar i pentru clasele de tiine ale naturii.
· PROGRAME COLARE – INFORMATIC, clasa a IX-a , ciclul inferior al liceului, Filiera teoretic, profil real, specializrile: Matematic-informatic, tiinele naturii, Filiera vocaional, profil militar, specializarea: Matematic-informatic;
· PROGRAME COLARE – INFORMATIC, clasa a IX-a , ciclul inferior al liceului, Filiera teoretic, profil real, specializarea: Matematic-informatic intensiv informatic, Filiera vocaional, profil militar, specializarea: Matematic-informatic intensiv informatic;
· PROGRAME COLARE – INFORMATIC, clasa a X-a , ciclul inferior al liceului, Filiera teoretic, profil real, specializrile: Matematic-informatic, tiinele naturii, Filiera vocaional, profil militar, specializarea: Matematic-informatic;
· PROGRAME COLARE – INFORMATIC, clasa a X-a , ciclul inferior al liceului, Filiera teoretic, profil real, specializarea: Matematic-informatic intensiv informatic, Filiera vocaional, profil militar, specializarea: Matematic-informatic intensiv informatic;
· PROGRAME COLARE – INFORMATIC, clasa a XI-a , ciclul superior al liceului, Filiera teoretic, profil real, specializrile: Matematic-informatic, tiinele naturii, Filiera vocaional, profil militar, specializarea: Matematic-informatic;
· PROGRAME COLARE – INFORMATIC, clasa a XI-a , ciclul superior al liceului, Filiera teoretic, profil real, specializarea: Matematic-informatic intensiv informatic, Filiera vocaional, profil militar, specializarea: Matematic-informatic intensiv informatic;
· PROGRAME COLARE – INFORMATIC, clasa a XII-a , ciclul superior al liceului, Filiera teoretic, profil real, specializrile: Matematic-informatic, tiinele naturii, Filiera vocaional, profil militar, specializarea: Matematic-informatic;
· PROGRAME COLARE – INFORMATIC, clasa a XII-a , ciclul superior al liceului, Filiera teoretic, profil real, specializarea: Matematic-informatic intensiv informatic, Filiera vocaional, profil militar, specializarea: Matematic-informatic intensiv informatic.
Pentru clasele cu specializarea matematic-informatic i cele cu specializarea matematic-informatic intensiv informatic, coninuturile din programele colare sunt asemntoare, diferena fcându-se prin parcurgerea materiei, mai „repede” la clasele de matematic-informatic intensiv informatic, datorit numrului de ore mai mare (în general, sunt 3 ore în plus, care se desfoar în laboratorul de informatic, pe grupe de 10-15 elevi).
Fiele de lucru sau de evaluare/ autoevaluare i testele care sunt folosite la una din specializrile precizate mai sus, în anumite situaii pot fi folosite i pentru celelalte specializri, profesorul de la clas fiind cel care poate stabili, în funcie de program, de materia parcurs, de nivelul i caracteristicile grupului de elevi, care resurse educaionale sunt potrivite pentru elevii si.
Pentru a veni în sprijinul profesorului, acest ghid îi pune la dispoziie modele de fie de documentare, fie de lucru, fie/teste de evaluare/autoevaluare etc. pentru disciplina Informatic, structurate astfel (ANEXA 2):
· TEST DE EVALUARE. ALGORITMI/ EXPRESII/ STRUCTURI - clasa a IX-a, matematic-informatic, material realizat de profesor Catarag tefania Issabella, de la Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea;
· TEST DE EVALUARE. ALGORITMI/ EXPRESII/ STRUCTURI - clasa a IX-a, tiinele naturii, material realizat de profesor Catarag tefania Issabella, de la Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea;
· VECTOR DE FRECVEN/ VECTOR CARACTERISTIC - clasa a IX-a, matematic-informatic intensiv informatic, material realizat de profesor Cojocaru Nicoleta, de la Colegiul Naional de Informatic „Matei Basarab”, Rm. Vâlcea;
· PRELUCRRI ALE SECVENELOR DE ELEMENTE DINTR-UN VECTOR - clasa a IX-a, matematic-informatic intensiv informatic; clasa a X-a, matematic-informatic, material realizat de profesor Ianc Simona, de la Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea;
· SUME PARIALE ÎN VECTORI - clasa a IX-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Ianc Simona, de la Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea;
· VECTORI CARACTERISTICI/ DE APARIII I VECTORI DE FRECVEN - clasa a IX-a, matematic-informatic, intensiv informatic, material realizat de profesor Ianc Simona, de la Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea;
· RECURSIVITATEA - clasa a XI-a, matematic - informatic; clasa a X-a, matematic-informatic intensiv informatic, material realizat de profesor Ptru Laureniu, de la Colegiul Naional „Gib Mihescu”, Drgani;
· TEST ERECURSIVITATE - clasa a XI-a, matematic-informatic; clasa a X-a, matematic-informatic intensiv informatic, material realizat de profesor Ptru Laureniu, de la Colegiul Naional „Gib Mihescu”, Drgani;
· DIVIDE ET IMPERA. APLICAII CU VECTORI - clasa a XI-a, matematic-informatic; clasa a X-a, matematic-informatic intensiv informatic, material realizat de profesor Merlan Doina Narcisa, de la Colegiul Economic, Rm. Vâlcea;
· METODA GREEDY – clasa a XI-a, matematic-informatic intensiv informatic, material realizat de profesor Catarag tefania Issabella, de la Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea;
· METODA BACKTRACKING. PROBLEME REZOLVATE - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Merlan Doina Narcisa, de la Colegiul Economic, Rm. Vâlcea;
· CREAREA I PARCURGEREA LISTELOR LINIARE ALOCATE DINAMIC ( lecie video .mp4) - clasa a XI-a, matematic-informatic intensiv informatic, material realizat de profesor Mlisan Mirela, de la Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· ARBORII - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Farcaanu Maria Antoanela, de la Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· APLICAII CU ARBORI - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Farcaanu Maria Antoanela, de la Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· ARBORE PARIAL DE COST MINIM - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Farcaanu Maria Antoanela, de la Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· FI DE LUCRU ARBORI - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Farcaanu Maria Antoanela, de la Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· TEM VECTORI DE TAI - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Farcaanu Maria Antoanela, de la Colegiul Naional „Mircea cel Btrân”, Rm. Vâlcea;
· TEST ARBORI BINARI - clasa a XI-a, matematic-informatic/ matematic-informatic intensiv informatic, material realizat de profesor Merlan Doina Narcisa, de la Colegiul Economic, Rm. Vâlcea;
· VARIANTE BACALAUREAT 2009 INFORMATIC INTENSIV C++. REZOLVRI GRAFURI NEORIENTATE - clasa a XII-a, matematic-informatic intensiv informatic (pregtire pentru bacalaureat), material realizat de profesor Merlan Doina Narcisa, de la Colegiul Economic, Rm. Vâlcea;
· MODEL SUBIECT BACALAUREAT 2019 . REZOLVRI I EXPLICAII - clasa a XII-a, matematic-informatic (pregtire pentru bacalaureat), material realizat de profesor Merlan Doina Narcisa, de la Colegiul Economic, Rm. Vâlcea.
4.3. Disciplina TEHNOLOGIA INFORMAIILOR I A
COMUNICAIILOR (TIC) – pentru liceu
Aceast disciplin este prevzut în planul cadru pentru toate clasele de liceu, indiferent de profil, specializare sau domeniu de pregtire. Coninuturile din programele colare pentru clasele a IX-a i a X-a sunt comune multor specializri, acestea fiind baza pentru programa probei de evaluare a competenelor digitale din cadrul examenului de bacalaureat.
· STRUCTURA REELEI INTERNET – clasa a IX-a, filiera tehnologic, toate profilurile i specializrile, material realizat de Ciochin Luisa, de la Liceul Tehnologic Forestier, Rm. Vâlcea;
· TEST DE EVALUARE REEAUA INTERNET - clasa a IX-a, filiera tehnologic, toate profilurile i specializrile, material realizat de profesor Ciochin Luisa, de la Liceul Tehnologic Forestier, Rm. Vâlcea;
· BAZE DE DATE. DIAGRAMA ENTITI-RELAII (ERD) - clasa a X-a, filiera tehnologic, toate profilurile i specializrile, material realizat de profesor Merlan Doina Narcisa, de la Colegiul Economic, Rm. Vâlcea;
· BAZE DE DATE M ICROSOFT ACCESS ( arhiv .rar) - clasa a X-a, filiera teoretic, toate profilurile i specializrile, material realizat de profesor Cojocaru Nicoleta, de la Colegiul Naional de Informatic „Matei Basarab”, Rm. Vâlcea;
· TEST DE EVALUARE BAZE DE DATE MICROSOFT ACCESS - clasa a X-a, filiera teoretic, profil real, filiera vocaional, profil artistic, material realizat de profesor Tricu Algina Elena, de la Liceul de Arte „Victor Giuleanu”, Rm. Vâlcea;
· BAZE DE DATE. MAPAREA ERD-U LUI - clasa a XI-a, filiera tehnologic, toate profilurile i specializrile, material realizat de profesor Merlan Doina Narcisa, de la Colegiul Economic, Rm. Vâlcea;
· SUPORT DIDACTIC COMPETENE DIGITALE - clasa a XII-a, filiera tehnologic, toate profilurile i specializrile, material realizat de profesor Ciochin Luisa, de la Liceul Tehnologic Forestier, Rm. Vâlcea;
· FI DE LUCRU COMPETENE DIGITALE – clasa a XII-a, filiera tehnologic, toate profilurile i specializrile, material realizat de profesor Ciochin Luisa, de la Liceul Tehnologic Forestier, Rm. Vâlcea.
V. MODALITI DE COMUNICARE I TRANSMITERE A
MATERIALELOR CTRE ELEVI
Resursele educaionale pot fi puse la dispoziia elevilor prin pot sau prin intermediul voluntarilor din cadrul unitilor de învmânt, ONG-urilor, autoritilor locale, etc.).
Transmiterea resurselor educaionale se face periodic(cel puin o dat pe sptmân).
VI. MODALITI DE ASIGURARE A FEEDBACK-ULUI
DIN PARTEA ELEVILOR
Colectarea fielor de lucru, fielor/testelor de evaluare/autoevaluare se face la nivelul unitii de învmânt de ctre persoanele implicate în transmiterea acestora, iar coala asigur transmiterea acestora ctre cadrele didactice spre evaluare i oferirea feedback-ului ctre elevi.
ANEXA 1
ANEXA 1 – 1
OPERATORI I OPERANZI
· Clasa a V-a
Profesor Farcaanu Maria-Antoanela
FORMULA este expresia format din OPERATORI i OPERANZI.
OPERANZII exprim valorile sau variabilele care vor participa la calculul formulei.
OPERATORII sunt simboluri care redau „aciunile” ce vor avea loc între operanzi.
Operatorii se împart în mai multe grupe:
· Operatori aritmetici:
a / b
a % b
Variabilei din stânga îi este atribuit valoarea variabilei din dreapta
a = b
a = b
· Operatorii de relaie:
a < = b
a < =9
> =
a > = b
x > = 10
· Operatorii logici:
APLICAII REZOLVATE:
1) 10 – 7 % 3 * 2 = 10 – 1 * 2 = 10 – 2 = 8
2) 15 / 7 – 8 % ( 3 – 1 ) + 10 = 2 – 8 % 2 + 10 = 2 – 0 + 10 = 12
3) ( 24 % 3 / 5 + 1) * 7 / 3 = ( 8 / 5 + 1 ) * 7 / 3 = ( 1 + 1 ) * 7 / 3 = 2 * 7 / 3 = 14 / 3 = 4
4) 100 – ( 25 / 5 + 7 ) % 10 * 2 = 100 – ( 5 + 7 ) % 10 * 2 = 100 – 12 % 10 * 2 =
= 100 – 2 * 2 = 100 – 4 = 96
5) 14 * ( 5 % 3 – 1 ) + 27 / 9 = 14 * (2 – 1 ) + 3 = 14 + 3 = 17
· Clasa a VI-a
Profesor Grecea Violeta
Într-un algoritm, întâlnim urmtoarele tipuri de structuri:
Structurile repetitive ne permit s repetm un grup de instruciuni!
STRUCTURA REPETITIV CU NUMR CUNOSCUT DE PAI
Determin executarea unui grup de instruciuni de un numr precizat de ori.
Exemplu:
Un personaj dintr-un joc va sri de 10 ori în sus. Al doilea personaj va bate de 3 ori din palme. Repetarea aciunii (srit în sus, btut din palme) se realizeaz cu ajutorul unor instruciuni repetitive cu numr cunoscut de pai.
· Sintaxa în pseudocod a unei structuri repetitive cu numr cunoscut de pai
În limbajul pseudocod (limbaj natural de descriere a algoritmilor), structura repetitiv cu numr cunoscut de pai are urmtoarea sintax:
PENTRU contor <- valoare iniial, valoare final, pas EXECUT
Instruciuni

Instruciunile se execut pentru fiecare valoare a contorului care îndeplinete condiia de a se situa între valoarea iniial i valoarea final, inclusiv aceasta. Dup fiecare execuie, contorul îi modific valoarea cu cea anterioar + pas.
· Exemple din viaa de zi cu zi - structuri repetitive cu numr cunoscut de pai
1. Modul în care rezolvm cele 7 exerciii din tema de la matematic: identificm primul exerciiu, îl rezolvm, identificm cel de-al doilea exerciiu, în rezolvm, identificm cel de-al treilea exerciiu, îl rezolvm etc.
2. Scriem o propoziie, pe caiet, de 100 de ori.
3. Scriem numerele de la 1 la 100, pe caiet.
4. Un copil are la dispoziie 3 jucrii. Pentru fiecare dintre cele 3 jucrii, trebuie s noteze greutatea jucriei.
· APLICAII
1. Pentru fiecare dintre exemplele de mai sus, identificai operaia care se repet i numrul de repetiii.
Rezolvare exemplul 1.

Numrul de repetiii este egal cu 7.
2. Identificai alte 3 situaii din viaa de zi cu zi în care apare o structur repetitiv cu numr cunoscut de pai.
· Jocuri care s conin structuri repetitive cu numr cunoscut de pai, fr utilizarea tehnologiei
1. Cel mai norocos- câtig!
Trei copii joac un joc cu zaruri. Fiecare arunc, pe rând, de câte 5 ori, cele 2 zaruri pe care le au. Punctele de pe zaruri se adun i ofer un punctaj final pentru fiecare copil. Câtig cel cu punctajul mai mare.
2. Ptratul
Doi copii au la dispoziie un ptrat împrit în 6 linii i 6 coloane jos i dou zaruri. Începând cu csua stânga sus, vor scrie în csuele obinute, numere naturale i mesajul X (cu semnificaia c se anuleaz tot punctajul).
Iat un exemplu de ptrat, mai jos.
Copiii arunc pe rând, de câte 5 ori fiecare, cu zarurile. Numerele de pe cele dou zaruri reprezint linia i coloana csuei de unde se ia punctajul. Dac nimerete csua cu X, se anuleaz tot punctajul de pân acum, al juctorului. Câtig cel cu punctajul mai mare.
3. Fotbal
Cinci copii arunc la poart cu mingea, pe rând. Câtig cel care a înscris cele mai multe goluri.
4. Arcul
Doi copii au la dispoziie un arc, trei sgei i o int. Fiecare arunc la int cu arcul de 3 ori, însumând punctajul obinut. Câtig cel cu punctajul mai mare.
5. Distracie
ase prieteni îi scriu prenumele pe câte o foaie de hârtie. Hârtiile sunt amestecate i întoarse cu faa în jos. Fiecare alege una dintre hârtiile cu prenumele i rostete prenumele ales, citind de la dreapta spre stânga literele. Pentru fiecare prenume rostit corect, câtig 1 punct. Fiecare are la dispoziie 3 încercri.
6. Joc în SCRATCH, fr SCRATCH
Decupai blocurile de mai jos i încercai s aezai atâtea câte avei nevoie i în ce ordine dorii, astfel încât personajul din imagine s îi schimbe aspectul (costumul) de 3 ori, la apsarea steguleului verde. Scriei valorile corespunztoare unde acestea lipsesc.
Acesta este personajul i costumele pe care le are la dispoziie. Trebuie s le aezai în ordinea în care dorii s îi schimbe aspectul. Creai, pe foaia de hârtie, o poveste plecând de la acest personaj i schimbarea aspectului su.
SARCIN DE LUCRU:
Creai i voi alte 3 jocuri distractive în care s apar cel puin o structur repetitiv cu numr cunoscut de pai.
APLICAII DE 5 stele:
1. Se consider urmtoarea secven de instruciuni, reprezentat în pseudocod:
x1
dac (i mod 3 != 0) atunci xx-1


a) Ce valoare va avea variabila x în urma execuiei acestei secvene?
b) Rescriei secvena de mai sus, folosind alte dou structuri repetitive cunoscute.
c) Scriei un enun al problemei rezolvate de algoritmul de mai sus.
2. Se consider urmtoarea secven de instruciuni, reprezentat în pseudocod :
s0; p1;
pp*i
sfârit pentru;
afieaz s,p
a) Ce se afieaz în urma execuiei secvenei de mai sus?
b) Rescriei secvena de mai sus, folosind alte dou structuri repetitive cunoscute.
c) Scriei un enun al problemei rezolvate de algoritmul de mai sus.
3. Scriei un algoritm pseudocod care rezolv urmtoarele probleme, pentru a calcula sumele:
DESPRE INTERNET
În România, începând cu 1970, demareaz proiectul RENAC (Reeaua Naional de Calculatoare) / RENOD (Reeaua Nodal de Comunicaii) pentru constituirea unei reele la nivel naional. Proiectul a fost finalizat la sfâritul anului 1983.
În anul 1989, cercettorul britanic Tim Berners-Lee, în timp ce lucra ca inginer de software la CERN (Organizaia European pentru Cercetri Nucleare) din Geneva, a creat World Wide Web prin unirea hipertextului cu Internetul. Din anul 1994, Tim Berners-Lee este directorul World Wide Web Consortium (W3C), care creeaz tehnologii pentru a dezvolta Web-ul.
· REELE DE CALCULATOARE
O reea de calculatoare este format dintr-un grup de dou sau mai multe calculatoare, interconectate, care comunic între ele în scopul partajrii informaiei.
Calculatoarele i dispozitivele din reea comunic între ele pe baza unui set de reguli, numit protocol. Toate sistemele de operare utilizeaz un Protocol de Control al Transmisiei/Protocol Internet (TCP/IP).
Protocolul de Transfer al Fiierelor – File Transport Protocol (FTP) este cea mai folosit metod de transfer a fiierelor, indiferent de tipul i dimensiunea acestora, de la un calculator la altul, prin intermediul Internetului.
Avantajele lucrului într-o reea de calculatoare sunt:
· Partajarea fiierelor;
· Accesul la Internet.
Pentru a se conecta în reea, fiecare calculator trebuie s dispun de o plac de reea, care s asigure, prin cablu sau prin unde radio (wireless), legtura cu celelalte calculatoare sau dispozitive ale reelei.
În funcie de aria de rspândire, se definesc urmtoarele reele:
· Personal Area Network (PAN) – reea de foarte mic întindere de cel mult câiva metri, constând din aparatele interconectabile din apropierea unei persoane ( PC, imprimant, scanner, telefon mobil, etc.);
· Local Area Network (LAN) – reea realizat la nivelul unei cldiri sau a unui grup de cldiri;
· Metropolitan Area Network (MAN) – reea realizat la nivelul unui întreg ora sau a unei zone urbane. Aceste reele folosesc de obicei tehnologia fr fir (wireless) sau fibr optic pentru a crea conexiuni.
· Wide Area Network (WAN) – reeaua conecteaz orae, regiuni sau ri. Pentru conexiuni se folosesc linii telefonice închiriate, fibr optic, transmisiuni prin satelit.
· REEAUA INTERNET
Este o reea global compus din alte reele de calculatoare interconectate printr-un standard de comunicare numit TCP/IP (Transmission Control Protocol i Internet Protocol) destinat s faciliteze schimbul de date i informaii.
Cele mai importante servicii oferite de Internet sunt:
· E-mail (pota electronic) – permite schimbul de mesaje electronice între persoane care pot accesa acest serviciu, indiferent unde se afl acesta.
· WWW (Word Wide Web) – pune la dispoziie un sistem în care documentele i informaiile sunt legate între ele i pot fi uor accesate prin reeaua Internet.
· FTP-ul (File Transfer Protocol) – permite transferul fiierelor între calculatoare conectate la INTERNET.
· Telnet – permite conectarea prin Internet de la distan, de pe un calculator local pe un alt calculator aflat în alt locaie.
· IRC (Internet Relay Chat) – permite comunicarea (transmiterea mesajelor) în timp real între persoane.
· CUTAREA INFORMAIILOR ÎN INTERNET
Pentru a gsi informaiile pe care le dorim în reeaua Internet, avem nevoie de un browser i de un motor de cutare.
Un browser sau navigator este un program ( o aplicaie software) care permite utilizatorilor s afieze text, grafic, video, muzic i alte informaii situate pe o pagin din WWW, dar i s comunice cu furnizorul de informaii i chiar s comunice între ei.
Exemplu:
Microsoft Internet Explorer, Google Chrome, Mozila Firefox, Opera, Apple Safari.
Un motor de cutare este un program care acceseaz Internetul i care reine titlul, cuvintele cheie i parial, coninutul paginilor web, într-o colecie de date. În momentul în care cutm prin intermediul unui motor de cutare o anumit informaie, motorul va afia o list cu adresele site-urilor care conin date despre informaia solicitat, list extras din colecia de date.
Ex: Google, Yahoo, Bing, Baidu.
Avantaje ale Internetului:
· Reprezint o surs de divertisment;
· Ofer posibilitatea comunicrii în timp real a oamenilor din întreaga lume.
· Libertatea de exprimare.
Dezavantaje ale Internetului:
· Lipsa proteciei datelor personale i posibilitatea furtului de identitate;
· Imposibilitatea de a verifica dac o informaie este adevrat sau fals;
· Posibilitate de virusare a calculatorului;
· Existena de site-uri periculoase pentru copii.
· Rspândirea ideilor periculoase.
Internetul i majoritatea reelelor folosesc principiul client/server. Servere de pe tot globul ofer anumite servicii, iar clienii (PC-uri, calculatoare portabile sau telefoane) se conecteaz la acestea pentru a accesa informaii.
Procesul de transfer a fiierelor de pe calculatorul server pe calculatorul client poart numele de download, iar procesul de transfer a fiierelor de pe calculatorul client pe calculatorul server poart numele de upload.
· POTA ELECTRONIC
Este o variant de a trimite o scrisoare unui destinatar, nu în form fizic (scris pe hârtie, pus în plic cu timbru i dus la pot), ci în form electronic, cu ajutorul unui dispozitiv electronic, respectiv calculator (laptop sau desktop), tablet sau telefon inteligent.
Scopul potei electronice este de a trimite mesaje text (de tipul scrisorilor), dar în format electronic, unui destinatar, într-o csu potal virtual, de unde destinatarul le ia i le citete dac i când dorete, exact cum ar proceda cu scrisorile tradiionale, primite prin pot.
Avantajele potei electronice:
· Comoditate.
Pentru a putea trimite i primi e-mailuri trebuie s avem un cont de e-mail. La creare cantului ne sunt solicitate serie de informaii personale.
O adres de e-mail este format din:
· Numele contului de pot electronic (poate fi numele tu sau alt nume sugestiv);
· Caracterul special: @;
· Adresa calculatorului gazd, a serverului pe care este creat csua de e-mail.
Data: ___________
______________________ ______
1. Ce este Internetul? (1p)
a) O surs de informaii
b) O reea de calculatoare
c) O reea mondial de calculatoare interconectate
d) O surs de comunicare
2. Care este cel mai folosit protocol? (1p)
a) E –mail
b) Chat
c) FTP
d) Facebook
3. Cum se numete prima reea de calculatoare creat în anul 1969? (1p)
a) CYBERNET
b) INTRANET
c) INTERNET
d) ARPANET
a) LAN i MAN
d) PAN, LAN, MAN i WAN
5. Într-o reea de calculatoare de tip client/server, calculatoarele pot avea statut de: (1p)
a) Client i server
a) Intrare
b) Ieire
7. Identific adresa de e-mail (1p)
a) www.abc.ro
b) abc@ro.com
c) abc@yahoo.com
d) www.edu@
a) Chrome
b) Opera
c) Google
d) Internet Explorer
_______________________________________________________________
_______________________________________________________________
2 - c) FTP
3 - d) ARPANET
5 - c) Client sau Server
6 - a) Intrare – Ieire
· Reprezint o surs de divertisment;
· Ofer posibilitatea comunicrii în timp real a oamenilor din întreaga lume.
- Dezavantaje:
· Lipsa proteciei datelor personale i posibilitatea furtului de identitate;
· Imposibilitatea de a verifica dac o informaie este adevrat sau fals;
· Posibilitate de virusare a calculatorului.
· Clasa a IX-a, matematic-informatic
Profesor Catarag tefania Issabella
Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea
1. Scriei secvena de program care afieaz numerele naturale nenule, mai mici decât un numr dat n, care au ultima cifr 2. Exemplu: dac n=26, se vor afia: 2, 12, 22
2. Scriei secvena de program care determin media aritmetic a numerelor care se divid la 3 din n numere citite de la tastatur. Exemplu: dac se citesc numerele 5, 6, 11,3, 9, 20 se va afia (6+3+9)/3= 6
3. Scriei secvena de program care determin suma cifrelor impare dintr-un numr natural n citit de la tastatur. Exemplu: pentru n= 21746 se va afia 8.
4. Fie secvena:
atunci
scrie t;
a) Scriei valoarea pe care o va afia algoritmul dac se citesc valorile 12 i 3
b) Scriei în pseudocod un algoritm echivalent cu cel dat, în care s se înlocuiasc structura cât timp...execut cu o structur repetitiv de alt tip.
· Clasa a IX-a, tiinele naturii
Profesor Catarag tefania Issabella
Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea
1. Declarai i citii de la tastatur 2 variabile de tip întreg.
1. Enumerai tipurile de date folosite în pseudocod.
1. Alegei cuvintele cheie care fac parte din structurile de control: întreg, dac, repet, real, atunci, început, pentru.
1. Enumerai operatorii logici. Dai un exemplu de utilizare a unui operator.
1. Evaluai urmtoarea expresie: 3^2 <7 or 10 mod 3 = 1
1. Scriei în forma acceptat de calculator expresia: 2x2 -4x +1
1. Scriei condiia pentru ca un numr natural a s fie numr pozitiv i s aib 2 cifre.
1. Ce se va afia în urma executrii urmtoarei secvene de atribuiri?
a← 5 b← 20 c← 30 a← b div 2 b← a+c div 5 c← b ^2
1. Fie secvena:
Atunci x ← x +1;
· Clasa a IX-a, matematic-informatic intensiv informatic
Profesor Cojocaru Nicoleta
Colegiul Naional de Informatic „Matei Basarab”, Rm. Vâlcea
tim c vectorii sunt o colecie de valori de acelai tip (întreg, caracter, sau alte tipuri), valori ce pot fi accesate dup un indice, sau poziie, care se mai cheam i indicele în vector al acelei valori.
EXEMPLU:
V
Acest vector are numele v i are n elemente, numere întregi. Indicii elementelor sunt 0, 1, 2, ... , n-1.
DEFINIIE:
Vectorul de frecven reine numrul de apariii al fiecrei valori citite într-un vector. Folosirea vectorului de frecvene permite scrierea unor algoritmi eficieni în cazul în care datele de intrare au valori dintr-un domeniu cunoscut care poate fi prelucrat rapid. Folosirea unui vector de frecven sau marcare este eficient numai în cazul în care valorile care intereseaz sunt întregi i numrul valorilor distincte posibile este cel mult 1.000.000.
În orice mulime elementele sunt unice, iar vectorul frecvenelor are doar valori 0 sau 1. Acest vector este numit vectorul caracteristic al unei mulimi.
Vectorul de frecvene poate fi folosit pentru a obine rapid mulimea asociat ca un vector caracteristic astfel:
- 0 înseamn c elementul nu aparine mulimii;
- o valoare diferit de 0 înseamn c elementul aparine mulimii.
Exemple de probleme:
1. Fiind dat un numr natural n între 1 i dou miliarde s se afieze cifrele numrului i numrul de apariii ale fiecrei cifre în numr.
Date de intrare: Fiierul de intrare cifdist.in conine numrul n.
Date de ieire: Fiierul de ieire cifdist.out va conine pe fiecare linie cifra si numrul de apariii a acesteia în numr, separate printr-un spaiu.
Exemplu:
cifdist.in
cfidist.out
Explicaii
2342342444
2 3
3 2
4 5
Numrul 2342342444 conine 3 cifre distincte, 2, 3 i 4. Cifra 2 apare în numr de 3 ori, cifra 3 de 2 ori i cifra 4 de 5 ori.
Vectorul de frecven pentru cifrele unui numr se declar sub forma unui vector cu 10 componente, de la v[0], … , v[9]. Acestea vor fi iniializate cu 0, iar dup citirea numrului n se va incrementa cu 1 numrul apariiilor pentru fiecare cifr a lui n.
Atenie! Vectorul de frecvene nu permite refacerea numrului citit iniial, dac este necesar valoarea acestuia trebuie memorat separat.
#include<fstream> using namespace std;
ifstream f("cifdist.in");
ofstream g("cifdist.out");
{ c=n%10;
for(c=0;c<10;c++)
return 0;
}
2. Se dau n numere naturale cu cel mult dou cifre fiecare. S se afieze acele numere care apar o singur dat.
#include <iostream>
}
ÎNCERCAI SINGURI:
Pentru problema rezolvat anterior, s se afieze acele numere care apar o singur dat, precum i frecvena lor.
3. S se scrie un program care citete cel mult 1000000 de numere naturale din intervalul închis [0,9] i determin cel mai mare numr prim citit i numrul su de apariii.
#include <iostream>
}
TEM:
a. S se scrie un program care citete din fiierul „date.in” cel mult 1000000 de numere naturale din intervalul închis [0,1000] i determin cel mai mare numr par de trei cifre citit i numrul su de apariii.
b. S se scrie un program care citete din fiierul „date.in” cel mult 1000000 de numere naturale din intervalul închis [0,100] i determin cel mai mic numr impar de dou cifre citit i numrul su de apariii.
c. Se d un ir cu cel puin 3 i cel mult 1.000.000 de numere naturale din intervalul (0, 1.000.000.000). Se cere s se afieze pe ecran, separate printr-un spaiu, dou numere distincte, anume cel mai mare numr impar cu dou cifre i cel mai mic numr par cu dou cifre care NU fac parte din ir. Dac nu exist dou astfel de valori se va afia pe ecran mesajul nu exist.
http://www.pbinfo.ro/ problemele:mincifre,numere8,numere1
· Clasa a IX-a, matematic-informatic intensiv informatic
· Clasa a X-a, matematic-informatic
Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea
Definiie: Fie a un vector cu n elemente. Se numete secven a vectorului a o succesiune de elemente consecutive din a, în ordinea din a.
Orice secven a unui vector este unic determinat de doi indici li ≤ lf, ai primului, respectiv ultimului element din secven (li=limita iniial, lf=limita final).
Exemplu: Fiind dat vectorul a=(1, 3, 4, 7, 8, 10, 13). Atunci:
· (1, 3, 4, 7), (3, 4, 7, 8, 10), (7, 8, 10, 13), (1), (13) reprezint secvene ale vectorului a
· (1, 4, 3, 10) nu reprezint secven în vectorul a – ordinea valorilor nu este cea din vectorul a
· (1, 3, 4, 8) nu reprezint secven în vectorul a – valorile nu sunt consecutive în vector
· (1, 3, 4, 5, 7) nu reprezint secven în vectorul a – avem o valoare care nu apare în vectorul a
Definiie: Prin lungimea unei secvene se înelege numrul de elemente care formeaz secvena. Lungimea secvenei delimitate de indicii li i lf este lf - li + 1 (li=limita iniial, lf=limita final).
Numrul secvenelor unui vector
Numrul secvenelor unui vector poate fi determinat numrând secvenele de lungime 1, 2, …, n.
· sunt n secvene de lungime 1 – fiecare element în parte.
…
· sunt dou secvene de lungime n-1 – secvenele 1-(n-1) i 2-n este o secvena de lungime n – întreg vectorul.
În total vor fi n+(n−1)+…+2+1= n*(n+1)/2 secvene!
Secven de lungime maxim
Fie a un vector cu elemente de un anumit tip. S se determine cea mai lung secven din vector în care toate elementele au o anumit proprietate P.
I. Prima soluie la care ne gândim este s lum în considerare toate secvenele posibile (cele n*(n+1)/2 secvene), s verificm dac toate elementele din secven verific proprietatea P i apoi s comparm lungimea secvenei cu un maxim i s modificm dac este nevoie acel maxim (reinem i poziia de început/sfârit a secvenei de lungime maxim).
CITESTE n
CITESTE a[i]
PENTRU i=1, n EXECUTA
PENTRU j=i, n EXECUTA
//tratez secvena cuprinsa intre indicii i si j
Cod←1
PENTRU k=i, j EXECUTA
DACA a[k] nu respecta proprietatea P ATUNCI
Cod←0
SFARSIT DACA
SFARSIT PENTRU
Maxim=j-i+1
//
// lungime maxima
SFARSIT DACA
SFARSIT DACA
SFARSIT PENTRU
SFARSIT PENTRU
SCRIE Maxim //lungimea maxima a secvenei
PENTRU i=imax, jmax EXECUTA //scrie elementele din secventa de lungime maxim
SCRIE a[i]
SFARSIT PENTRU
II. A doua soluie este cea eficient. Parcurgem liniar vectorul element cu element i reinem la fiecare pas lungimea secvenei curente, pozitia de început/pozitia de sfârit a secvenei curente precum i lungimea secvenei de lungime maxim, pozitia de început/pozitia de sfârit a acestei secvene.
Iniial: maxim←0; lc←0; lic←0; lfc←0; //lungimea secvenei curente, limita iniial
//i limita final a secvenei curente
CITESTE n
PENTRU i=1, n EXECUTA
CITESTE a[i] SFARSIT PENTRU maxim←0; lic←0; lfc←0; lc←0
PENTRU i=1, n EXECUTA //parcurg pe rând elementele din vector
DACA a[i] are proprietatea P ATUNCI
lc←lc+1 //creste lungimea secvenei curente
DACA lic=0 ATUNCI //a[i] este primul din secventa curenta
lic←i
lfc←i //rein limita iniial si cea finala a secvenei curente
ALTFEL
SFARSIT DACA
ALTFEL //s-a terminat secventa curenta si compar lungimea ei cu maxim
DACA lc>maxim ATUNCI
maxim=lc limax=lic lfmax=lfc
//rein limita iniial si cea finala pentru secventa de lungime maxima
SFARSIT DACA
lc=0 //începe o noua secventa a crei lungime este 0
lic←0
lfc←0 //limita iniial si limita finala a secvenei curente
SFARSIT DACA
SFARSIT PENTRU
DACA lc>maxim ATUNCI
maxim=lc limax=lic
lfmax=lfc
//rein limita iniial si cea finala pentru secventa de lungime maxima
SFARSIT DACA
SCRIE maxim
SCRIE a[i]
SFARSIT PENTRU
Exemplu numeric:
2, 4, 3, 5, 6, 8, 10, 1, 3, 2, 4, 6, 8 (vector cu 13 elemente numere naturale). Determin cea mai lung secven de elemente pare din vector.
Lc=0 lic=lfc=0 i=1 Lc=1 lic=lfc=1 //2 este par i crete lc iar lic i lfc iau valoarea lui i i=2 lc=2 lfc=2 //4 este par i crete lc iar lfc=2
i=3 maxim=2, limax=1, lfmax=2 //3 nu este par ceea ce înseamn c s-a terminat secvena curent, se modific maxim precum i limitele limax i lfmax
Lc=lic=lfc=0 //lc, lic si lfc devin 0 pentru c începe o nou secven i=4 //5 nu este par i=5 lc=1 lic=lfc=5 //6 este par i crete lc iar lic i lfc iau valoarea lui i adic 5 i=6 lc=2 lif=6 //8 este par i crete lc iar lfc devine 6
i=7 lc=3 lif=7 //10 este par i crete lc iar lfc devine 7
i=8 maxim=3, limax=5, lfmax=7 // 1 nu este par ceea ce înseamn c s-a terminat secvena curent, se modific maxim precum i limitele limax i lfmax
Lc=lic=lfc=0 //lc, lic si lfc devin 0 pentru ca începe o nou secven i=9 // 3 nu este par i=10 lc=1 lic=lfc=10 //2 este par i crete lc iar lic i lfc iau valoarea lui i adic 10 i=11 lc=2 lfc=11 //4 este par i crete lc iar lfc devine 11 i=12 lc=3 lfc=12 //6 este par i crete lc iar lfc devine 12 i=13 lc=4 lfc=13 //8 este par i crete lc iar lfc devine 13
S-a terminat secvena curent. Comparm lc cu maxim i se modific maxim i limitele limax i lfmax.
Maxim=4 limax=10 lfmax=13
Lungimea maxim este 4 iar secvena începe la poziia 4 i se termin la poziia 10.
Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea
Se consider un vector cu elemente numerice. Se cere s se determine suma elementelor dintr-o anumit secven dat sau din mai multe secvene date.
I. Soluia banal este aceea în care sunt parcurse toate elementele din secven i sunt adugate la sum.
CITESTE n
CITESTE a[i]
SFARSIT PENTRU
CITESTE li, lf //indicii de început i sfârit pentru secven a crei sum se //calculeaz
S←0
S←S+a[i]
SFARSIT PENTRU
SCRIE S
Pentru o singur secven timpul de execuie este acceptabil dar dac se dorete calcularea sumelor pentru un numr mare de secvene timpul de execuie poate deveni inacceptabil de mare.
În astfel de situaii putem folosi o a doua soluie care utilizeaz sumele pariale.
II.
Fie un vector a cu n elemente. Poziiile elementelor sunt numerotate de la 1 la n.
Determinm suma elementelor din secvena determinat de indicii 5 i 9:
Valoarea sumei este a[5] + a[6] + a[7] + a[8] + a[9] = 5 + 1 + 8 + 0 + 9 = 23.
Pentru a determina rapid aceast sum, vom construi un alt vector S pe care îl vom numi vectorul sumelor pariale. Fiecare element S[i] din acest vector va fi egal cu suma elementelor vectorului cuprinse între poziiile 1 i i (inclusiv aceste poziii).
S[i]=a[1]+a[2]+...+a[i].
Acest vector se poate construi la citirea vectorul a folosind urmtoarea relaie:
S[1]=a[1]
S[2]=a[1]+a[2]=S[1]+a[2]
………………………………………………………….
Practic, fiecare element S[i] (suma elementelor cuprinse între poziiile 1 i i) din vectorul sumelor pariale se obine adunând la anteriorul element din acest vector (S[i-1]=suma elementelor cuprinse între poziiile 1 i i-1) elementul a[i].
Pentru a determina suma elementelor din secvena determinat de indicii li i lf folosim urmtoarea formul, în timp constant: a[li]+a[li + 1]+...+a[lf]=S[lf]−S[li − 1]
=a[1]+a[2]+…+a[lf] – (a[1]+a[2]+…+a[li-1])=a[li]+…+a[lf]
Astfel, pentru li=5 i lf=9:
a[5]+a[6]+a[7]+a[8]+a[9]=S[9]−S[4]=39-16=23
CITESTE n
CITESTE a[i]
SFARSIT PENTRU
SCRIE Suma
Observaie:
Este posibil ca sumele pariale ale elementelor din vectorul a s depeasc limita maxim a tipului de date folosit pentru elementele din vector (de exemplu int). În acest caz, vectorul sumelor pariale S trebuie declarat cu elemente de un tip care permite valori mai mari (de exemplu long long int).
· Clasa a IX-a, matematic-informatic/
Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea
Problema 1: Se dau dou numere naturale cu cel mult 9 cifre fiecare. Se cere s se afieze cifrele comune celor dou numere, ordonate cresctor.
Exemplu: x=12432576
Cifrele comune sunt: 2 3 5 6 7
Exist mai multe variante de rezolvare a problemei la care ne putem gândi.
Vom pstra cifrele celor dou numere în doi vectori (notm vectorii a i b).
I. Cutm elementele vectorului b printre elementele vectorului a i pstrm în vectorul c doar acele elemente din b care se gasesc în a dar nu au fost puse înc în vectorul c. În acest fel obinem în vectorul c cifrele comune. În final trebuie s ordonm vectorul c folosind una dintre metodele de sortare. Putem ordona iniial vectorii a i b i apoi s folosim cutarea binar i obinem vectorul c deja ordonat.
II. Ordonm cresctor elementele din cei doi vectori a i b. Putem folosi apoi interclasarea pentru a obine elementele comune (luate o singur dat) care, evident, vor fi în ordine cresctoare.
III. Parcurgem cifrele de la 0 la 9 (cresctor) i cutm fiecare cifr în vectorii a i b. Dac cifra apare atât în vectorul a cât i în vectorul b atunci o afim. Aceas variant de rezolvare o putem gândi i fr pstrarea cifrelor numerelor în vectorii a i b. În acest caz, pentru fiecare cifr determinm cifrele din x i y pentru a vedea dac cifra apare i în x i în y.
Soluia eficient presupune definirea a doi vectori cu cate 10 elemente fiecare, pentru fiecare dintre cele dou numere x i y. Vectorii vor fi indexai începând de la 0.
Indicii elementelor din vector reprezint cifrele de la 0 la 9.
Vectorii sunt definii în felul urmtor:
Vectorii vor fi construii dup citirea celor dou numere. În final, parcurgem cifrele de la 0 la 9 i dac pe poziia corespunztoare cifrei respective i în vectorul a i în vectorul b se afl valoarea 1 atunci afim cifra.
Cifrele comune sunt: 2, 3, 5, 6, 7
Vectorii astfel definii se numesc vectori caracteristici (sau vectori de apariii). Elementele lor caracterizeaz cifrele de la 0 la 9, stabilind pentru fiecare cifr dac face sau nu parte din numrul respectiv.
Observaii:
· vectorul caracteristic (de apariii) are dimensiune constant – egal cu numrul de valori pe care le caracterizeaz
· elementele vectorului caracteristic sunt 0 sau 1 (echivalent cu Adevrat i Fals) Pentru a putea folosi un vector caracteristic (de apariii) în rezolvarea unei probleme trebuie îndeplinite câteva condiii condiii:
· datele caracterizate (pentru care verificm apariia) au valori mici, sunt numere naturale dintr-un interval de forma [0,ValMax] sau pot fi echivalente cu astfel de numere
· practic, putem folosi un vector caracteristic dac memoria disponibil permite declararea unui vector cu un numr de elemente corespunztor. De exemplu, dac datele de intrare sunt din intervalul [0, 1000] sau [0,10000] putem folosi un vector caracteristic dar dac datele de intrare sunt din intervalul [0, 1000000000] nu putem folosi un vector caracteristic
//vectorii a i b trebuie s aib iniial toate elementele egale cu 0
CITESTE x, y
crest[x/10]
a[c]1 //în vectorul a pe poziia c pun valoarea 1 (cifra c se gsete în x)
x[x/10]
PANA CAND x=0 REPETA crest[y/10]
b[c]1 //în vectorul b pe poziia c pun valoarea 1 (cifra c se gsete în y)
y[y/10]
PENTRU c=0, 9 EXECUTA
DACA (a[c]=1) and (b[c]=1) ATUNCI // dac cifra c apare în ambele numere
SCRIE c
SFARSIT DACA
SFARSIT PENTRU
Problema 2: Se d un numr natural cu cel mult 9 cifre. Se cere s se afieze cifra cu cel mai mare numr de apariii. Dac sunt mai multe cifre cu numr maxim de apariii se va afia cea mai mare.
Exemplu: x=15232525
Cifra cerut este 5.
O prim idee de rezolvare ar fi aceea în care calculm pentru fiecare cifr de la 0 la 9 de cate ori apare în numrul dat. Calculm apoi maximul de apariii i selectm cifra cerut.
Soluia eficient presupune definirea unui vector a cu 10 elemente, vector ai crui indici sunt de la 0 la 9.
Elementele vectorului vor fi definite în felul urmtor:
a[i] = numrul apariiilor cifrei i în numrul x
Vectorul va fi construit imediat dup citirea numrului x. Dup construirea vectorului a se va determina maximul de apariii i cifra cea mai mare care are numr maxim de apariii.
Un vector de genul acesta se numete vector de frecven.
PENTRU i=0, 9 EXECUTA
a[i]0 //iniial numrul apariiilor este 0 pentru fiecare cifr
SFARSIT PENTRU
crest[x/10]
a[c]a[c]+1 //crete numrul apariiilor pentru cifra c
x[x/10]
PENTRU c=0, 9 EXECUTA
DACA a[c]>=maxap ATUNCI //mai mare sau egal pentru a reine cifra cea
//mai mare cu numr maxim de apariii
maxapa[c] cmaxc
SFARSIT DACA
SFARSIT PENTRU
SCRIE cmax
Problema 3 (Ciurul lui Eratostene): Se d n numr natural. S se afieze numerele naturale prime mai mici sau egale cu n.
Ciurul lui Eratostene este un algoritm vechi i simplu de determinare a tuturor numerelor naturale prime pân la un numr precizat. A fost creat de Eratostene – matematician din Grecia antic.
1. Se scrie o list a numerelor de la 0 la numrul precizat (n în cazul nostru)
2. Se taie 0 i 1 despre care se tie c nu sunt numere prime
3. Se caut primul numr netiat. Primul numr netiat este numr prim.
4. Se taie toi multiplii acelui numr (cei care nu au fost înc tiai) din list
5. Se repet paii 3 i 4 pân când sunt epuizate toate numerele din list
Exemplific în continuare algoritmul pentru n=100.
Pentru fiecare numr x netiat voi tia multiplii mai mari decât el (2*x, 3*x, 4*x, …) i mai mici sau egali cu n.
Am tiat 0 i 1 despre care tim c nu sunt numere prime.
Primul numr netiat este 2. Am marcat cu portocaliu valoarea 2 care este numr prim i am tiat cu linii portocalii multiplii lui 2.
Primul numr netiat este 3. Am marcat cu galben valoarea 3 care este numr prim i am tiat cu linii galbene multiplii lui 3 netiai înc.
Primul numr netiat este 5. Am marcat cu albastru valoarea 5 care este numr prim i am tiat cu linii albastre multiplii lui 5 netiai înc.
Primul numr netiat este 7. Am marcat cu mov valoarea 7 care este numr prim i am tiat cu linii mov multiplii lui 7 netiai înc.
Primul numr netiat este 11. Multimplii lui 11 sunt deja tiai.
Toate numerele rmase netiate sunt numere prime: 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
CITESTE n
ciur[i] 0 //0 înseamn element netiat
SFARSIT PENTRU
PENTRU i=2, n EXECUTA
DACA ciur[i]=0 ATUNCI //dac i este netiat
//tai multiplii lui i (multiplii au forma i*j)
j2 //multiplii lui i pleaca de la 2*i (j pleaca de la 2)
CAT TIMP i*j<=n EXECUTA
ciur[i*j]1 //tai multiplul i*j
jj+1
SFARSIT CAT TIMP
PENTRU i=1, n EXECUTA
DACA a[i]=0 ATUNCI //a[i]=0 inseamn c i este prim
SCRIE i
SFARSIT DACA
SFRASIT PENTRU
· Clasa a XI-a, matematic-informatic
Colegiul Naional „Gib Mihescu”, Drgani
Spunem c o noiune este recursiv, dac în definirea ei apare însi noiunea care se definete.
În informatic, un subprogram se numete recursiv dac se autoapeleaz, fie direct (în definiia lui, se face apel la el însui), fie indirect (subprogramul X apeleaz subprogramul Y, care apeleaz subprogramul X). Din afara subprogramului se face un prim apel al acestuia, dup care acesta se autoapeleaz de un anumit numr de ori, creându-se un lan de autoapeluri recursive.
Deoarece un subprogram recursiv se autoapeleaz, în interiorul acestuia trebuie s existe o condiie de oprire a lanului de autoapeluri, fr aceast condiie, subprogramul s-ar autoapela la infinit.
Pentru a implementa un subprogram recursiv, trebuie s:
· Identificm relaia de recuren
· Identificm condiiile de oprire ale autoapelului
Unul dintre cele mai simple exemple de subprograme recursive este factorialul.
n!=n*(n-1)*(n-2)*...*3*2*1=n*(n-1)!
Definiia recursiv a lui n! este: ! =
Funcia recursiv se va scrie astfel:
long fact(int n)
}
Primul apel al unui subprogram recursiv se realizeaz din afara acestuia, apoi subprogramul se autoapeleaz, executându-se corpul acesteia, eventual cu alte date de intrare (parametrii) pân la întâlnirea condiiei de oprire.
Pentru exemplul de mai sus, primul apel poate fi realizat în programul principal:
int main()
}
Un subprogram recursiv trebuie s asigure condiia de consisten, modificare a parametrilor sau variabilelor locale, astfel încât lanul de autoapeluri s tind spre îndeplinirea condiiei de oprire.
MECANISMUL DE AUTOAPELARE A SUBPROGRAMELOR
Se tie c la apelul unui subprogram, se pstreaz în stiv contextual modulului apelant (valorile parametrilor formali, variabilelor locale i adresa de revenire). În cazul subprogramelor recursive, de fiecare dat când subprogramul se autoapeleaz, se creeaz un nou nivel în stiv i se memoreaz parametrii formali, variabilele locale i adresa de revenire. Instruciunile aflate dup apelul recursiv, vor fi executate pentru fiecare nivel al stivei pentru parametrii i variabilele din stiv. Acest lucru se întâmpl, deoarece la fiecare autoapel s-a salvat adresa de revenire din subprogramul apelant. Dup ce se termin execuia subprogramului, se elibereaz segmentul de stiv alocat.
OBSERVAII:
1. Pentru orice algoritm recursiv exist un algoritm iterativ care rezolv aceeai problem.
2. Recursivitatea ofer avantajul unor soluii mai clare pentru probleme i o lungime mai mic a programului. Ea prezint îns dezavantajul unui timp mai mare de execuie i a unui spaiu de memorie mai mare.
Exemplu 1. Scriei o funcie recursiv care calculeaz suma cifrelor unui numr natural, transmis ca parametru.
Identificarea relaiei de recuren. Notm cu s(n) – suma cifrelor numrului natural n.
() =
int suma(int n)
}
Exemplu 2. Scriei o funcie recursiv care primete ca parametru un numr natural i returneaz numrul obinut prin eliminarea cifrelor pare.
De fapt, va trebui sa reconstruim numrul iniial, prin adugarea doar a cifrelor impare.
Funcia recursiv se va scrie astfel:
int sterg(int n){
if(n==0) return 0;
if(n%2) return sterg(n/10)*10+n%10; //dac cifra este impar o adugm în numr
else
}
Exemplu 3. S se calculeze CMMDC al doua numele naturale folosind o funcie recursiv.
Poate fi folosit algoritmul lui Euclid, în oricare dintre cele dou forme.
int cmmdc(int a, int b){ //varianta prin restul împririi
}
int cmmdc2(int a, int b) { //varianta prin scderi repetate
if(a==b) return a; // dac numerele sunt egale, returnm cel mai mare divizor comun
if(a>b) return cmmdc(a-b,b); // dac a este mai mare, atunci scdem din a pe b
else
}
TEM
1. Scriei o funcie recursiv care verific dac un numr natural este prim sau nu.
2. Se citete un vector a cu n elemente numere naturale. S se calculeze elementul maxim din vector. Se va folosi o funcie recursiv pentru citire i una recursiv pentru determinarea elementului maxim.
3. S se determine cifra maxim a unui numr natural folosind o funcie recursiv.
4. Descompunei un numr natural n ca sum de termeni din irul lui Fibonacci. Scriei funcii recursive pentru toate prelucrrile necesare.
5. Se citete un numr natural n. S se descompun numrul n in toate modurile ca sum de dou numere a i b care au proprietatea c b este rsturnatul lui a. Se vor scrie i folosi dou funcii recursive pentru:
- Calculul rsturnatului
- Descompunerea cerut
6. Se citete un numr natural n. S se descompun ca sum de puteri cresctoare ale lui 2. Se vor folosi doar prelucrri / calcule realizate cu ajutorul funciilor implementate recursiv.
7. Scriei un subprogram recursiv care descompune un numr în factori primi.
8. Se d un numr natural n. S se determine dac n este palindrom (egal cu rsturnatul su), utilizând recursivitatea.
9. Scriei un program care transform un numr natural n din baza 10 în baza b (1<b<10). Se va folosi un subprogram recursiv care calculeaz i returneaz numrul în baza b.
10. Se citete de la tastatur, caracter cu caracter, un ir de caractere. Citirea se încheie la întâlnirea caracterului $. Folosind un algoritm recursiv, s se afieze în ordine invers citirii, cifrele care apar în ir.
· Clasa a XI-a, matematic-informatic
Colegiul Naional „Gib Mihescu”, Drgani
1. Ce afieaz subprogramul F, descris mai jos, la apelul F(5)?
void F(int x){
}
2. Se consider subprogramul recursiv descris mai jos incomplet. Cu ce valoare trebuie înlocuite punctele de suspensie pentru ca funcia s returneze cifra minim a numrului natural nenul transmis prin parametrul x?
int Min(int x){
if(x==0)return ......; else{
}}
void F(int x){
}}
4. Se consider subprogramul F definit mai jos. Ce se va afia în urma apelului F(’a ’)?
void F(char c)
}}
5. Pentru definiia de mai jos a subprogramului f, ce valoare are f(132764)?
int f(long n)
}
6. Pentru definiia de mai jos a subprogramului f, ce valoare are f(100)?
int f(int x)
}
7. Scriei o funcie recursiv care calculeaz i afieaz suma primelor n numere prime.
Exemplu:
OBSERVAIE:
Toate subiectele sunt obligatorii. Primele 6 subiecte au câte un punct fiecare, iar problema 7 are 3 puncte. Se acord un punct din oficiu. Timp de rezolvare: 50 de minute.
· Clasa a XI-a, matematic-informatic
Profesor Merlan Doina Narcisa
Colegiul Economic, Rm. Vâlcea
Metoda DIVIDE ET IMPERA aplicat pentru probleme care prelucreaz vectori (cu n elemente), presupune împrirea succesiv a vectorului în 2 subvectori de lungime egal (iniial se obin subvectori de lungime n/2), pân se obine un vector cu un singur element.
Vectorul iniial: x=(x1, x2, ..., xk, xk+1, ..., xn), unde k=(n+1)/2
La prima împrire a vectorului se obin subvectorii: (x1, x2, ..., xk) i (xk+1, ..., xn)
Rezolvarea unei probleme cu metoda DIVIDE ET IMPERA presupune:
· rezolvarea celor 2 subprobleme (în cazul nostru: prelucrarea celor 2 subvectori)
· combinarea celor 2 soluii pentru a obine soluia problemei iniiale (soluia final a problemei).
Putem considera c, la un moment dat (un anumit pas), se lucreaz cu vectorul:
(xli, xli+1, ..., xls), unde:
· li= limita inferioar a indicilor subvectorului curent;
· ls= limita superioar a indicilor subvectorului curent;
· k=(li+ls)/2.
Se continu împrirea în subprobleme (subvectori) pân când se ajunge la cea mai simpl problem (vector cu un singur element, adic li=ls).
Pentru rezolvarea celor 2 subprobleme (în cazul nostru, prelucrarea celor 2 subvectori) i combinarea celor 2 soluii, se folosete RECURSIVITATEA.
Cazul particular care se rezolv în mod direct (fr autoapel) este: li=ls (s-a ajuns la un subvector cu un singur element).
Cazul general, adic în cazul în care li!=ls, se parcurg paii:
· se rezolv subproblema S1 - pentru prima jumtate a vectorului (autoapel cu parametrii li i k);
· se rezolv subproblema S2 - pentru a doua jumtate a vectorului (autoapel cu parametrii k+1 i ls);
· se combin cele dou soluii obinute pentru S1, respectiv pentru S2 i se obine soluia problemei
PROBLEME REZOLVATE
Considerm c datele de intrare sunt vectorul x i n (numrul de elemente), declarate ca variabile globale (la începutul programului), la care se adaug datele specifice problemei.
Pentru citirea datelor de intrare se folosete funcia citire de tip void, fr parametri:
void citire()
· PROBLEMA 1
Se consider un vector cu n (n ≤ 25) elemente numere reale citite de la tastatur. S se verifice dac toate elementele vectorului sunt în ordine strict descresctoare.
Rezolvare:
Se consider vectorul x cu n (n ≤ 25) elemente numere reale citit de la tastatur.
Spunem c elementele vectorului x sunt în ordine strict descresctoare dac toi subvectorii au elementele în ordine strict descresctoare, adic: x1>x2>x3> ... >xn
Conform Divide et Impera: spunem c elementele vectorului sunt în ordine strict descresctoare dac cei 2 subvectori au elementele în ordine strict descresctoare, adic: xli>xli+1>xli+2>...>xk i xk+1>xk+2>...>xls. Vom folosi funcia descresc cu 2 parametri: li (limita inferioar a indicilor) i ls (limita superioar a indicilor).
Cazul particular care se rezolv în mod direct: pentru li=ls spunem c elementele vectorului sunt în ordine strict descresctoare (un singur element este ordonat cum vrem noi).
În funcia Main se face apelul funciei astfel: descresc(1,n)
Programul C++ corespunztor:
void citire()
cout<<”elemente vector:”;
}
{
else
else
return 0;
· PROBLEMA 2
Se consider un vector n (n ≤ 20) elemente numere reale i o valoare y (numr real) citite de la tastatur. S se verifice dac y aparine vectorului.
Rezolvare:
Se consider vectorul x cu n (n ≤ 20) elemente numere reale i o valoare y (numr real) citite de la tastatur.
Spunem c valoarea y aparine vectorului dac se regsete printre elementele vectorului, adic: xli=y sau xli+1=y sau xli+2=y ... sau xk=y sau xk+1=y ... sau xls=y .
Conform Divide et Impera: spunem c valoarea y aparine vectorului x dac valoarea y aparine unuia din cei 2 subvectori, adic:
xli=y sau xli+1=y sau xli+2=y... sau xk=y, respectiv xk+1=y sau xk+2=y ... sau xls=y
Pentru rezolvarea cerinei se folosete funcia apartine cu 2 parametri: li (limita inferioar a indicilor) i ls (limita superioar a indicilor).
Cazul particular care se rezolv în mod direct: pentru li=ls spunem c valoarea y aparine vectorului dac x[li]==y.
În funcia Main se face apelul funciei astfel: apartine(1,n)
Programul C++ corespunztor:
void citire()
{
else return 0;}
}
}
return 0;
· PROBLEMA 3
Se consider un vector cu n (n ≤ 25) elemente numere naturale citit de la tastatur. S se calculeze suma elementelor impare de 3 cifre.
Rezolvare:
Se consider vectorul x cu n (n ≤ 25) elemente numere naturale citite de la tastatur.
Suma elementelor impare de 3 cifre din vector se refer la acele elemente care îndeplinesc condiiile: au 3 cifre (între 100 i 999) i sunt impare (restul împririi la 2 este 1).
Conform Divide et Impera: suma elementelor impare de 3 cifre din vectorul curent este S1+S2, unde:
· Vectorul curent este: (xli, xli+1, ..., xls)
· Primul subvector este: (xli,xli+1,xli+2,...,xk)
· Al doilea subvector este: (xk+1,xk+2,...,xls)
· S1= suma elementelor impare de 3 cifre din primul subvector
· S2= suma elementelor impare de 3 cifre din al doilea subvector
Pentru rezolvarea cerinei se folosete funcia suma cu 2 parametri: li (limita inferioar a indicilor) i ls (limita superioar a indicilor).
Cazul particular care se rezolv în mod direct: pentru li=ls suma este x[li] dac x[li]>=100 && x[li]<=999 && x[li]%2==1.În caz contrar, suma este 0.
În funcia Main se face apelul funciei astfel: suma(1,n)
Programul C++ corespunztor:
void citire()
cout<<”elemente vector:”;
for(i=1;i<=n;i++)
cin>>x[i];
{
{if(x[li]>=100 && x[li]<=999 && x[li]%2==1)
return x[li];
int main()
· PROBLEMA 4
Se consider un vector cu n (n ≤ 20) elemente numere naturale i 2 numere naturale a i b citite de la tastatur. S se determine câte numere din ir aparin intervalului [a, b].
Rezolvare:
Se consider vectorul x cu n (n ≤ 20) elemente numere naturale i valorile naturale a i b citite de la tastatur.
Numrul elementelor din vector care aparin intervalului [a, b] se refer la acele elemente care îndeplinesc condiia: sunt numere între a i b.
Conform Divide et Impera: numrul elementelor care aparin intervalului [a, b] din vectorul curent este Nr1+Nr2, unde:
· Vectorul curent este: (xli, xli+1, ..., xls)
· Primul subvector este: (xli,xli+1,xli+2,...,xk)
· Al doilea subvector este: (xk+1,xk+2,...,xls)
· nr1= numrul elementelor care aparin intervalului [a, b] din primul subvector
· nr2= numrul elementelor care aparin intervalului [a, b] din al doilea subvector
Pentru rezolvarea cerinei se folosete funcia nr_ab cu 2 parametri: li (limita inferioar a indicilor) i ls (limita superioar a indicilor).
Cazul particular care se rezolv în mod direct: pentru li=ls numrul elementelor este 1 dac x[li]>=a && x[li]<=b. În caz contrar, numrul este 0.
În funcia Main se face apelul funciei astfel: nr_ab(1,n)
Programul C++ corespunztor:
void citire()
cout<<”elemente vector:”;
for(i=1;i<=n;i++)
cin>>x[i];
{
return 1;
else
return 0;
· PROBLEMA 5
Se consider un vector cu n (n ≤ 30) elemente numere reale citite de la tastatur. S se calculeze suma numerelor pozitive care se afl pe poziii pare în vector.
Rezolvare:
Se consider vectorul x cu n (n ≤ 30) elemente numere reale citite de la tastatur.
Suma elementelor pozitive de pe poziii pare din vector se refer la acele elemente care îndeplinesc condiiile: sunt pozitive ( >0) i se afl pe poziii pare în vector (restul împririi la 2 al indicelui elementului vectorului este 0).
Conform Divide et Impera: suma elementelor pozitive de pe poziii pare în vectorul curent este S1+S2, unde:
· Vectorul curent este: (xli, xli+1, ..., xls)
· Primul subvector este: (xli,xli+1,xli+2,...,xk)
· Al doilea subvector este: (xk+1,xk+2,...,xls)
· S1= suma elementelor pozitive de pe poziii pare din primul subvector
· S2= suma elementelor pozitive de pe poziii pare din al doilea subvector
Pentru rezolvarea cerinei se folosete funcia suma cu 2 parametri: li (limita inferioar a indicilor) i ls (limita superioar a indicilor).
Cazul particular care se rezolv în mod direct: pentru li=ls suma este x[li] dac x[li]>0 && li%2==0.În caz contrar, suma este 0.
În funcia Main se face apelul funciei astfel: suma(1,n).
Programul C++ corespunztor:
void citire()
{
{
· PROBLEMA 6
Se consider un vector cu n (n ≤ 20) elemente numere naturale i 2 numere naturale a i b citite de la tastatur. S se numere câte elemente ale vectorului au proprietatea c împrite la a, dau restul b.
Rezolvare:
Se consider vectorul x cu n (n ≤ 20) elemente numere naturale i valorile naturale a i b citite de la tastatur.
Numrul elementelor din vector cu proprietatea c împrite la a, dau restul b.
Conform Divide et Impera: numrul elementelor cu proprietatea c împrite la a, dau restul b din vectorul curent este Nr1+Nr2, unde:
· Vectorul curent este: (xli, xli+1, ..., xls)
· Primul subvector este: (xli,xli+1,xli+2,...,xk)
· Al doilea subvector este: (xk+1,xk+2,...,xls)
· Nr1= numrul elementelor care împrite la a, dau restul b din primul subvector
· Nr2= numrul elementelor care împrite la a, dau restul b din al doilea subvector
Pentru rezolvarea cerinei se folosete funcia nr_ab cu 2 parametri: li (limita inferioar a indicilor) i ls (limita superioar a indicilor).
Cazul particular care se rezolv în mod direct: pentru li=ls numrul elementelor este 1 dac x[li]%a==b. În caz contrar, numrul este 0.
În funcia Main se face apelul funciei astfel: nr_ab(1,n).
Programul C++ corespunztor:
void citire()
{
else return 0;
}
if(nr>0)
cout<<”Nr. el. care împrite la ”<<a<<”, dau restul ”<<b<<=”<<nr;
else
cout<<”Nu exista elemente care împrite la a, dau restul b.”;
return 0;
Profesor Catarag tefania Issabella
Colegiul Naional „Alexandru Lahovari”, Rm. Vâlcea
Metoda Greedy (greedy = lacom), denumit i metoda optimului local, reprezint o metod de programare utilizat în probleme de optimizare i care furnizeaz o singur soluie (optimul global) care este obinut prin alegeri succesive ale optimului local.
Algoritmii de tip greedy, asemenea algoritmilor backtracking i de programare dinamic se utilizeaz pentru rezolvarea unor probleme a cror soluie se poate exprima sub forma unui vector de numere întregi. În comparaie cu metoda backtracking, metoda Greedy nu va determina toate soluiile problemei. Metoda va gsi doar o singur soluie i, în general soluia gsit este soluia optim.
Metoda se aplic problemelor în care se d o mulime A cu n elemente i trebuie determinat o submulime a sa, S cu m elemente, care îndeplinesc anumite condiii. Algoritmul va determina la fiecare pas k o component x[k] a vectorului soluie i spre deosebire de algoritmul backtracking, nu mai revine ulterior la aceast alegere. Pentru ca elementele care se selecteaz s aparin soluiei optime, la pasul k se va alege candidatul care este optim pentru elementul x[k] al soluiei deci un optim local.
Paii metodei greedy sunt:
1. se iniializeaz mulimea soluiilor S cu mulimea vid, S=Ø;
2. la fiecare pas se alege un anumit element x∈A, candidatul optim la momentul respectiv, care poate conduce la o soluie optim;
3. se verific dac elementul ales poate fi adugat la mulimea soluiilor:
· dac se poate aduga, atunci va fi adugat i mulimea soluiilor devine S=S ∪ {x}- un element introdus în mulimea S nu va mai putea fi eliminat;
· dac nu se poate aduga, el nu se mai testeaz ulterior.
4. procedeul continu, pân când au fost determinate toate elementele din mulimea soluiilor.
Structura general a unei aplicaii greedy:
Sol = Ø;
Alege x A;
Dac este posibil atunci Sol Sol + x; Pân când am obinut soluia
Afieaz Sol;
· De regul metoda greedy are o complexitate de O (n k).
· Exist destul de puine probleme pentru care se poate aplica aceast metod.
· Metoda greedy se aplic atunci când tim c se ajunge la soluia dorit.
1. SUM MAXIM
Se d o mulime A={a1, a2, . . ., an} cu elemente reale. S se determine o submulime a lui S astfel încât suma elementelor submulimii s fie maxim.
Rezolvare: Se vor cuta între elementele vectorului A doar elementele mai mari sau egale cu 0. Se va utiliza un subprogram greedy ( ) pentru implementarea algoritmului.
#include <iostream>
void greedy( )
if ( A[ i ] >= 0 )
cout << endl <<" Elementele vectorului " << endl ;
for ( i = 1 ; i <= n ; i++ )
{ cout <<"A[" <<i<<"] = "; cin >> A[ i ] ;}
greedy();
for ( i= 1; i <= m ;i ++ ) cout << S [ i ] <<' ';
return 0; }
2. Se d o mulime A={a1, a2, . . ., an} cu elemente întregi. S se determine cele mai mari dou elemente ale mulimii.
#include <iostream>
#include<fstream>
}
3. PROBLEMA PLANIFICRII SPECTACOLELOR
Într-o sal de spectacol trebuie planificate n spectacole într-o zi. Pentru fiecare spectacol se cunosc ora de început i ora de terminare (numere întregi). S se planifice un numr maxim de spectacole astfel încât s nu fie doua spectacole care s se suprapun.
Rezolvare:
Pas 1 - Se sorteaz spectacolele dup ora terminrii lor;
Pas 2 - Primul spectacol ales este cel care se termin cel mai devreme;
Pas 3 - Se alege primul spectacol care îndeplinete condiia c începe dup ce s-a terminat ultimul spectacol programat;
Pas 4 - Dac nu s-a gsit un asemenea spectacol atunci algoritmul se termin altfel se programeaz spectacolul gsit i se reia pasul 3.
Exemplu: fiierul date.in conine pe prima linie numrul de spectacole i apoi ora de începere i ora de terminare pentru fiecare spectacol:
8
Rezolvare:
{ int s,d; };
{
}
{
{
{
}
{
s[++k]=a[i];
4. PROBLEMA RUCSACULUI (CAZUL CONTINUU)
O persoan are un rucsac cu care poate transporta o greutate maxim g. Persoana are la dispoziie n obiecte pentru care se cunosc greutatea i câtigul obinut. S se precizeze ce obiecte trebuie s transporte persoana astfel încât câtigul total s fie maxim i s nu se depeasc greutatea maxim a rucsacului.
Rezolvare:
· se determin pentru fiecare obiect eficiena de transport (raportul dintre câtig i greutate)
· se ordoneaz obiectele în ordine descresctoare a eficienei de transport
· atâta timp cât nu s-a atins greutatea maxim a rucsacului i nu au fost luate în considerare toate obiectele, se va selecta obiectul cu eficiena de transport maxim existând dou situaii:
- obiectul încape în totalitate în rucsac, caz în care se va scdea din greutatea rmas de încrcat greutatea obiectului i se adun la câtig, câtigul obinut din transportul obiectului adugat;
- obiectul nu încape în totalitate în rucsac, deci se va determina partea care poate fi transportat, se adun câtigul obinut din transportul acestei pri i se tiprete procentul care s-a încrcat din obiect.
Exemplu:
g=3 n=3 adic greutatea ce poate fi transportat este 3 i avem la dispoziie 3 obiecte.
obiectele (greutate, câtig):
1,4,1
3,6,0.6667 (al doilea obiect se încarc în raport de 2/3)
Câtig maxim obinut = 8
void citire(float &g, int &n, obiect a[])
{
a[i].r=0;//initial nu se foloseste obiectul
}
}
{
{
}
}
{
{
fout<<a[i].g<<","<<a[i].c<<","<<setprecision(4)<<a[i].r<<endl;
c=c+a[i].c*a[i].r;
}
{
s[++k]=a[i];
}
sp=g;
5. PROBLEMA COMIS-VOIAJORULUI
Un comis - voiajor pleac dintr-un ora, trebuie s viziteze un numr de orae i s se întoarc în oraul iniial cu un efort minim. Orice ora i este legat de un alt ora j printr-un drum de A[ i ][ j ] kilometri. S se determine traseul pe care trebuie s-l parcurg comis-voiajorul care s aib un numr minim de kilometri.
Rezolvare:
Se va alege un ora de pornire. La fiecare pas se va selecta un alt ora din cele neselectate pân acum i aflat la distan minim fa de oraul de pornire.
Algoritmul se încheie atunci când s-au selectat toate oraele.
#include<fstream>
int s[100],viz[100],n,x;
int a[100][100];
{
}
if(k==n)
}
În ceea ce privete complexitatea, se poate afirma c algoritmii de tip greedy sunt eficieni, operaia principal fiind cea de selecie a elementelor. Dac este necesar o ordonare a elementelor mulimii A atunci aceast operaie de sortare este cea mai costisitoare.
Ordinul de complexitate al algoritmilor de tip „greedy” poate fi O(n2) sau O(n lg n) sau O(n), în funcie de natura elementelor din A i algoritmul de sortare folosit.
6. Fiind dat o hart cu n ri, se cere o soluie de colorare a hrii, utilizând cel mult patru culori, astfel încât dou ri ce au frontiera comun s fie colorate diferit.
Exemplu:
Rezolvare:
void afisare()
fout<<endl;
if(a[i][k]==1 && x[i]==x[k]) return 0;
return 1;
a[t2][t1]=1;
}
7. Se citesc 3 numere naturale S, n i e cu urmtoarele semnificaii: S este o sum de bani care trebuie pltit folosind bancnote care au valori puterile lui e de la 1 la e la n. S se afieze modalitatea de plat folosind un numr minim de bancnote de tipurile precizate. S se afieze la final numrul de bancnote folosite.
Rezolvare:
int main()
{
t=t+S/p;
S=S % p;
}
8. Fiind dat o tabla de ah de dimensiunea n × n i un cal în colul stânga sus al acesteia, se cere s se deplaseze calul pe tabl astfel încât s treac o singur dat prin fiecare ptrat al tablei.
Rezolvare:
ifstream fin("date.in");
ofstream fout("date.out");
void afis()
fout<<endl;
}
{
}
{
else
{
}
}
}
}
Profesor Merlan Doina Narcisa
Colegiul Economic, Rm. Vâlcea
Backtracking este numele generic al unui „ algoritm  general de descoperire a tuturor soluiilor unei probleme de calcul, algoritm ce se bazeaz pe construirea incremental de soluii-candidat, abandonând fiecare candidat parial imediat ce devine clar c acesta nu are anse s devin o soluie valid.” ( https://ro.wikipedia.org )
Tehnica de programare Backtracking se poate aplica pentru problemele ce admit conceptul de „candidat parial al soluiei” i ofer un test relativ rapid asupra posibilitii ca un astfel de candidat s poat duce ctre o soluie valid (rezultat). Aceast metod este recomandat atunci când nu se dispune de o alt metod mai rapid de rezolvare, cunoscut fiind timpul mare de execuie al algoritmilor ce o implementeaz, având o complexitate exponenial.
În cazul în care mulimile S1, S2, …, Sn au acelai numr p de elemente, timpul necesar de execuie al algoritmului este O(pn). Dac mulimile S1, S2, …, Sn nu au acelai numr de elemente, atunci se noteaz cu „m” minimul cardinalelor mulimilor S1, S2, …, Sn si cu „M”, maximul. În aceast situaie, timpul de execuie este situat în intervalul [O(mn) , O(Mn)].
Când se poate aplica, îns, metoda Backtracking este adesea mult mai rapid decât cutarea printre toi candidaii posibili.
Cerina problemei se refer, de cele mai multe ori, la gsirea tuturor soluiilor, la gsirea numrului de soluii care satisfac anumite condiii, sau la gsirea unei singure soluii, care poate reprezenta un maxim sau un minim (dup gsirea acesteia se întrerupe execuia).
De obicei, metoda Backtracking se aplic problemelor în care soluia se poate prezenta sub forma unui vector x = (x1, x2, … ,xn), unde x1 S1, x2 S2, ..., xn Sn. Mulimile S1, S2, ... , Sn sunt finite, elementele lor fiind într-o relaie de ordine bine stabilit (de obicei reprezentând termenii unei progresii aritmetice) i se numesc mulimi de valori posibile. La modul general, spunem c xi Si, pentru i {1, … , n}, sau c x=(x1, x2, … ,xn) S1 x S2 x ... x Sn (spaiul soluiilor posibile).
Aceast metod evit generarea tuturor soluiilor posibile i apoi alegerea acelor soluii care conv