asd13algiterlab

Algoritmi si structuri de date (5-6.11.2014) Informatica&Matematic, anul 1 ASD13AlgIterLab

1

ALGORITMI ITERATIVI (continuare) R1. Enunul problemei: S se descrie un algoritm pentru determinarea tuturor ptratelor perfecte mai mici sau egale cu nN* dat. Metoda de rezolvare: O metod ar fi s parcurgem toate numerele de la 0 la n i s testm

dac acestea sunt ptrate perfecte sau nu ( Ni? ii

?][ = ).

O alt metod: i=? astfel nct i2n este echivalent cu i=? astfel nct 1 i [ n ], astfel c este suficient s parcurgem toate numerele naturale i ntre 1 i [ n ] i s afim i2. Descrierea algoritmului n pseudocod: citeste n *presupunem n1 pentru i = 0, [ n ], 1 repeta

scrie i2 Descrierea algoritmului n C++ (CodeBlocks):

#include //#include //pt sqrt using namespace std; int main() { int n,i; coutn; cout

Algoritmi si structuri de date (5-6.11.2014) Informatica&Matematic, anul 1 ASD13AlgIterLab

2

Descrierea algoritmului 1 n pseudocod: citeste n *presupunem n1 S 0 pentru k = 1, n repeta kfact 1 pentru i = 2, k repeta *i=1 a fost omis kfact kfact * i *pentru a nu mai inmulti cu 1

S S + kfact scrie S

Algoritmul anterior calculeaz fiecare factorial de la capt (12k). Dar innd cont c la un moment dat, adugm un factorial, la urmtorul nu ar trebui dect s nmulim cu k curent (k! = (k-1)! k). Acest lucru se aplic la orice algoritm n care termenul curent al sumei se poate scrie (n ntregime sau parial) n funcie de termenul anterior (n ntregime sau parial):

S = 1! + 2! + 3! + ...+ n! ==

n

kk

1!, iar k! = (k-1)! k, pentru k1 (reamintim 0! = 1).

Descrierea algoritmului 2 n pseudocod: citeste n *presupunem n1 S 0 *initializarea sumei cu 0 kfact 1 *initializarea termenului curent al sumei cu 1 pentru k = 1, n repeta kfact kfact * k S S + kfact

scrie S Se mai poate optimiza algoritmul anterior, prin iniializarea sumei cu primul termen, apoi k ncepe de la valoarea 2. Descrierea algoritmului n C++ (CodeBlocks):

#include #include using namespace std; int main() { int n,k; float S=1,kfact=1; //declarare si initializare //am inclus in suma deja 1! //factorilele este bine sa fie memorate in tip de date float coutn; //presupunem ca for (k=2;k

Algoritmi si structuri de date (5-6.11.2014) Informatica&Matematic, anul 1 ASD13AlgIterLab

3

Descrierea algoritmului n pseudocod: citeste n,a *presupunem n1 S 0 *initializarea sumei cu 0 ak 1 *initializarea puterii cu 1 pentru k = 1, n repeta ak ak * a S S + k*ak

scrie S Descrierea algoritmului n C++ (CodeBlocks):

#include #include using namespace std; int main() { int n,k; float S=0,ak=1,a; //functie putere care creste repede => memorare in "float" //factorilele este bine sa fie memorate in tip de date float coutn; //pp. n>=1 couta; for (k=1;k

Algoritmi si structuri de date (5-6.11.2014) Informatica&Matematic, anul 1 ASD13AlgIterLab

4

for (int i=2;i*i

Algoritmi si structuri de date (5-6.11.2014) Informatica&Matematic, anul 1 ASD13AlgIterLab

5

Tem suplimentar:

1. S se descrie un algoritm pentru a afia divizorii primi ai unui numr natural dat.

2. S se descrie un algoritm pentru afiarea tuturor numerelor prime de 3 cifre, care citite

invers sunt tot numere prime.

3. S se descrie un algoritm pentru a stabili dac dou numere sunt gemene (p i q sunt 2

numere gemene dac ambele sunt numere prime i q p = 2). De exemplu, 3 i 5,

5 i 7, 11 i 13, 17 i 19, 29 i 31 sunt numere gemene.

4. S se descrie un algoritm pentru a exprima o sum de lei dat n numr minim de

bancnote n valoarea de 1 leu, 5 lei, 10 lei, 50 lei, 100 lei i 500 lei.