Cel Mai Mare Divizor Comun- cmmdc

cmmdc

Înainte de a începe  să vă povestesc despre Replit, fost Repl.it, este un start-up cu sediul în San Francisco și un mediu de dezvoltare integrat online. Replit fiind Software ca serviciu permite utilizatorilor să creeze proiecte online și să scrie cod în multe limbi acceptate.

Interpretorul de Python este furnizat de acest site si aveti acces  la conținut în interfață sau în cloud unde este salvat fișierul numit repl

Concept

În matematică, cel mai mare divizor comun a două sau mai multe numere întregi, care nu sunt toate zero, este cel mai marenumăr întreg pozitiv care împarte fiecare dintre numerele întregi. Pentru două numere întregi x, y se notează cel mai maredivizor comun al lui x și y. De exemplu, cel mai mare factor comun dintre 20 și 15 este 5, deoarece 5 împarte atât 20, cât și 15și niciun număr mai mare nu are această proprietate. Conceptul este ușor de extins la seturi de mai mult de două numere:GCD-ul unui set de numere este cel mai mare număr care împarte fiecare dintre ele.

Utilitate

GCD este utilizat pentru o varietate de aplicații în teoria numerelor, în special în aritmetica modulară și, prin urmare, în algoritmide criptare, cum ar fi RSA.De asemenea, este folosit pentru aplicații mai simple, cum ar fi simplificarea fracțiilor. Acest lucru faceca GCD un concept destul de fundamental pentru teoria numerelor și, ca atare, au fost descoperiți o serie de algoritmi pentru a-lcalcula eficient.
RSA este un criptosistem cu cheie publică care este utilizat pe scară largă pentru transmiterea securizată a datelor. Este, deasemenea, unul dintre cele mai vechi sisteme .  Acronimul „RSA” provine de la numele de familie ale lui Ron Rivest, Adi Shamirși Leonard Adleman, care au descris public algoritmul în 1977

Abordari 

Vom menționa trei modalități diferite de a calcula cel mai mare divizor comun (GCD) a două numere în Python:

• Folosirea funcției integrale Python gcd() din modulul math: Aceasta este o modalitate simplă de a calculaGCD-ul a două numere, fără a fi nevoie să scrieți propriul cod.
• Algoritmul de forță brută: Aceasta implică verificarea tuturor numerelor între cele două numere date, începândde la cel mai mic, pentru a vedea dacă sunt divizori comuni ai ambelor numere.
• Algoritmul euclidian recursiv: Acesta se bazează pe faptul că GCD-ul a două numere este egal cu GCD-ul restuluiîmpărțirii lor și al numărului mai mic dintre ele. Aceasta implică apelarea recursivă a funcției pe ea însăși, folosindrestul împărțirii dintre numere ca argumente, până când se găsește GCD-ul
• Algoritmul euclidian pentru determinarea cmmdc-ului a doua numere,implementat intr-o functie care utilizeaza o bucla while

 

Un caz particular este – Algoritmul Euclidian folosind o buclă while cu iterația prin numerele în ordine inversă, de la cel maimare către cel mai mic, și verificarea dacă fiecare număr este un divizor comun al ambelor numere. Atunci când se găsește un divizor comun, acesta poate fi returnat ca fiind GCD-ul.

1.

Abordarea prin functia gcd() din biblioteca math
Există mai multe modalități de a calcula cel mai mare divizor comun (GCD) a două numere în Python. O altă abordare arputea fi folosirea funcției integrale Python gcd() din modulul math. Această funcție returnează GCD-ul a două numere, carepot fi pozitive sau negative.

PSEUDOCOD

1. 1. Importați modulul math, care conține funcția gcd.
   2. Cititi cele două numere de la tastatură folosind instrucțiunea input.
   3. Convertiți numerele la tipul int folosind funcția int.
   4. Păstrați rezultatul apelării funcției gcd pentru cele două numere într-o variabilă (de exemplu, result).
   5. Afișați rezultatul folosind instrucțiunea print.

PROGRAM PYTHON

 

 

 

2.

Abordarea unui algoritm de “forță brută”
Un algoritm de forță brută pentru a găsi cel mai mare divizor comun (GCD) a două numere ar putea fi unul care verificătoate numerele între ele și cele două numere dată, începând de la cel mai mic, pentru a vedea dacă sunt divizori comuniai ambelor numere. Atunci când se găsește un divizor comun, acesta poate fi returnat ca fiind GCD-ul.

 

PSEUDOCOD 

Acesta este un program care calculează cel mai mare divizor comun (GCD) pentru două numere folosind o funcție numită calc_gcd.
În pași, aici sunt etapele pe care le urmează programul:

1. 1. Definiți funcția calc_gcd care primește două argumente numite num1 și num2.
   2. Găsiți cel mai mic dintre cele două numere folosind funcția min și păstrați-l într-o variabilă numită celmaimic.
   3. Utilizați o structură de buclă for pentru a parcurge toate numerele între 1 și celmaimic (inclusiv).
   4. Verificați dacă fiecare număr din buclă este divizor atât pentru num1 cât și pentru num2 folosind operatorii de modulo (%). Dacă un număr este divizor pentru ambele numere, atunci păstrați-l într-o variabilă numită gcd.
   5. După ce bucla se termină, returnați valoarea lui gcd ca rezultat al funcției.
   6. Cititi cele două numere de la tastatură folosind instrucțiunea input.
   7. Apelați funcția calc_gcd cu cele două numere ca argumente și păstrați rezultatul într-o variabilă numită result.
   8. Afișați rezultatul folosind instrucțiunea print.

PROGRAM PYTHON

3.

Abordarea unui algoritm euclidian recursiv
Aici, vom găsi Cel mai mare divizor comun (GCD) folosind o funcție recursivă definită de utilizator. O funcție recursivăeste o funcție care se autoinvocă pe baza unei condiții.Dacă sunteți în căutarea unui program Python care calculeazăGCD folosind o funcție recursivă, sunteți la locul potrivit.

PSEUDOCOD

1. 1. Definiți o funcție numită calc_gcd care primește două argumente, num1 și num2.
   2. Verificați dacă num2 este egal cu 0. Dacă este adevărat, întoarceți num1 ca rezultat.
   3. Dacă num2 nu este egal cu 0, apelați din nou funcția calc_gcd cu num2 ca primul argument și cu num1 % num2 ca al doilea argument. Întoarceți rezultatul acestei apelări recursive ca rezultat al funcției.
   4. Cititi cele două numere de la tastatură folosind instrucțiunea input.
   5. Apelați funcția calc_gcd cu cele două numere ca argumente și păstrați rezultatul într-o variabilă numită result.
   6. Afișați rezultatul folosind instrucțiunea print.

PROGRAM PYTHON

Abordarea unui algoritm euclidian care utilizează o buclă while

PSEUDOCOD

1. 1. Definiți o funcție numită calc_gcd care ia două argumente, a și b.
   2. Utilizați o buclă while care să verifice dacă b este diferit de 0.
   3. Declarați o variabilă temporară numită t și atribuiți-i valoarea lui b.
   4. Atribuiți lui b rezultatul împărțirii lui a la b folosind operatorul modulo (%).
   5. Atribuiți lui a valoarea lui t.
   6. După ce bucla while s-a terminat, returnați valoarea lui a.
   7. Cititi cele două numere de la tastatură folosind instrucțiunea input.
   8. Apelați funcția calc_gcd cu cele două numere ca argumente și păstrați rezultatul într-o variabilă numită result.
   9. Afișați rezultatul folosind instrucțiunea print

PROGRAM PYTHON

 

 

5….ȘI NU PREA

Caz particular (nu intoarce intotdeauna cmmmdc real)

Abordarea unui algoritm euclidian cu bucla while cu iterare inversa
Algoritmul euclidian folosind o bucla while: Aceasta implica iterarea prin numerele in ordine inversa, de la cel mai mare catre cel mai mic, si verificarea daca fiecare numar este un divizor comun al ambelor numere. Atunci cand se gaseste un divizor comun, acesta poate fi returnat ca fiind cmmdc.

Functia care utilizeaza iterarea inversa pentru a determina cel mai mare divizor comun (cmmdc) a doua numere nu va calcula intotdeauna cmmdc-ul acestora. In schimb, aceasta functie va verifica daca fiecare numar intre cele doua numere date este un divizor comun al ambelor numere, in ordine inversa, de la cel mai mare catre cel mai mic. Daca se gaseste un divizor comun, acesta este returnat. Daca nu se gaseste un divizor comun dupa ce s-au parcurs toate numerele, atunci se returneaza 1.

Prin urmare, daca cele doua numere nu au un divizor comun mai mare decat 1, atunci aceasta functie va returna 1, in loc de cmmdc-ul lor real. De exemplu, daca cele doua numere sunt 2 si 3, cmmdc-ul lor este 1, dar functia va returna 1 indiferent daca a fost gasit sau nu un divizor comun.

PSEUDOCOD

1. 1. Definirea unei functii calc_gcd care ia două argumente, num1 și num2.
   2. Determinarea celui mai mare dintre cele două numere folosind funcția max() și păstrarea lui într-o variabilă numită celmaimic.
   3. Utilizarea unei bucle while pentru a parcurge numerele în ordine inversă, de la cel mai mare către cel mai mic.
   4. Verificarea dacă celmaimic este divizor comun pentru ambele numere folosind operatorii de modulo (%). Dacă un număr este divizor comun pentru ambele numere, întoarcerea lui ca GCD.
   5. Dacă nu se găsește un divizor comun după ce se parcurg toate numerele, atunci întoarcerea 1 ca valoare default.
   6. Citirea celor două numere de la tastatură folosind instrucțiunea input.
   7. Apelarea funcției calc_gcd cu cele două numere ca argumente și păstrarea rezultatului într-o variabilă numită result.
   8. Afișarea rezultatului folosind instrucțiunea print.

 

PROGRAM PYTHON

 

Utilizam :

Programe Python Variabile

Programe Python Liste

Site extern

replit