APLICATII - Algoritmi elementari

I. Algoritmi care prelucreaza cifrele unui numar: 1. dat n numar natural se cere:

1.1. numarul de cifre al lui n 1.2. suma/produsul cifrelor lui n 1.3. minim/maxim pe cifrele lui n 1.4. numarul zerourilor/cifrelor impare/ cifrelor pare ale lui n 1.5. sa se verifice divizibilitatea cu 3 conform criteriului 1.6. sa se verifice divizibilitatea cu 11 conform criteriului(11|n daca suma cifrelor dp pozitii pare -

suma cifrelor dp pozitii impare divizibila cu 11) 1.7. sa se verifice daca n este palindrom

2. sa se genereze toate numerele de trei cifre bine ordonate crescator/descrescator 3. dat n natural nenul sa se elimine o cifra astfel incat numarul rezultat sa fie maxim/minim 4. sa se afiseze cifra de control a unui numar natural dat (suma cifrelor, suma sumei cifrelor…samd

pana se obtine un numar dintr-o cifra). 5. dat n natural sa se afiseze cifrele distincte ce apar in scrierea sa, in ordine crescatoare 6. dat n natural sa se afiseze cel mai mare numar care se poate forma cu toate cifrele sale 7. sa se verifice daca un numar natural dat are aspect de munte (cifrele sale sunt in ordine strict

crescatoare pana la un punct si strict descrescatoare din acel punct la sfarsit; EX: 1479320) II. Divizibilitate. Algoritmi care prelucreaza divizorii proprii unui numar

1. Dat n un numar natural se cere:

1.1. sa se calculeze numarul/suma/produsul divizorilor sai 1.2. sa se verifice daca e perfect (suma div proprii + 1 = numaru datl) 1.3. sa se genereze primele n numere perfecte/numerele perfecte mai mici decat n 1.4. sa se descompuna in factori primi 1.5. sa se determine puterea la care apare un factor prim p, dat, in descompunerea in factori primi a

lui n, fara a efectua descompunerea 1.6. sa se determine numarul de zerouri in care se termina produsul numerelor a1, a2,…,an citite pe

rand, fara a efectua produsul 2. Se citeste pe rand un sir de n numere naturale. Sa se determine numarul cu cei mai multi divizori 3. Dat n natural sa se determine eficient cel mai mare/cel mai mic divizor propriu diferit de 1 4. Sa se determine cel mai mare numar <= n care are un numar maxim de divizori primi III. Algoritm de testare a primalitatii unui numar 1. Dat n numar natural se cere:

1.1. Sa se afiseze primele n numere prime 1.2. Sa se afiseze cel mai mare numar prim <= n / cel mai mic numar prim >= n

2. Se citesc pe rand numere naturale prime pana la citirea unui numai neprim. Sa se determine numarul de valori introduse

3. Se considera sirul 7,17,37,47,67…sa se determine pentru un n dat, al n-ulea termen al sirului 4. Sa se determine primele n perechi de numere prime gemene (a,b sunt prime gemene daca sunt

impare consecutive si prime; EX: 3,5; 5,7; 11.13 etc.

IV. Descompunerea unui număr în factori primi

1. Dat n un numar natural nenul de cel mult 9 cifre, sa se verifice daca este liber de patrate (in descompunerea in factori primi, nici un factor prim nu apare la o putere para)

2. Sa se afiseze factorii primi, in ordine crescatoare, din descompunerea unui numar natural nenul dat.

3. Se citesc pe rand n numere naturale nenule, sa se afiseze numerele citite care au un numar impar de factori primi in descompunere. Sa se afiseze cate astfel de numere s-au gasit.

V. cmmdc si cmmmc Cmmmc(a, b)=a*b/cmmdc(a,b) 1. Se citesc pe rand n numere naturale, sa se determine cmmdc-ul/cmmmc-ul acestora 2. Se citesc numere intregi pana la citirea lui 0, sa se afiseze toate tripletele de numere consecutive

a,b,c cu proprietatea cmmdc(a,b) = c 3. Fie fractia intreaga a/b data prin numarator si numitor, sa se afiseze fractia ireductibila 4. Se citesc pe rand n numere naturale. Sa se determine cate dintre acestea sunt prime cu k dat 5. Se citesc pe rand n fractii date prin numarator si numitor. Sa se afiseze fractia suma in forma

ireductibila VI. Algoritmi care prelucreaza sirul lui Fibonacci f0 = f1= 1; fn = fn-1 + fn-2, n>= 2 f0=1; f1=1; pentru i=1,n,+1 executa f2=f0+f1

f0=f1 f1=f2

sfarsit pentru

int i; if (n >=2) { f0=f1=1; for (i=2; i<=n; i++) { f2=f1 + f0; prelucrare(f2); f0=f1; f1=f2; }

Cel mai mare numar fibonacci mai mic egal cu n if (n < 2) prelucrare(n) else { f0=f1=1; while (f0+f1<=n) { f2 = f1 + f0; f0=f1; f1=f2; } prelucrare(f1); }

APLICATII: 1. Dat n natural sa se verifice daca este termen Fibonacci, daca nu sa se determine cel mai apropiat

termen Fibonacci si rangul sau. 2. Date 2 numere naturale nenule a,b sa se verifice daca sunt termeni consecutivi in sirul Fibonacci. 3. Sa se afiseze termenul Fibonacci de rang n pentru un n dat 4. Sa se determine toate modalitatile de a urca o scara cu n trepte stiind ca intr-un pas se poate urca o

treapta sau doua. 5. Dat n numar natural nenul sa se determine o descompunere a sa in suma de termeni Fibonacci cu

numar minim de termeni. VII. Algoritmi care utilizeaza conversii intre baze B10 ->B

long cmmdc (long n, int b) { long s=0, p=1; while (n) { s=s+p*n%b; n=n/b; p=p*10; } return s; }

B->B10

long cmmdc (long n, int b) { long s=0, p=1; while (n) { s=s+p*n%10; n=n/10; p=p*b; } return s; }

APLICATII: 1. Dat n numar natural in baza b1 si o baza b2 sa se afiseze conversia numarului din b1 in b2 2. Dat n numar natural si o baza b sa se determine numarul de cifre necesar conversiei in baza b a lui n 3. Dat n numar natural si o baza b sa se determine numarul de cifre 0 din reprezentarea in baza b 4. Dat a in baza b1 si b in baza b2 sa se decida care din ele este mai mare in baza 10 VIII. Algoritmi care citesc si prelucreaza pe rand numere #include <fstream.h> ifstream fin(“….in”); ofstream fout(“….out”);

Citirea pe rand a n numere si prelucrarea lor fin>>n; for (i=1; i<=n; i++) { fin>>x; prelucrare(x); }

Citirea pe rand a n numere si prelucrarea perechilor de nr. citite consecutiv fin>>n; fin>>a; for (i=2; i<=n; i++) { fin>>b; prelucrare(a, b); a=b;}

Citirea pe rand a numerelor pana la indeplinirea unei conditii fin>>n; while (cond) { prelucrare(n); fin>>n; }

Citirea pe rand a numerelor pana la sfarsitul fisierului fara sa stim cate numere sunt while (fin>>x) prelucrare(x); EX: construirea vectorului de frecventa sau a vectorului caracteristic pentru un sir numerele din fisier while (fin>>x)

c[x]++; //sau c[x]=1; //prelucrarea numerelor distincte gasite in fisier, in ordine crescatoare (valmax=valoarea maxima

//pe care o poate avea un numar intalnit in fisier) for (i=0; i<=valmax; i++) if (c[i]!=0) prelucrare (i);

//prelucrarea tuturor numerelor gasite in fisier, in ordine crescatoare (valmax=valoarea maxima //pe care o poate avea un numar intalnit in fisier)

for (i=0; i<=valmax; i++) for (j=1; j<=c[i]; j++) prelucrare (i);

Obs: Algoritmii de citire si prelucrare pe rand sunt liniari (se pot utilize in cazul cerintelor de algoritmi eficienti ca timp de executie si spatiu de memorie)