algoritmi pentru prelucrarea cifrelor, cmmdc, divizori primi
TRANSCRIPT
Algoritmi pentru prelucrarea cifrelor, cmmdc, divizori primi
Clasa a V-a
1
Algoritmi pentru prelucrarea cifrelor, cmmdc, divizori primi
Algoritmul pentru prelucrarea cifrelor se bazeaza pe existenta in limbajul C a unor instructiuni care ajuta la prelucrarea ultimei cifre din numar : uc=n%10 ajuta la eliminarea ultimei cifre din numar: n=n/10 .
if (n == 0) //prelucrarea numarului 0 while (n > 0) { cif = n%10; //operatii care prelucreaza //cifra curenta conform problemei n = n / 10; }
do{ cif = n%10; //operatii care prelucreaza //cifra curenta conform problemei n = n / 10; } while (n > 0);
ATENȚIE! Prin spargerea unui număr în cifre, valoarea inițială se distruge.
Dacă mai aveți nevoie de ea în program, trebuie să-i faceți o copie lui n înainte de a-l sparge
Calcularea cifrelor unui numar
Programul se bazeaza pe urmatorul principiu: contorul nrcifre numara cifra unitatilor, apoi cifra zecilor, a sutelor si asa
mai departe. Dupa fiecare cifra, conturul se mareste cu o unitate, iar apoi se elimina ultima cifra a numarului citit n nrcifre = 0; if (n == 0) nrcifre = 1; while (n > 0) { nrcifre++;
n = n / 10; }
Determinarea primei cifre a unui numar n
if (n == 0) primacif = 0; while (n > 9) n=n / 10; primacif = n;
Determinarea oglinditului lui n (de ex., oglinditul numarului 12345 este 54321) ogl = 0; while (n > 0) { cif = n % 10; ogl = ogl * 10 + cif; n = n / 10; }
ATENȚIE! La oglindirea unui număr terminat cu cifre de 0, aceste cifre 0 se pierd deoarece devin zerouri semnificative, în fața primei cifre a oglinditului.
Eliminarea cifrelor pare
p = 1; nr = 0; while (n>0) { cif = n % 10;
if(cif % 2 != 0) { nr = nr + cif*p;
p = p * 10; } n = n / 10;
}
Algoritmi pentru prelucrarea cifrelor, cmmdc, divizori primi
Clasa a V-a
2
Numararea aparitiilor cifrei K
nrap = 0; if (n == 0 && k == 0) nrap = 1; while (n>0) { cif = n % 10; if (cif == k) nrap++; n = n / 10; }
Extragerea cifrelor lui n în ordinea în care apar în numar
//determinăm cea mai mare putere a lui 10, care este mai mică sau egală decât numărul n p = 1; while (p * 10 <= n) p = p * 10; while (n > 0) { cif = n / p; //prelucreaza cif conform cerintelor problemei n = n % p; }
Probleme propuse: 1. Se citeste un numar natural n de cel mult 15 cifre. Sa se afiseze elimine din n cifrele impare apoi sa se verifice
daca numarul rezultat este palindrom (este egal cu oglinditul). Se va afisa numarul rezultat si valoarea 1 daca e palindrom sau 0 daca nu. Ex: pentru n=245352102492, se vor afisa 2420242 1
2. Se citesc pe rand n numere naturale. Sa se afiseze numarul de cifre pare continute in toate aceste numere. 3. Se citesc pe rand n numere naturale nenule. Sa se afiseze sirul format cu prima cifra a fiecarui numar dat. 4. Cifră: se citește un număr n, să se spună dacă este format dintr-o singură cifră, repetată.
Exemple: 3333 este un astfel de număr, 2424 nu este, 5 este, 88 este. Algoritmi pentru cmmdc Cel mai mare divizor comun ( C.M.M.D.C.) pentru doua numere naturale nenule este cel mai mare numar
natural care divide numerele date. Exemplu:
C.M.M.D.C. al numerelor a = 18, b = 12 este, 6.
D1={ 1, 2, 3, 6, 9, 18 } D2={ 1, 2, 3, 6, 12 }
Dc={ 1, 2, 3, 6,} iar cel mai mare divizor comun este 6
Algoritmul lui Euclid ( c.m.m.d.c. a două numere )
Algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun (CMMDC). Euclid a observat
că CMMDC al două numere a și b rămîne același dacă se scade numărul mai mic din cel mai mare.
Presupunînd că a este numărul mai mare, scăzînd în mod repetat pe b din a, în a va rămîne restul împărțirii lui a la b.
Rezultă că CMMDC(a, b) este totuna cu CMMDC(b, a % b). Algoritmul care rezultă este
următorul:
luăm restul împărțirii lui a la b, apoi restul împărțirii lui b la rest, și așa mai departe, pînă ce obținem un rest zero. CMMDC este numărul rămas, cel diferit de zero.
Exemplu: Să calculăm CMMDC(18, 12).
Calculăm 18 % 12 = 6. De aceea va trebui să calculăm CMMDC(12, 6). În continuare calculăm 12 % 6 = 0. Deoarece restul este zero CMMDC va fi ultimul număr nenul, adica 6.
a b c=a/b r=a%b
18 12 1 6
12 6 2 0
6 0
Algoritmi pentru prelucrarea cifrelor, cmmdc, divizori primi
Clasa a V-a
3
CMMDC(a, b)
CMMDC(a, b) CMMDC(a, b) CMMMC(a, b)
while (a!=b) { if(a>b) a=a-b; else b=b-a; } CMMDC = a;
rest = a % b; while (rest != 0) { a = b; b = rest; rest = a % b; } CMMDC = b;
while (b != 0)
{
rest = a % b;
a = b;
b = rest;
}
CMMDC = a;
P=a*b; while (b != 0) { rest = a % b; a = b; b = rest; } CMMMC =P/a;
Cel mai mic multiplu comun ( c.m.m.m.c.) pentru doua numere naturale nenule este cel mai mic numar natural care se divide cu numerele date.
Exemplu: C.m.m.m.c. al numerelor a = 18, b = 12 este
M1={ 18, 36, 54, 72.. } M2={ 12, 24, 36, 48, 60, 72 } Dc={ 36, 72, } iar cel mai mic multiplu comun este 36
C.m.m.d.c. al numerelor a = 30, b = 20 este 60.
Atentie! Ca sa calculati cel mai mic multiplu comun, trebuie sa calculati cmmdc si sa aplicati formula
cmmmc=(ca*cb)/cmmdc; unde ca=a; cb=b; copiile valorilor initiale, facute inainte de a calcula cmmdc
Daca CMMDC = 1, numerele respective se numesc prime intre ele. (numim numar prim orice numar natural care are exact 2 divizori distincti: pe 1 si pe el insusi ! 0 si 1 NU sunt numere prime ; primul numar prim este 2;)
Exemplu: Numerele 24, 15 sunt prime intre ele, caci (24, 15) = 1.
Probleme propuse:
1. Doi prieteni, un iepure și o broscuță joacă un joc: pornesc de la o linie de start și încep să sară. Broasca sare n centimetri, iar iepurele m centimetri. Cine este mai în spate vine la rînd să sară. Jocul se termină atunci cînd iepurele și broasca sînt iarăși la egalitate. Cîți centimetri au parcurs cei doi prieteni?
Săriturile broscuței și iepurelui
2. Pavaj: să se paveze un dreptunghi cu pătrate maximale. Se citesc a și b numere naturale, dimensiunile laturilor dreptunghiului, să se afișeze latura pătratelor cele mai mari cu care putem acoperi dreptunghiul, precum și numărul lor. Ex: dacă a este 3 și b este 4 vom afișa 1 și 12 (cel mai mare pătrat cu care putem acoperi dreptunghiul are latură 1 și
avem nevoie de 12 astfel de pătrate); dacă a este 6 și b este 8 vom afișa 2 și 12;dacă a este 12 și b este 20 vom afișa 4 și 15.
3. Se citesc pe rand n numere naturale nenule. Sa se determine cmmdc pentru mininul si maximul din sir. Ex: N=5 si valorile 12 8 9 28 17. Se va afisa 4 (cmmdc(8, 28)=4)
4. Se citesc K un numar natural nenul apoi se citesc pe rand n numere naturale nenule. Sa se afiseze numerele prime cu K sau valoarea 0, daca nu exista astfel de numere. Ex. K=15, N=5 si valorile 12 8 9 28 17. Se vor afisa 8 28 17
Algoritmi pentru prelucrarea cifrelor, cmmdc, divizori primi
Clasa a V-a
4
Descompunerea in factori primi. Determinarea divizorilor primi ai lui n.
for( d = 2; d * d <= n; d++)
{ m = 0;
while ( n % d == 0)
{ m++;
n = n / d;
}
if (m>0)
cout<<m<<" ^ "<< p<<endl; ... //operatii care trebuie efectuate cu divizorul prim d la puterea m
}
if (n>1) //prelucreaza ultimul divizor prim n, care apare la puterea 1
cout<<n<<" ^ " << 1<<endl;
Numarul divizorilor lui n. Formula lui Euler.
Fie N = p1m1 * p2m2 * ...* pkmk atunci numarul de divizori ai lui N este Nrdiv = (m1 + 1)*(m2 + 1)*...*(mk + 1)
nrdiv = 1;
for( d = 2; d * d <= n; d++)
{
p = 0;
while (n % d == 0)
{
p++;
n = n / d;
}
nrdiv = nrdiv * (p + 1);
}
if (n>1)
nrdiv = nrdiv * 2;
Probleme propuse: 1. Se citește n un numar natural nenul. Sa se determine cel mai mic număr care are aceeași factori primi în
descompunere ca și n. Ex: pentru n=720, se va afisa 30 (30=2 * 3 * 5, 720=24 * 3 2 * 5)
Tema
www.pbinfo.ro : numere15, ProdusCifreImpare, , UltimaCifraPara, cifre23, ProdusCifreImpare, PrimaCifraMinima,
Aparitii, Aparitii2, CmmdcN, AfisareDivizoriComuni, FractieMinima
http://campion.edu.ro/arhiva problemele: tort, gard, ingerasi,
Trimiteţi soluţiile pe adresa [email protected] sub forma unei arhive denumită cu numele vostru.
Creaţi arhiva urmând paşii:
1. Creaţi un folder cu numelevostru_tema5
2. Copiati una câte una sursele main.cpp în acest folder şi redenumiţi-le cu numele problemei
3. Arhivaţi acest folder pastrand numele arhivei identic cu al folderului
4. Ataşaţi arhiva la email-ul pe care îl trimiteţi la adresa [email protected]
Termen: 9 decembrie 2018, ora 21 SUCCES!