Bella: /* CMMMC */

2017-11-29T14:19:21Z

CMMMC

New page

==Structura repetitiva ''DO WHILE''==
Structura repetitivă de tip DO-WHILE (execută -cîtă timp) reprezinta structura de control cu ajutorul careia executam un set de instructiuni, de mai multe ori, in functie de o conditie. Spre deosebire de instructiunea WHILE –DO, aceasta structura executa mai intai blocul de instructiuni si mai apoi testeaza conditia.

[[Image:sl-repeat-until.gif|frame|none|Schemă logică DO-WHILE]]

Mecanism:

Pasul 1. Se executa pachetul de instructiuni “Prel”;
Pasul 2: Se testeaza conditia. Daca conditia este adevarata atunci revenim la pasul 1. Daca conditia este
falsa se trece la pasul 3.
Pasul 3. Stop

'''Obs''': Spre deosebire de instructiunea while-do, instructiunea do –while, executa cel putin odata
pachetul de instructiuni, indiferent de valoarea de adevar a expresiei logice(conditie).
Orice instructiune do-while, poate fi inlocuita de o instructiunea while, echivalenta (vezi tabelul).
==Aplicatii==
===Suma cifrelor unui numar===

Sã se realizeze un algoritm ce calculeazã suma cifrelor unui numar natural.

{| class="wikitable"
!Pseudocod
!C
!C++
|- style="vertical-align:top;"
|
citeste n;
s ← 0;
Repeta
s ← s + n%10
n ← n/10
cat-timp (n>0)
scrie s
|
<syntaxhighlight>
#include<stdio.h>
int main(){
int n,s;
scanf(“%d”,&n);
s=0;
do{
s=s+n%10;
n=n/10;
}while(n>0);
printf(“%d”,s);
return 0;
}
</syntaxhighlight>
|
<syntaxhighlight>
#include <iostream>
using namespace std;
int main(){
int n,s; cin>>n;
s=0;
do{
s=s+n%10;
n=n/10;
}while(n>0);
cout<<s;
return 0;
}

</syntaxhighlight>
|}

===Cifra de control===
Se citeste un numar n. Afisati cifra de control a numarul n. Cifra de control se obtine prin adunarea repetata a cifrelor numarului pana cand se obtine o singuracifra.
Ex: n=193 s=1+9+3=13 s=1+3=4
<syntaxhighlight>
#include <iostream>

using namespace std;

int main(){
int n, s;
cout << "Dati un numar n:" << endl;
cin >> n;
do{
s = 0;
while( n > 0 ){
s = s + n % 10;
n = n / 10;
}
n = s;
}while( s > 9 );
cout << "Cifra de control este " << s;
return 0;
}
</syntaxhighlight>

O alta metoda de rezolvare:
cifcontrol = ( n-1 ) % 9 + 1

===Descompunerea in factori primi ===
====Varianta1 cu do while ====
Vom imparti numarul repetat la factori primi, pana cand acesta devine 1. Atentie la afisare: Cand afisam primul factor nu vom mai pune "*" inainte.
<syntaxhighlight>
#include<stdio.h>
int main(){
int n, p, d, pas;
scanf( "%d", &n );
d = 2; pas = 1;
do{
p = 0; ///impartim pe n la d de cate ori se poate
while( n % d == 0 ){
n= n / d;
p = p + 1; ///rezulta p, ca fiind puterea divizorului
}
if( p > 0 )
if( pas == 1 ){
printf("%d^%d", d, p);
pas = pas + 1;
}
else
printf("*%d^%d", d, p);
d = d + 1;
}while( n > 1 ); ///cata vreme n nu a fost descompus
return 0;
}

</syntaxhighlight>

=== Varianta 2 cu while do ===
Atentie la afisare: Cand vom afisa ultimul factor nu vom mai pune "*" dupa.

<syntaxhighlight>

#include <stdio.h>
int main(){
int n, d, p;
scanf( "%d", &n ); // cin>>n;
d = 2;
while(n > 1){
p = 0;
while( n % d == 0 ){
n = n / d;
p = p + 1;
}
if(p != 0)
if(n == 1) //ca am gasit un ultim factor
printf("%d^%d", d, p); //cout<<d<<"^"<<p;
else
printf("%d^%d*", d, p); //cout<<d<<"^"<<p<<"*";
d = d + 1;
}
return 0;
}
</syntaxhighlight>

====Varianta2 cu do-while ====
<syntaxhighlight>
#include <stdio.h>
int main(){
int n, d, p;
scanf("%d",&n); //cin>>n;
d = 2;
do{
p = 0;
while( n % d == 0 ){
n = n / d;
p = p + 1;
}
if(p != 0)
if(n == 1) //ca am gasit un ultim factor
printf("%d^%d", d, p); //cout<<d<<"^"<<p;
else
printf("%d^%d*", d, p); //cout<<d<<"^"<<p<<"*";
d = d + 1;
}while(n != 1);
return 0;
}
</syntaxhighlight>

====Descompunere in factori primi - Optimizare ====
<syntaxhighlight>
#include <stdio.h>

int main(){
int n, d, p;
scanf( "%d", &n );
d = 2;
while(d * d <= n){
p = 0;
while(n % d == 0 ){
n = n / d;
p = p + 1;
}
if( p > 0 )
printf("%d %d\n", d, p);

d = d + 1;
}
// verificam daca mi-a mai ramas in n un factor prim
if ( n > 1)
printf("%d 1", n);

return 0;
}
</syntaxhighlight>

=== Algoritmul lui Euclid - cmmdc ===
[http://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid Algoritmul lui Euclid] este o metodă eficientă de calcul al celui mai mare divizor comun (<tt>CMMDC</tt>). El este denumit după matematicianul grec Euclid, care l-a inventat. Un avantaj important al algoritmului lui Euclid este că el poate găsi <tt>CMMDC</tt> eficient fără să trebuiască să calculeze factorii primi ai numerelor.

Euclid a observat că <tt>CMMDC</tt> al două numere <tt>a</tt> și <tt>b</tt> rămîne același dacă se scade numărul mai mic din cel mai mare (demonstrați!). Presupunînd că <tt>a</tt> este numărul mai mare, scăzînd în mod repetat pe <tt>b</tt> din <tt>a</tt>, în <tt>a</tt> va rămîne restul împărțirii lui <tt>a</tt> la <tt>b</tt>. Rezultă că <tt>CMMDC(a, b)</tt> este totuna cu <tt>CMMDC(b, a % b)</tt>. Algoritmul care rezultă este următorul: luăm restul împărțirii lui <tt>a</tt> la <tt>b</tt>, apoi restul împărțirii lui <tt>b</tt> la rest, și așa mai departe, pînă ce obținem un rest zero. <tt>CMMDC</tt> este numărul rămas, cel diferit de zero.

Exemplu
Să calculăm <tt>CMMDC(252, 105)</tt>. Calculăm <tt>252 % 105 = 42</tt>. De aceea va trebui să calculăm <tt>CMMDC(105, 42)</tt>. În continuare calculăm <tt>105 % 42 = 21</tt>. Deci, vom calcula <tt>CMMDC(42, 21)</tt>. Calculăm <tt>42 % 21 = 0</tt>. Deoarece restul este zero <tt>CMMDC</tt> va fi ultimul număr nenul, adica <tt>21</tt>.

====Algoritmul ce foloseste structura ''while do''====
{| class="wikitable"
!Pseudocod
!C
!C++
|- style="vertical-align:top;"
|
citeste a,b;
while( b <> 0 )
r ← a mod b;
a ← b;
b ← r;
scrie a
|
<syntaxhighlight>
#include<stdio.h>
int main(){
int a,b,r;
scanf("%d%d",&a,&b);
while( b > 0){
r = a % b;
a = b;
b = r;
}
printf("%d", a);
return 0;
}
</syntaxhighlight>
|
<syntaxhighlight>
#include <iostream>
using namespace std;
int main(){
int a,b,r;
cin>> a >> b;
while( b > 0 ){
r = a % b;
a = b;
b = r;
}
cout << a;
return 0;
}
</syntaxhighlight>
|}

====Algoritmul ce foloseste structura ''do while''====
{| class="wikitable"
!Pseudocod
!C
!C++
|- style="vertical-align:top;"
|
citeste a,b;
do
r ← a mod b;
a ← b;
b ← r;
while( r <> 0 )
scrie a
|
<syntaxhighlight>
#include<stdio.h>
int main(){
int a,b,r;
scanf("%d%d",&a,&b);
do{
r = a % b;
a = b;
b = r;
}while( r != 0)
printf("%d", a);
return 0;
}
</syntaxhighlight>
|
<syntaxhighlight>
#include <iostream>
using namespace std;
int main(){
int a,b,r;
cin>> a >> b;
do{
r = a % b;
a = b;
b = r;
}while( r != 0 )
cout << a;
return 0;
}
</syntaxhighlight>
|}

== CMMMC ==
<syntaxhighlight>
#include <stdio.h>

int main(){
long long a, b, r, ca, cb;
scanf( "%lld", &a );
scanf( "%lld", &b );

ca = a;
cb = b;
while(b != 0){
r = a % b;
a = b;
b = r;
}

printf("%lld", ca * cb / a );
return 0;
}
</syntaxhighlight>
'''Aplicatie''':
Doi prieteni, un iepure și o broscuță joacă un joc: pornesc de la o linie de start și încep să sară. Broasca sare <tt>n</tt> centimetri, iar iepurele <tt>m</tt> 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?

[[Image:cmmmc.gif|frame|none|Săriturile broscuței și iepurelui]]

'''Răspuns''': după cum se vede și din figură, broscuța și iepurele vor sări o lungime egală cu <tt>CMMMC(m, n)</tt>. Precum știm

<pre>CMMMC(m, n) = m ∙ n / CMMDC(m, n)</pre>.

= Tema 12 =

Descompunerea in factori primi:

* [https://www.pbinfo.ro/?pagina=probleme&id=62 Factorizare] teorie
* [https://www.pbinfo.ro/?pagina=probleme&id=63 Factorizare1]
* [https://www.pbinfo.ro/?pagina=detalii-evaluare&id=6312881 Factoriprimi]
* [https://www.pbinfo.ro/?pagina=probleme&id=268 Divk]
* [https://www.pbinfo.ro/?pagina=probleme&id=1319 Descompunere_factori]

Cmmdc / Cmmmc:

* [https://www.pbinfo.ro/?pagina=probleme&id=378 pavare] teorie
* [https://www.pbinfo.ro/?pagina=probleme&id=410 cmmdc2]
* [http://varena.ro/problema/plaja1 plaja1]
* [http://varena.ro/problema/plaja1 plaja1]
* [http://varena.ro/problema/vraji vraji]
* [http://varena.ro/problema/padure padure]

Clasa a V-a lecția 6 S12 - Revision history

Bella: /* CMMMC */