Limbajului C++ - Suport de curs pentru clasele 9-11, profil matematica-informatica

prof.informatica Gabriela Gligor

Probleme de baza Instructiuni C++ 1.Eliminarea cifrelor unui numar.Enunt: Se citeste un numar de la tastatura.Sa se afiseze toate cifrele din numar. I. Partea teoretica Rezolvarea problemei se bazeaza pe eliminarea succesiva a ultimei cifre din numar cat timp mai exista cifre in numar. Deoarece in limbajul C++ sunt definiti operatorii matematici / si %,se observa ca din punct de vedere matematic: i. restul impartirii la 10 a unui numar reprezinta exact ultima cifra din acel numar Ex: n=1354 => r = n%10 = 4 ii. catul impartirii la 10 a unui numar reprezinta numarul initial din care s-a taiat ultima cifra. Ex: n=1354 => c = n/10 = 135 Deci din observatiile i. si ii. =>afisarea cifrelor unui numar este posibila in C++ parcurgand in mod repetitiv cele doua etape: 1.afisarea ultimei cifre 2.ajustarea numarului (prin eliminarea ultimei cifre). Obs: Momentul de oprire al algoritmului este cand numarul n devine 0 (n=0). II. Pasii algoritmului Pas1. daca n!=0 atunci pas 2 altfel pas3 Pas 2. scrie n%10 n=n/10 pas1 Pas 3. stop. ex: n=1354 ? da pas1. n=1354 =>n!=0 => scrie n%10 (4) ? da n=n/10 (n=135) pas 2. n=135 => n!=0 => scrie n%10 (5) ? da n=n/10 (n=13) pas3. n=13 => n!=0 => scrie n%10 (3) ? da n=n/10 (n=1) pas 4. n=1 => n!=0 => scrie n%10 (1) ? nu n=n/10 (n=0) pas 5. n=0 => n!=0 => stop. III. Secventa de program while (n!=0) { cout divizorii proprii sunt {2,3,4,6} => toti divizorii proprii sunt intervalul de cautare al divizorilor proprii ai lui n este [2,n/2]. Algoritmul consta in: -parcurgerea intervalului [2,n/2] cu ajutorul unui contor i si -verificarea fiecarei valori i daca este divizor sau nu al lui n II. Pasii algoritmului pas1. i = 2 pas2. daca i i n%i= =0 => scrie i (2) 2 6 12 2 i=i+1 (i=3)? da ? da

p2. i=3 => i n%i= =0 => scrie i (3) 3 6 12 3 i=i+1 (i=4)? da ? da

p3. i=4 => i n%i= =0 => scrie i (4) 4 6 12 4 i=i+1 (i=5)? da ? nu

p4. i=5 => i n%i= =0 => i=i+1 (i=6)5 ? 6 da 12 5 ? da

p5. i=6 => i n%i= =0 => scrie i (6) 6 6 12 6 i=i+1 (i=7)nu

p6. i=7 =>i stop.7 6

III. Secventa de program for(i=2;iintervalul de cautare a unui divizor va fi intervalul corespunzator divizorului n1 adica [2, n ].

De ce [2, n ] ? Ex: fie n=6 => Cazuri 6= 2*3 , n1=2 n2=3 6=3*2 , n1=3 n2=22

n1

n2

n/2

n=6

Atunci cand n1=n2 => n=n12 => n1= n

n

Rezolvarea problemei: Parcurgem cu un contor i intervalul [2, n ] in speranta ca nu vom gasi nici un divizor=>Intrebarea ar fi :ce se intampla daca totusi gasesc un divizor? =>avem nevoie de o variabila logica ok cu care sa punem in evidenta daca am gasit sau nu un divizor=> initial ok=1 (adica presupunem ca n este prim) si daca vom gasi cel putin un divizor atunci ok=0 (adica presupunerea facuta initial ca n este prim este falsa). (1) Din (1) => ca daca gasim cel putin un divizor deja stim ca n nu mai este prim =>numai are rost sa parcurgem restul intervalului=> conditia de cautare a primului divizor este: i pas4 altfel pas5 pas4. ok=0 =>pas5 pas5. i=i+1 =>pas2 pas6.daca ok=0 scrie nu e nr. prim altfel scrie nr. e prim Ex1: n=12212 12 2

da

da

p1. ok=1,i=2 => i n%i=0 => ok=0,i=i+1(3) p2. ok=0, i=3 => i ok=0=> scrie nu este nr.prim da3 12

Ex2: n=13

2

13

13 2 da nu

p1. ok=1,i=2 => i n%i=0 => i=i+1(3)3 13 da 13 3 nu

p2. ok=1, i=3 => i n%i=0 =>i=i+1(4)4 13 nu nu

p3. ok=1, i=4 => i ok=0 => scrie nr. prim III. Secventa de program for (i=2,ok=1; ia=b => a>b => a=a-b=66 6 da

p3.a=6,b=6=>a=b=> scrie cmmdc=a=6 =>stop. III. Secventa de program if (a= =0 || b= =0) //daca a=0 sau b=0 cmmdc este suma lor(cazurile particulare) cout scrie 2 =>n%i= =0 => n=n/i=90=> n%i= =0 => n=n/i=45=> n%i= =0 => i=i+1=3da 45 3 da 45 3 da 45 3 da 15 3 da 15 3 5 3 nu

p2. i=3,n=45 => n!=1 => n%i= =0 => scrie 3 =>n%i= =0 => n=n/i=15=> n%i= =0 => n=n/i=5=> n%i= =0 => i=i+1=4da 5 4 nu

p3. i=4,n=5 => n!=1 => n%i= =0 => i=i+1=5da 5 5 da 5 5 da 5 5 1 5 nu

p4. i=5,n=5 => n!=1 => n%i= =0 => scrie 5 => n%i= =0 => n=n/i=1=> n%i= =0 =>i=i+1=6nu

p5.i=6,n=1 => n!=1 => stop.

III. Secventa de program for(i=2; n!=1; i++) // se parcurg divizorii lui n ,incepand de la primul numar prim(2),cat timp acesta se mai poate descompune if (n%i= =0) //daca i este divizor atunci se afiseaza si se imparte succesiv numarul la el eliminandu-se astfel toti multipli lui { cout nq=r0=1 , n=n/q=66 da 0 1 0 1 0 6 2

pas2.n=6,q=2,nq=r0=1 => n!=0 => nq=r1r0=r1*10+r0=r1*10+nq=01 , n=n/q=33 da 1 0 1 12

0 1

12

1

3

2

pas3.n=3,q=2,nq= r1r0=1 => n!=0 => nq= r2r1r0=r2*10 + r1r0=r2*10 +nq=101 , n=n/q=11 da 1 1 0 1 13

1 0 1

13

101

1

1 2

pas4.n=1,q=2,nq= r2r1r0=101 => n!=0 => nq= r3r2r1r0= r3 *10 + r2r1r0= r3 *10 +nq=1101 , n=n/q=0nu

pas5.n=0,q=2,nq= r3r2r1r0=1101 => n!=0 =>scrie 1101 Nota: 1.Se observa ca formula de calcul a lui nq este:

nq=r*10i-1+nqunde i [1,k] k- numarul de cifre a lui nq(numarul de impartiri) . r- al i-lea rest obtinut din impartirea lui n la q.

2.Pentru a putea calcula in mod eficient 10k vom folosi o variabila p in care se vor calcula in mod iterativ (de la un pas la altul) puterile lui 10. Initial p=1(100) iar formula de calcul a lui p va fi: p=p*10 =>formula de calcul a lui nq este:

nq=r*p+nqAlgoritmul pe pasi este: p1.nq=0,p=1 p2.daca n!=0 atunci p3 altfel p4 p3.nq=n%q *p + nq n=n/q p=p*10 => p2 p4.scrie nq III. Secventa de program nq=0; //initial nq=0 p=1; //initial p=1=100 while(n!=0) { nq=n%q+nq; n=n/q; p=p*10; //creste puterea pentru pasul urmator // p=10k+1=10k*10 } cout primul termen din suma va fi : r0*q0 => formula generala de calcul a lui n va fi :

n=ri-1*qi-1 +nunde i [1,k] , k-numarul de cifre din nq 4. Calculul puterii lui q ( qk-1=q*qk-2 ) se va face tot iterativ folosind o variabila p astfel: p=q0=1(initial) p=p*q (in caz general) => formula generala de calcul a lui n va fi :

n=ri-1*p +nunde i [1,k] , k-numarul de cifre din nqRezolvarea problemei consta in:-extragerea fiecarei cifre din nq cat timp nq!=0 si -calculul sumei, prin adaugarea noului termen Nota: La fiecare pas se aduna un termen de forma : ri-1*p , unde p=q II. Pasii algoritmului p1. p=1,n=0 p2.daca nq!=0 atunci p3 altfel p4 p3.n=nq%10*p+n p=p*q nq=nq/10 =>p2 p4. scrie n Ex: nq=10101 da 1 1 0 pas1.nq=10101, n=0, p=20=1 => nq!=0 => n=nq%10*p+n=1,da 0 2 1 1 2

i-1

si ri-1 cifra extrasa de pe pozitia i din nq.

p=p*q=1*2=21,2 2

nq=nq/10=1010 nq=nq/10=101 nq=nq/10=10 nq=nq/10=1

pas2.nq=1010, n=1,p=21 => nq!=0 => n=nq%10*p+n=0*21+1=1, p=p*q=21*2=22,da 1 4 1 4 2

pas3.nq=101, n=1,p=22 => nq!=0 => n=nq%10*p+n=1*22+1=5, p=p*q=22*2=23,da 0 8 5 8 2

pas4.nq=10, n=5,p=23 => nq!=0 => n=nq%10*p+n=0*23+5=5,da 1 16 5

p=p*q=23*2=24,16 2

pas5.nq=1, n=5,p=24 => nq!=0 => n=nq%10*p+n=1*24+5=21, p=p*q=24*2=25, nq=nq/10=0nu

pas6.nq=0, n=21,p=2 => nq!=0 => scrie 21 III. Secventa de program n = 0; //initial n=0 p = 1; //initial p=20=1 while(nq!=0) { n = nq%10 * p + n; //se calculeaza n ca o suma p * = q; //creste puterea p nq / =10; //se elimina ultima cifra din nq } cout