Calcularea CMMDC si a CMMMC
13In urmatoarea perioada voi propune si voi rezolva probleme simple pentru un incepator in algoritmica si C/C++ pentru a incerca sa aducem si sa trezim interesele si celor mai slabuti dintre noi. 😀
In general pentru calcularea celui mai mare divizor comun se foloseste algoritmul algoritmul lui Euclid prin scaderi repetate sau prin impartiri repetate.De preferat pentru timpul de executie este calcularea celui mai mare divizor comun prin impartiri repetate.
Calcularea celui mai mare divizor comun (CMMDC) prin scaderi repetate
#include <stdio.h> int main() { int a,b; scanf("%d %d",&a,&b); while(a!=b) { if(a>b) a=a-b; else b=b-a; } printf("cmmdc= %d",a); return 0; }
Calcularea celui mai mare divizor comun (CMMDC) prin impartiri repetate
#include <stdio.h> int main() { int a,b,r; scanf("%d %d",&a,&b); r = a % b; while(r != 0) { a = b; b = r; r = a % b; } printf("cmmdc= %d",b); return 0; }
O varianta recursiva pentru cel de-al doilea algoritm si mult mai simplu de memeorat:
int cmmdc(int a, int b) { if((!a) || (!b)) return a+b; if(a>b) return cmmdc(a%b,b); return cmmdc(a,b%a); }
Calcularea celui mai mic multiplu comun(CMMMC)
Ne putem folosi de formula CMMMC = a*b/CMMDC. 😀
#include <stdio.h> int main() { int a,b,r,c,x,y; scanf("%d %d",&a,&b); x=a; y=b; while(b!=0) { r=a % b; a=b; b=r; } printf("cmmdc= %d\n",a); c=x*y/a; printf("cmmmc= %d",c); return 0; }
Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!
Nu am ce spune decat… EXCELENT. Ca o prima metoda ai folosit algoritmul euclidean, asta doar daca am efectua operatiile de scadere in binar ar mai putea fi imbunatatita viteza.
…parerea mea
Nu putem fi siguri de asta.Pe noile compilatoare transformarea din codul limbajului de programare in cod nativ se face mult mai eficient.Pe borland spre exemplu la numere foarte foarte mari s-ar vedea diferente insa pe Mingw/Dev-C++ putin probabil.
Eu am inceput cu scaderile repetate, apoi cu cel mai mic multiplu. Am ajuns la algoritumul lui Euclid mai tarziu. Paradoxal things ! 😀
Ma bucur ca ai inteles aceasta” limba straina” pentru mine 🙂 Informatica asta ma omoara ;))
Poate vb si noi sa imi dai cateva ideii 😀
super de treaba formulele, super bune
#include
#include
void main()
{
int a,b,c,d,x,y;
clrscr();
cout<>a;
cout<>b;
x=a;
y=b;
while(x!=y)
{
if(x>y)
x=x-y;
else
y=y-x;
}
c=x;
d=(a*b)/c;
cout<<"cmmdc="<<c<<endl;
cout<<"cmmmc="<<d<<endl;
getch();
}
🙂
private static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
private static void cmmdcPrinScaderi() throws IOException {
long a, b;
System.out.println(„Introdu primul numar: „);
a = Long.parseLong(bf.readLine());
System.out.println(„Introdu al doilea numar: „);
b = Long.parseLong(bf.readLine());
while (a != b) {
if (a > b) {
a = a – b;
} else {
b = b – a;
}
}
System.out.println(„CMMDC= ” + a);
}
private static void cmmdcPrinImpartiri() throws IOException {
long a, b, r;
System.out.println(„Introdu primul numar: „);
a = Long.parseLong(bf.readLine());
System.out.println(„Introdu al doilea numar: „);
b = Long.parseLong(bf.readLine());
r = a % b;
while (r != 0) {
a = b;
b = r;
r = a % b;
}
System.out.println(„CMMDC= ” + b);
}
private static void alegeMetoda(){
System.out.println(„Alege metoda de aflare a cmmdc: 1.Prin impartire 2.Prin scadere „);
try {
String metoda = bf.readLine();
if(metoda.equals(„1”)){
cmmdcPrinImpartiri();
}else if(metoda.equals(„2”)){
cmmdcPrinScaderi();
}
System.out.println(„Doresti sa afli si cmmmc al numerelor? 1.Da 2.Nu 3.Doresc sa introduc alte numere „);
String optiune = bf.readLine();
if(optiune.equals(„1”)){
}
} catch (IOException ex) {
Logger.getLogger(CMMDC.class.getName()).log(Level.SEVERE, null, ex);
}
}
public static void main(String args[]) {
alegeMetoda();
}
01.#include
02.int main()
03.{
04.
int a,b,r;
05.
scanf(„%d %d”,&a,&b);
06.
r = a % b;
07.
while(r != 0)
08.
{
09.
a = b;
10.
b = r;
11.
r = a % b;
12.
}
13.
14.
printf(„cmmdc= %d”,b);
15.
return 0;
16.}
Multumesc mult mult mult maine dau olimpiada si astea ma ajuta 😉 🙂 🙂 =) 😀 poate mai schimbam o vorba mai incolo sa-mi dati si mie niste idei ptr grad cls a-6-a oji 2011
Exp :
sirul : 1 5 4 7
ordonat : 1 4 5 7
cate numere si-au schimbat pozitzia ?
:: 1
=: afisez 1
Acum sa nu ma retrag de la subiect :
sigur trb sa afisez a la scaderi repetate ?
care ia mai mult timp de executie (banuiesc ca cel prin imparitiri repetate , dar intreb sa ma asigur ) ????
Stii, eu apreciez ce-ai facut, o treaba foarte buna!
Dar, cum abia am inceput sa lucrez in C++, nu stiu ce-i cu „scanf” si „printf”.
Daca puteti sa-mi spuneti ce-i cu cele doua?
„Scanf” este echivalent cu functia „Cin” din libraria iostream iar „Printf” cu „Cout”.
Ma poate ajuta cineva cu CMMMC a unui sir de n numere?Asta este tot ce am reazlizat pana acum
#include
#include
void main(void)
{
int poz[255],i,n;
printf("Introduceti numarul de pozitii:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Introduceti numarul:");
scanf("%d",&poz[i]);
}
while(i!=NULL)
{
i
}
}
Revin cu un cod „ceva mai avansat”:
#include
#include
void main(void)
{
int poz[255],i,n,a,b,r;
printf("Introduceti numarul de pozitii:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Introduceti numarul:");
scanf("%d",&poz[i]);
}
a=poz[i];
b=poz[i+1];
for(i=0;i<n;i++)
{
r=a*b/a;
}
printf("CMMMC:%d",r);
getch();
}
de ce nu faci cu „int main()” si te complici cu „void main(void)”??? e mult mai simplu sa pui un return code la sfarsit 😉