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)
[email protected]
c)
[email protected]
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