#2 C++ Algoritmi (Partea a II-a) Adrian Runceanu

Programarea calculatoarelor

#2

Adrian Runceanuwww.runceanu.ro/adrian

2016

C++Algoritmi (Partea a II-a)

[email protected]

Curs 2

Algoritmi(continuare)

02.11.2016 Curs - Programarea calculatoarelor 2

[email protected]

2. ALGORITMI

2.1. Algoritmi elementari (numai cu operatia de atribuire)

2.2. Algoritmi cu structura de decizie2.3. Algoritmi cu structura repetitivă cu test iniţial2.4. Algoritmi cu structura repetitivă cu test final2.5. Algoritmi cu structura repetitivă cu număr

cunoscut de pași


[email protected]

2.1. Algoritmi elementari

PROBLEMA 1 Să se calculeze perimetrul şi aria unui dreptunghi,

ştiind laturile sale.

Pas 1: Stabilim care sunt datele de intrare, adică cele carevor fi prelucrate cu ajutorul algoritmului, împreună cudatele de ieşire.

În cazul problemei date, avem:Date de intrare: l şi L numere reale ce reprezintă laturile

dreptunghiului.Date de ieşire: p şi A numere reale ce reprezintă

perimetrul, respectiv aria dreptunghiului.02.11.2016 Curs - Programarea calculatoarelor 4

[email protected]


Pas 2: Analiza problemeiStabilim condiţiile pe care trebuie să le

îndeplinească datele de intrare pentru a fi prelucrate încadrul algoritmului.

În cadrul problemei pe care o avem de rezolvat,cunoaştem formulele pentru calculul perimetrului,respectiv ariei unui dreptunghi dacă se stiu laturilesale:

Perimetru = 2*( latime + Lungime )Aria = latime * Lungime



Pas 3:Scriereaalgoritmului în pseudocod:


real l, L, p, A

citeşte l, L

p <- 2 * ( l + L )

scrie ‘Perimetrul dreptunghiului este ‘, p

A <- l * L

scrie ‘Aria dreptunghiului este’, A

stop

[email protected]

2.1. Algoritmi elementariPROBLEMA 2

Sa se calculeze si sa se afiseze valoarea distanteiintre doua puncte, dandu-se coordonatele acestora:A(x1, y1) si B(x2, y2).

Pas 1: Stabilim care sunt datele de intrare, adică cele care vor fi prelucrate cu ajutorul algoritmului, împreună cu datele de ieşire.

În cazul problemei date, avem:Date de intrare: x1, x2, y1 şi y2 numere reale ce reprezintă

coordonatele celor doua puncte.Date de ieşire: d = distanta intre cele doua puncte02.11.2016 Curs - Programarea calculatoarelor 7

[email protected]



îndeplinească datele de intrare pentru a fi prelucrateîn cadrul algoritmului.

În cadrul problemei pe care o avem de rezolvat,cunoaştem formula de calcul pentru aflareadistantei dintre doua puncte in plan:


)()()()( 21212121 yyyyxxxxd




real x1, x2, y1, y2, d

citeşte x1, y1, x2, y2

scrie ‘Distanta dintre cele doua puncteeste ’, d

stop

)21

()21

()21

()21

( yyyyxxxxd

[email protected]


PROBLEMA 3 Se dau două numere reale x şi y. Să se calculeze

următoarele expresii:A = 2 + x - yB = x * A + yC = A - 2 * B + x

Pas 1: Stabilim care sunt datele de intrare, şi ce tip de datereprezintă, împreună cu datele de ieşire.

În cazul problemei date, avem:Date de intrare: x şi y numere realeDate de ieşire: A, B şi C numere reale


[email protected]



îndeplinească datele de intrare pentru a fiprelucrate în cadrul algoritmului.

În cadrul problemei pe care o avem de rezolvat,cunoaştem formulele pentru fiecare expresie:

A = 2 + x - y B = x * A + yC = A - 2 * B + x





real x, y, A, B, C

citeşte x, y

A <- 2 + x - y

B <- x * A + y

C <- A - 2 * B + x

scrie ‘Valoarea expresiei A este ‘, A

scrie ‘Valoarea expresiei B este ‘, B

scrie ‘Valoarea expresiei C este ‘, C

stop

[email protected]

2. ALGORITMI

2.1. Algoritmi elementari numai cu operatia de atribuire)


cunoscut de pași


[email protected]

2.2. Algoritmi cu structura de decizie

PROBLEMA 4 Se dau trei numere întregi a, b si c. Să se scrie unalgoritm care să se determine maximul și minimulacestor valori.

Pas 1: Stabilim care sunt datele de intrare, adică cele carevor fi prelucrate cu ajutorul algoritmului, împreună cudatele de ieşire.

În cazul problemei date, avem:Date de intrare: a, b și c numere întregiDate de ieșire: min, respectiv max02.11.2016 Curs - Programarea calculatoarelor 14

[email protected]



îndeplinească datele de intrare pentru a fi prelucrate încadrul algoritmului.

i) Comparăm primele două numere (a și b). În funcție decare este mai mic sau mai mare am determinat minimulși maximul celor două valori.

ii) Comparăm valorile de minim, respectiv de maxim cu celde-al treilea număr si astfel vom determina cea maimică, respectiv cea mai mare valoare dintre cele treidate.


[email protected]


Pas 3:Scriereaalgoritmuluiîn pseudocod:


intreg a, b, c, min, max

citeşte a, b, c

dacă a < b atunci

min <- a

max <- b

altfel

min <- b

max <- a

sfârşit dacă

dacă c < min atunci

min <- c

sfarşit dacă

dacă c > max atunci

max <- c

sfarşit dacă

scrie min, max

stop


PROBLEMA 5Să se calculeze valoarea funcţiei f(x), ştiind că x este un număr real

introdus de la tastatură:

Pas 1: Stabilim care sunt datele de intrare, adică cele care vor fi prelucratecu ajutorul algoritmului, împreună cu datele de ieşire.

În cazul problemei date, avem:Date de intrare: x număr realDate de iesire: f număr real, reprezentând valoarea funcţiei date


0,2

]0,7(,30

]7,(,206

)(

xdacax

xdacax

xdacax

xf

[email protected]



îndeplinească datele de intrare pentru a fiprelucrate în cadrul algoritmului. Căutăm cazurileparticulare.

În cadrul problemei pe care o avem de rezolvat,verificăm condiţiile date în expresia funcţiei:

1) Dacă x <= -7, atunci funcţia are valoarea: -6x + 202) Daca x > -7 si x <= 0, atunci funcţia are valoarea:

x+303) Daca x > 0, atunci funcţia are valoarea: sqrt(x) + 2





real x, f

citeşte x

dacă x <= -7 atunci

f <- -6 * x + 20

altfel

dacă x > -7 şi x <= 0 atunci

f <- x + 30

altfel

f <- sqrt(x) + 2

sfârşit dacă

sfarşit dacă

scrie f

stop

[email protected]


PROBLEMA 6Să se citească trei valori naturale a, b și c. Să se scrie

un algoritm care să verifice dacă cele trei numere sunt sau nu numere pitagorice.

Precizare: Numim numere pitagorice, trei valori care îndeplinesc Teorema lui Pitagora, adică verifică una din condițiile:


222

222

222

bac

cab

cba

[email protected]



În cazul problemei date, avem:

Date de intrare: a, b și c numere naturale

Date de ieşire: mesaj corespunzător


[email protected]


Pas 2: Analiza problemeiStabilim condiţiile pe care trebuie să le îndeplinească

datele de intrare pentru a fi prelucrate în cadrulalgoritmului.

În cadrul problemei pe care o avem de rezolvat,verificăm condiţiile care trebuie îndeplinite de cele treivalori:

1) Dacă 𝒂𝟐 = 𝒃𝟐 + 𝒄𝟐, atunci sunt numere pitagorice.Sau2) Daca 𝒃𝟐 = 𝒂𝟐 + 𝒄𝟐, atunci sunt numere pitagorice.Sau3) Daca 𝒄𝟐 = 𝒂𝟐 + 𝒃𝟐, atunci sunt numere pitagorice.02.11.2016 Curs - Programarea calculatoarelor 22

[email protected]


Pas 3:Scriereaalgoritmuluiîn pseudocod:


natural a,b,cciteşte a,b,cdacă 𝑎2 = 𝑏2 + 𝑐2 atunci

scrie ‘Numere pitagorice’altfel

dacă 𝑏2 = 𝑎2 + 𝑐2 atunciscrie ‘Numere pitagorice’

altfeldacă 𝑐2 = 𝑎2 + 𝑏2 atunci


scrie ‘NU SUNT nr. pitagorice’sfârşit dacă

sfarşit dacăsfarşit dacăstop

[email protected]


Varianta II-aPas 3:

Scriereaalgoritmuluiîn pseudocod:


natural a,b,cciteşte a,b,cdacă 𝑎2 = 𝑏2 + 𝑐2 sau 𝑏2 = 𝑎2 + 𝑐2 sau 𝑐2 = 𝑎2 + 𝑏2 atunci


scrie ‘NU SUNT nr. pitagorice’sfarşit dacăstop

[email protected]

2. ALGORITMI



cunoscut de pași


[email protected]

2.3. Algoritmi cu structura repetitivă cu test iniţial

PROBLEMA 7

Să se citească un număr natural n. Să se scrie un algoritm care afişează toţi divizorii numărului dat.

Exemplu:


Pentru n = 12, mulţimea divizorilor este formată din valorile 1, 2, 3, 4, 6, 12.

[email protected]




Date de intrare: n număr natural

Date de ieşire: divizorii numărului n


[email protected]


Pas 2: Analiza problemeiÎn cadrul problemei pe care o avem de rezolvat,

verificăm condiţia ca un număr să fie divizor al altui număr şi anume:

i este divizor al numărului n dacă se împarte exact la el, adică dacă este adevărată expresia n % i = 0.

Pentru a găsi toţi divizorii numărului n dat, vom da valori lui i, pornind de la valoarea 1 până la valoarea n.

Deci vom utiliza o structură repetitivă.




Pas 3:

Scriereaalgoritmului în pseudocod:

natural n, iciteşte ni <- 1cât timp i <= n execută

dacă n % i = 0 atunciscrie i

sfârşit dacăi <- i + 1

sfârşit cât timpstop

[email protected]


PROBLEMA 8Să se citească un număr natural n. Să se scrie unalgoritm care verifică dacă numărul dat este sau nunumăr prim.Un număr n este prim dacă are ca divizori doarvalorile 1 şi n.

Exemplu:


Pentru n = 7, se va afişa mesajul ‘numărul este prim’,

iar pentru n = 22, se va afişa mesajul ‘numărul NU

este prim’.

[email protected]


Pas 1: Stabilim care sunt datele de intrare, adică

cele care vor fi prelucrate cu ajutorul

algoritmului, împreună cu datele de ieşire.



Date de ieşire: număr prim sau nu


[email protected]


Pas 2: Analiza problemei:1) Vom presupune, la începutul problemei, că numărul n dateste prim, şi vom specifica acest lucru cu ajutorul uneivariabile de tip logic, căreia îi vom da valoarea ‘adevărat’.2) Apoi vom evalua, pe rând, toate valorile începând cuvaloarea 2 şi până la n-1, ca să determinăm dacă sunt divizoriai numărului n dat.3) Dacă găsim un singur divizor printre aceste numere, atuncivom acorda valoarea ‘fals’ variabilei de tip logic de laînceputul algoritmului.4) La sfârşit vom verifica care este valoarea variabilei de tiplogic şi vom afişa un mesaj corespunzător.




Pas 3:


natural n, ilogic pciteşte np <- adevărati <- 2cât timp i <= n-1 execută

dacă n % i = 0 atuncip <- fals


sfârşit cât timpdacă p = adevărat atunci

scrie ‘Numarul este prim’altfel

scrie ‘Numarul NU este prim’sfârşit dacăstop

[email protected]


PROBLEMA 9Să se calculeze suma şi produsul primelor nnumere naturale, n fiind introdus de latastatură.

Exemplu:


Pentru n = 5, se vor afişa valoriles = 1 + 2 + 3 + 4 + 5 = 15p = 1 * 2 * 3 * 4 * 5 = 120

[email protected]


Pas 1: Stabilim care sunt datele de intrare, adicăcele care vor fi prelucrate cu ajutorulalgoritmului, împreună cu datele de ieşire. Încazul problemei date, avem:


Date de ieşire: s şi p


[email protected]


Pas 2: Analiza problemeiLa începutul problemei, vom iniţializa două

valori, s pentru sumă cu 0 şi p pentru produs cu1.

Apoi vom verifica, pe rând, toate valorilenaturale de la 1 la n şi le vom însuma, respectivînmulţi.

Soluţiile obţinute le vom afişa.




Pas 3:


natural n, i, s, pciteşte ns <- 0p <- 1i <- 1cât timp i <= n execută

s <- s + ip <- p * ii <- i + 1

sfârşit cât timpscrie ‘Suma numerelor este’, sscrie ‘Produsul numerelor este’, pstop

[email protected]

2. ALGORITMI



cunoscut de pași


[email protected]

2.4. Algoritmi cu structura repetitivă cu test final

PROBLEMA 10

Să se scrie un program care verifică dacă unnumăr n este perfect sau nu.Un număr perfect este egal cu suma divizorilor lui,inclusiv 1 (exemplu: 6 = 1 + 2 + 3), mai putin el însuși.

Exemplu:


Pentru n = 28, se va afişa mesajulNumar perfect (divizorii lui 28 sunt

1,2,4,7,14)

[email protected]


Pas 1: Stabilim care sunt datele de intrare, adicăcele care vor fi prelucrate cu ajutorulalgoritmului, împreună cu datele de ieşire.


Date de intrare: n număr naturalDate de ieşire: mesaj corespunzător


[email protected]


Pas 2: Analiza problemei1) La începutul problemei, vom verifica initializa o

variabila de tip suma cu valoarea 0.2) Pentru fiecare valoare i de la 1 la n-1 o vom

verifica dacă i este divizor al numarului n. Dacaeste divizor atunci il insumam la valoarea s.

3) Verificam daca suma obtinuta este egala cunumarul n. Daca da atunci scriem mesajul‘Numarul este perfect’.




Pas 3:


natural n, i, sciteşte ni <- 1s<- 0repetă

dacă n % i = 0 atuncis <- s + i


până când i > n-1dacă s = n atunci

scrie ‘Numarul este perfect’altfel

scrie ‘Numarul NU este perfect’sfârşit dacăstop

[email protected]


PROBLEMA 11Fie şirul lui Fibonacci, definit astfel:f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) în cazul în care

n>1.Să se scrie un algoritm care implementează

valorile şirului lui Fibonacci.

Exemplu:


Pentru n = 7, se vor afişa valorile 1, 1, 2, 3, 5, 8, 13.

[email protected]



În cazul problemei date, avem:Date de intrare: n număr natural

Date de ieşire: numerele din şirul lui Fibonacci


[email protected]


Pas 2: Analiza problemeiLa începutul problemei, vom iniţializa două

valori (a şi b) cu primele două elemente aleşirului lui Fibonacci, adică cu valori de 1.

Apoi, într-un ciclu repetitiv vom calcula cuajutorul unei a treia valori (variabila c) suma lorşi vom da următoarele valori variabilelor a şi b.




Pas 3:


natural n, i, a, b, cciteşte ni <- 1a <- 1b <- 1repetă

c <- a + bscrie ca <- bb <- ci <- i + 1

până când i > n-2stop

[email protected]


PROBLEMA 12Fie un număr natural n de cinci cifre. Să se

scrie un algoritm care să calculeze suma cifrelornumărului dat.

Exemplu:


Pentru n = 2178, se va afişa valoareas = 2+1+7+8=18.

[email protected]




Date de intrare: n număr naturalDate de ieşire: s = suma cifrelor


[email protected]


Pas 2: Analiza problemeiLa începutul problemei, vom iniţializa

valoarea sumei cifrelor numărului n dat cu 0.Apoi, într-un ciclu repetitiv vom calcula

suma cifrelor numărului, ştiind că o cifră a unuinumăr scris în baza 10 este dată de n%10, iarcâtul este dat de n/10.




Pas 3:


natural n, sciteşte ns <- 0repetă

s <- s + n%10n <- n/10

până când n = 0scrie sstop

Numarulfara ultima

cifra

Ultimacifra a lui n

[email protected]

2. ALGORITMI



cunoscut de pași


[email protected]

2.5. Algoritmi cu structura repetitivă cu număr cunoscut de pași

PROBLEMA 13Se citesc două numere întregi a şi b. Să se realizeze

in pseudocod un algoritm care să verifice dacă cele douanumere sunt prietene.

Spunem ca două numere sunt prietene dacă sumadivizorilor proprii ai unui număr este egală cu celalalt şiinvers.

Exemplu:


Pentru n = 220, si m = 284 se vor afişa valorileDivizorii lui 220, sunt 1, 2, 4, 5, 10, 11, 20, 22,44, 55 și 110Divizorii lui 284, sunt 1, 2, 4, 71 și 142

[email protected]




Date de intrare: n si m numere naturaleDate de ieşire: numerele sunt sau nu prietene


[email protected]


Pas 2: Analiza problemeiLa începutul problemei, vom iniţializa valoarea unei

variabile pentru suma divizorilor lui n cu 0, iar apoivaloarea unei variabile pentru suma divizorilor lui m cu 0.

Apoi, într-un ciclu repetitiv avand n/2 pasi vom calculasuma divizorilor lui n.

Apoi, într-un ciclu repetitiv avand m/2 pasi vom calculasuma divizorilor lui m.

La sfarsit vom verifica daca cele suma divizorilorprimului numar este egala cu cel de-al doilea numar, iarsuma divizorilor celui de-al doilea numar este egala cuprimul numar.




Pas 3:


natural n, m, i, j, suma_n, suma_mciteşte nsuma_n <- 0pentru i=1,n/2 execută

daca n%i=0 atuncisuma_n <- suma_n + i

sfârșit dacasfârșit pentru



Pas 3:


suma_m <- 0pentru j=1,m/2 execută

dacă m%j=0 atuncisuma_m <- suma_m + j

sfârșit dacăsfârșit pentrudacă suma_n = m AND suma_m=natunci

scrie “Numere prietene”altfel

scrie “Numere neprietene”sfârșit dacăstop

[email protected]


PROBLEMA 14Se citesc pe rând, n numere naturale. Să se

realizeze, în pseudocod, un algoritm care sădetermine cel mai mare număr dintre cele ndate.

Exemplu:


Pentru n = 10, si valorile următoare:-2, 12, 56, -123, 34, 7, -45, 90, 23, 6 Valoarea maximă este 90

[email protected]




Date de intrare: n număr natural, n numerenaturale

Date de ieşire: valoarea maximă


[email protected]


Pas 2: Analiza problemeiLa începutul problemei, vom iniţializa o variabilă, în

care vom reține valoarea maximă, cu o valoare foartemica, arbitrar aleasă.

Apoi, într-un ciclu repetitiv având n pași vomcompara, pe rând cele n valori citite de la tastatură și vomreține de fiecare valoare mai mare decât cea din variabilamax.

La sfârșit vom avea valoarea cea mai mare în variabilamax.




Pas 3:


natural n, i, max, xciteşte nmax <- -10000pentru i=1,n execută

citește xdaca x>max atunci

max <- xsfârșit daca

sfârșit pentruscrie maxstop

[email protected]

Alte probleme propuse spre rezolvare

EnuntCe citesc trei numere naturale nenule. Sa se

verifice daca ele coincid chiar cu valorile 1, 2, si 3.Exemplu:


Pentru n = 10, si valorile următoare:-2, 12, 56, -123, 34, 7, -45, 90, 23, 6 Valoarea maximă este 90

[email protected]




Date de intrare: a,b,c numere natural nenuleDate de ieşire: mesaj corespunzator


[email protected]


Pas 2: Analiza problemei

Pentru a identifica daca cele trei numere citite sunt

chiar egale cu valorile 1, 2 si 3, putem verifica acest

lucru intr-un mod simplu.

Calculam suma si produsul lor si daca obtinem

pentru fiecare din cele doua valori astfel calculate,

valoarea 6, atunci am gasit rezultatul dorit.




Pas 3:


natural a, b, c, s, pciteste a, b, cs <- a + b + cp <- a * b * cdaca s = 6 si p = 6 atunci

scrie ‘Numerele citite sunt chiar 1, 2 si3’altfel

scrie ‘Numerele citite un sunt egale cu 1,2 si 3’sfarsit dacastop

[email protected]


Problema 2:Se citesc trei numere a,b,c. Sa se verifice daca aceste numere (puse in orice odine) sunt in progresie aritmetica si sa se afiseze ratia progresiei in caz afirmativ.

Problema 3:Se dau trei numere a,b,c. Sa se verifice daca pot reprezenta laturile unui triunghi. In caz afirmativ sa se precizeze ce tip de triunghi este: echilateral, isoscel, dreptunghic sau oarecare.02.11.2016 Curs - Programarea calculatoarelor 65

[email protected]

Referinte bibliograficeBibliografia necesară cursului:

1. Adrian Runceanu, Mihaela Runceanu, Noțiuni de programare înlimbajul C++, Academica Brâncuşi, Târgu-Jiu, 2012, ISBN 978-973-144-550-2, 483 pagini

2. Adrian Runceanu, Programarea şi utilizarea calculatoarelor,Editura Academică Brâncuși Targu-Jiu, 2003

3. Octavian Dogaru, C++ - Teorie şi practică, volumul I, EdituraMirton, Timişoara, 2004

4. O.Catrina, I.Cojocaru, Turbo C+, Editura Teora, Bucureşti, 19935. D.Costea, Iniţiere în limbajul C, Editura Teora, Bucureşti, 19966. K.Jamsa, C++, Editura Teora,19997. K.Jamsa & L.Klander, Totul despre C si C++, Teora, 2004

02.11.2016 Programarea Calculatoarelor - curs 66

[email protected]

Întrebări?


#2 C++ Algoritmi (Partea a II-a) Adrian Runceanu

Documents

Transcript of #2 C++ Algoritmi (Partea a II-a) Adrian Runceanu