Programarearunceanu.ro/adrian/wp-content/cursuri/S2progr2014/curs3-PC.pdf · Programarea...

Programareacalculatoarelor

Universitatea “Constantin Brâncuşi” din Târgu-JiuFacultatea de Inginerie

Departamentul de Automatică, Energie şi Mediu

Lect.dr. Adrian Runceanu

[email protected]@www.adrian.runceanu.ro

Curs 3

Algoritmi(partea III)

25.03.2015 Curs - Programarea calculatoarelor 2


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]

In cadrul cursului 2 – Algortimi (parteaII) am prezentat exemple prinproblemele de la 1 pana la 8



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

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



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 intrare: n număr natural

Date de ieşire: s şi p, numere naturale




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.


[email protected]



Pas 3:

Scriereaalgoritmului în pseudocod:

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


2. ALGORITMI



cunoscut de pași



2.4. Algoritmi cu structura repetitivă cu test final

PROBLEMA 10Să se scrie un program care verifică dacă un număr n

este perfect sau nu.Un număr perfect este egal cu suma divizorilor lui,

inclusiv 1 (exemplu: 6 = 1 + 2 + 3).Exemplu:


Pentru n = 28, se va afişa mesajulNumar perfect (divizorii lui 28 sunt 1,2,4,7,14)



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

În cazul problemei date, avem:

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




Pas 2: Analiza problemei1) La începutul problemei, vom 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’.


[email protected]



Pas 3:

Scriereaalgoritmuluiîn pseudocod:

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

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

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

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



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

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.



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: n număr naturalDate de ieşire: numerele din şirul lui Fibonacci




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,iar apoi vom da:

valoarea b variabilei aşi valoarea c variabilei b


[email protected]



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



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.





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




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.


[email protected]



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


2. ALGORITMI



cunoscut de pași



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 celălălt ş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





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




Pas 2: Analiza problemei La î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 suma divizorilor primuluinumar este egala cu cel de-al doilea numar, iar sumadivizorilor celui de-al doilea numar este egala cu primulnumar.


[email protected]



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

[email protected]



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



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 nnumere naturale date.

Exemplu:


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





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

Date de ieşire: valoarea maximă




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

care vom reține valoarea maximă, cu o valoarefoarte mică.

Apoi, într-un ciclu repetitiv având n pași vomcompara, pe rând cele n valori citite de la tastaturăși vom reține de fiecare data valoarea mai maredecât cea din variabila max.

La sfârșit vom avea valoarea cea mai mare învariabila max.


[email protected]



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



PROBLEMA 15Să se calculeze suma numerelor naturale

cuprinse intre două numere date (dintr-uninterval deschis – fara capetele intervalului).

Exemplu:


Pentru 3 si 6 reprezentand capeteleintervalului, se va afisa valoarea 9reprezentand suma.





Date de intrare: a si b numere naturaleDate de ieşire: suma numerelor aflate in intervalul

(a,b)




Pas 2: Analiza problemei

La începutul problemei, vom iniţializa cu 0 o

variabilă, în care vom reține valoarea suma

numerelor din intervalul (a,b).

Apoi, într-un ciclu repetitiv pornind de la a+1 si

mergand pana la b-1 vom aduna la suma toate

valorile din intervalul dat.

La sfârșit vom avea valoarea suma.25.03.2015 Curs - Programarea calculatoarelor 34

[email protected]



Pas 3:


natural a, b, i, sumaciteşte a,bsuma<- 0pentru i=a+1,b-1 execută

suma <- suma + isfârșit pentruscrie sumastop


Probleme propuse spre rezolvare:

1) Să se afişeze primele n numere prime.

Exemplu:

25.03.2015 Programarea calculatoarelor 36

Date de intrare: n=6 Date de ieşire: 2 3 5 7 11



2) Se citesc n numere naturale strict pozitive. Săse numere cate dintre ele sunt pare.

Exemplu:


Date de intrare: n=5 si valorile 4, 3, 6, 5, 7, 7 Date de ieşire: 2 numere pare



3) Se introduce un număr natural cu maxim 9cifre. Să se determine şi să se afişeze numărul decifre, cea mai mare cifră, cea mai mică şi sumatuturor cifrelor acestui număr.Exemplu:


Date de intrare: 24356103 Date de ieşire: 8 cifremax=6 min=0 suma=24



4) Cate cifre impare sunt intr-un număr dat?

Exemplu:


Date de intrare: 34725376 Date de ieşire: 4 cifre


Întrebări?


Programarearunceanu.ro/adrian/wp-content/cursuri/S2progr2014/curs3-PC.pdf · Programarea...

Documents

Transcript of Programarearunceanu.ro/adrian/wp-content/cursuri/S2progr2014/curs3-PC.pdf · Programarea...