PC-Config

Totul despre PC și mai mult de atât!

Algoritmul lui Euclid

Algoritmul lui Euclid ne poate ajuta să determinăm, având 2 numere, cel mai mare divizor comun, printr-o metodă simplă şi eficientă din punctul de vedere al consumului de resurse.

„Un număr întreg d se numește cel mai mare divizor comun a numerelor întregi a și b dacă și numai dacă pentru orice divizor comun c al lui a și b, d este un divizor al lui c.

În cazul în care impunem condiția d>0 este relativ simplu de verificat dacă d este unic. Acest număr se notează cu c.m.m.d.c(a,b), sau mai simplu: (a,b).

Folosind principiul bunei ordonări a numerelor naturale, putem deduce că c.m.m.d.c(a,b) este cel mai mic număr pozitiv care poate fi scris ca o combinație liniară a lui a și b, adică cel mai mic număr natural de forma a*x+b*y, unde x,y sunt numere întregi.”

Sursă: Wikipedia

Pseudocod

Di: n, m
De: n

citeşte n, m
┌cât timp n!=m execută
│   ┌dacă n>m
│   │   atunci n←n-m
│   │   altfel m←m-n
│   └■
└■
Scrie n

Limbaj C++

#include <iostream.h>
unsigned int n, m;
main()
{
cin>>n>>m;
while (n=m)
if (n>m) 
n=n-m;
else m=m-n;
Cout<<n;
}

12 Comments

  1. Vezi ca e gresit sa spui „sa determinam cel mai mare divizor comun al unui numar…”.
    C.M.M.D.C se poate afla doar din 2 numere: factorii comuni la puterea cea mai mica.

  2. Da asa este am gresit in introducere (din graba) dar algoritmul e bine scris!

  3. saluatre tuturora !…..este foarte interesant site-ul vostru ……il am in ” opera ” …pt momente dificile in viatza mea ….asa ca ms ca v-ati inventat
    …….)))))

  4. Multumim pentru aprecieri!

  5. De ce nu pot sa utilizez Borland C++ for Dos? Scriu datele si cand dau RUN ma scoate afara din program (vad desktop-ul)chiar daca nu am erori! Mentionez ca am instalat Windows XP Prof. ,fara a avea inainte MS-Dos! Multumesc anticipat!!

  6. Incearca sa reinstalezi programul.

  7. Andrei te-ai referit la kaspersky sau alte softuri de hack sau crack ca daca e vb de crack tata cumparam kaspersky nu umblam cu hackuri sau putem sal folosim trial 30 days

  8. Eu iam raspuns lui calipso care a intrebat daca poate recomanda anumite softuri. I-am explicat in ce conditii poate face recomandari.

  9. Am reinstalat BorlandC++ si nu mi s-a rezolvat problema.Te rog ajuta-ma daca ai vreo idee in aceasta situatie(kit-ul e bun)!

  10. e corect cum ati scris in pseudocod while(n=m)???…..

  11. scz….in c++

Lasă un răspuns

Your email address will not be published.

*

© 2018 PC-Config

Theme by Anders NorenUp ↑