asd13algiterlab
DESCRIPTION
alg liniariTRANSCRIPT
-
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.