6,258 matches
-
se oprește. Ultimul rest nenul "r" este cel mai mare divizor comun al lui "a" și "b". Numărul "N" nu poate fi infinit deoarece există doar un număr finit de numere nenegative întregi între restul inițial "r" și zero. Corectitudinea algoritmului lui Euclid se poate demonstra în doi pași. La primul pas, se arată că ultimul rest nenul "r" divide atât pe "a" cât și pe "b". Cum este divizor comun, el trebuie să fie mai mic sau egal cu cel
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
divizor comun "g" divide "r", de unde rezultă că "g" ≤ "r". Întrucât în prima parte a demonstrației s-a arătat că ("r" ≤ " g"), rezultă că "g" = "r". Deci "g" este cel mai mare divizor comun al tuturor perechilor succesive: Pentru ilustrare, algoritmul lui Euclid se poate utiliza pentru a găsi cel mai mare divizor comun al lui "a" = 1071 și "b" = 462. Pentru început, multiplii lui 462 sunt scăzuți din 1071 până rămâne un rest mai mic decât 462. Se pot scădea
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
pot scădea ("q" = 3) și rămâne restul 21 Apoi se scad multiplii lui 21 din 147 până când restul este mai mic decât 21. Se pot scădea șapte multipli ("q" = 7) și nu rămâne niciun rest Cum ultimul rest este zero, algoritmul se termină cu 21 ca cel mai mare divizor comun al lui 1071 și 462. Rezultatul este în concordanță cu CMMDC(1071, 462) găsit prin factorizarea efectuată mai sus. În formă tabelară, pașii sunt: Algoritmul lui Euclid poate fi vizualizat
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
Cum ultimul rest este zero, algoritmul se termină cu 21 ca cel mai mare divizor comun al lui 1071 și 462. Rezultatul este în concordanță cu CMMDC(1071, 462) găsit prin factorizarea efectuată mai sus. În formă tabelară, pașii sunt: Algoritmul lui Euclid poate fi vizualizat în termenii analogiei pătratelor dată mai sus pentru cel mai mare divizor comun. Se presupune că se dorește acoperirea unui dreptunghi "a"-pe-"b" cu pătrate care să-l acopere exact, unde "a" este cel
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
laturilor celui mai mic pătrat este CMMDC al dimensiunilor dreptunghiului original. De exemplu, cel mai mic pătrat din figura alăturată este 21-pe-21 (cu roșu), iar 21 este CMMDC de 1071 și 462, dimensiunile dreptunghiului original (verde). La fiecare pas "k", algoritmul lui Euclid calculează un cât "q" și un rest "r" ale două numere "r" și "r" unde modulul lui "r" este strict mai mic decât cel al lui "r". Teorema împărțirii cu rest asigură că există întotdeauna acest cât și
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
decât cel al lui "r". Teorema împărțirii cu rest asigură că există întotdeauna acest cât și acest rest. Teorema împărțirii cu rest a numerelor naturale spune și că "q" și "r" sunt unice, dar unicitatea lor nu este necesară pentru algoritmul lui Euclid. În versiunea originală dată de Euclid pentru acest algoritm, câtul și restul se găsesc prin scădere repetată; adică "r" este scăzut din "r" repetat până când restul "r" este mai mic decât "r". O abordare mai eficientă utilizează împărțirea
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
există întotdeauna acest cât și acest rest. Teorema împărțirii cu rest a numerelor naturale spune și că "q" și "r" sunt unice, dar unicitatea lor nu este necesară pentru algoritmul lui Euclid. În versiunea originală dată de Euclid pentru acest algoritm, câtul și restul se găsesc prin scădere repetată; adică "r" este scăzut din "r" repetat până când restul "r" este mai mic decât "r". O abordare mai eficientă utilizează împărțirea numerelor întregi și operația modulo pentru a calcula respectiv câtul și
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
decât "r". O abordare mai eficientă utilizează împărțirea numerelor întregi și operația modulo pentru a calcula respectiv câtul și restul. Operația modulo dă restul împărțirii a două numere; astfel, Restul este echivalent cu clasa de congruență din aritmetica modulară. Implementările algoritmului se pot exprima în pseudocod. De exemplu, versiunea bazată pe împărțire trebuie să fie programată ca La îneputul iterației "k", variabila "b" deține ultimul rest "r", iar variabila "a" deține predecesorul acesteia, "r". Pasul "b" := "a" mod "b" este echivalent
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
462) = CMMDC(462, 147). Acest al doilea CMMDC se calculează din CMMDC(147, 462 mod 147) = CMMDC(147, 21), care la rândul său se calculează din CMMDC(21, 147 mod 21) = CMMDC(21, 0) = 21. Într-o altă versiune a algoritmului lui Euclid, câtul de la fiecare pas este crescut cu unu dacă restul negativ rezultat este mai mic în modul decât restul pozitiv tipic. Anterior, ecuația presupunea că "r" > "r" > 0. Se poate, însa, calcula și un alt rest negativ "e
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
poate, însa, calcula și un alt rest negativ "e" unde "r" este presupus pozitiv. Dacă |"e"| < |"r"|, atunci "r" este înlocuit de "e". După cum a arătat Leopold Kronecker, această versiune necesită cel mai mic număr de pași dintre toate versiunile algoritmului lui Euclid. Algoritmul lui Euclid este unul dintre cei mai vechi algoritmi încă în uz. El apare în "Elemente" (c. 300 î.e.n.), anume în Cartea 7 (Propunerile 1-2) și în Cartea 10 (Propunerile 2-3). În Cartea 7, algoritmul este formulat
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
și un alt rest negativ "e" unde "r" este presupus pozitiv. Dacă |"e"| < |"r"|, atunci "r" este înlocuit de "e". După cum a arătat Leopold Kronecker, această versiune necesită cel mai mic număr de pași dintre toate versiunile algoritmului lui Euclid. Algoritmul lui Euclid este unul dintre cei mai vechi algoritmi încă în uz. El apare în "Elemente" (c. 300 î.e.n.), anume în Cartea 7 (Propunerile 1-2) și în Cartea 10 (Propunerile 2-3). În Cartea 7, algoritmul este formulat pentru întregi, pe când
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
presupus pozitiv. Dacă |"e"| < |"r"|, atunci "r" este înlocuit de "e". După cum a arătat Leopold Kronecker, această versiune necesită cel mai mic număr de pași dintre toate versiunile algoritmului lui Euclid. Algoritmul lui Euclid este unul dintre cei mai vechi algoritmi încă în uz. El apare în "Elemente" (c. 300 î.e.n.), anume în Cartea 7 (Propunerile 1-2) și în Cartea 10 (Propunerile 2-3). În Cartea 7, algoritmul este formulat pentru întregi, pe când în Cartea 10, el este formulat pentru lungimi de
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
toate versiunile algoritmului lui Euclid. Algoritmul lui Euclid este unul dintre cei mai vechi algoritmi încă în uz. El apare în "Elemente" (c. 300 î.e.n.), anume în Cartea 7 (Propunerile 1-2) și în Cartea 10 (Propunerile 2-3). În Cartea 7, algoritmul este formulat pentru întregi, pe când în Cartea 10, el este formulat pentru lungimi de segmente de dreaptă. (în uz modern, s-ar spune că a fost formulat pentru numere reale. Dar lungimile, ariile și volumele, reprezentate ca numere reale în
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
ariile și volumele, reprezentate ca numere reale în uz modern, nu se măsoară în aceleași unități și nu există o unitate naturală de lungime, arie sau volum, iar conceptul de numere reale nu era cunoscut la acea vreme.) Al doilea algoritm este geometric. CMMDC al două lungimi "a" și "b" corespunde celei mai mari lungimi "g" care măsoară "a" și "b" exact; cu alte cuvinte, lungimile "a" și "b" sunt ambele multipli întregi ai lungimii "g". Algoritmul nu a fost, probabil
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
acea vreme.) Al doilea algoritm este geometric. CMMDC al două lungimi "a" și "b" corespunde celei mai mari lungimi "g" care măsoară "a" și "b" exact; cu alte cuvinte, lungimile "a" și "b" sunt ambele multipli întregi ai lungimii "g". Algoritmul nu a fost, probabil, descoperit de Euclid, care doar a compilat rezultate ale matematicienilor dinaintea sa în lucrarea "Elemente". Matematicianul și istoricul B. L. van der Waerden sugerează că Cartea VII derivă dintr-un manual de teoria numerelor scris de
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
de Euclid, care doar a compilat rezultate ale matematicienilor dinaintea sa în lucrarea "Elemente". Matematicianul și istoricul B. L. van der Waerden sugerează că Cartea VII derivă dintr-un manual de teoria numerelor scris de matematicieni ai școlii lui Pitagora. Algoritmul a fost probabil cunoscut lui Eudoxus din Cnidus (circa 375 î.e.n.) Algoritmul ar putea fi dinainte chiar și de Eudoxus, judecând după utilizarea termenului tehnic ἀνθυφαίρεσις ("anthyphairesis", scădere reciprocă) din lucrările lui Euclid și Aristotel. După mai multe secole, algoritmul
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
lucrarea "Elemente". Matematicianul și istoricul B. L. van der Waerden sugerează că Cartea VII derivă dintr-un manual de teoria numerelor scris de matematicieni ai școlii lui Pitagora. Algoritmul a fost probabil cunoscut lui Eudoxus din Cnidus (circa 375 î.e.n.) Algoritmul ar putea fi dinainte chiar și de Eudoxus, judecând după utilizarea termenului tehnic ἀνθυφαίρεσις ("anthyphairesis", scădere reciprocă) din lucrările lui Euclid și Aristotel. După mai multe secole, algoritmul lui Euclid a fost descoperit independent în India și în China, și
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
Algoritmul a fost probabil cunoscut lui Eudoxus din Cnidus (circa 375 î.e.n.) Algoritmul ar putea fi dinainte chiar și de Eudoxus, judecând după utilizarea termenului tehnic ἀνθυφαίρεσις ("anthyphairesis", scădere reciprocă) din lucrările lui Euclid și Aristotel. După mai multe secole, algoritmul lui Euclid a fost descoperit independent în India și în China, și a fost utilizat mai ales pentru rezolvarea de ecuații diofantice care apar în astronomie și la realizarea de calendare precise. Spre sfârșitul secolului al V-lea, matematicianul și
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
independent în India și în China, și a fost utilizat mai ales pentru rezolvarea de ecuații diofantice care apar în astronomie și la realizarea de calendare precise. Spre sfârșitul secolului al V-lea, matematicianul și astronomul indian Aryabhata a descris algoritmul sub numele de „pulverizatorul”, poate din cauza eficienței sale în rezolvarea de ecuațiilor diofantice. Deși un caz special al teoremei chinezești a resturilor fusese deja descris de matematicianul și astronomul chinez Sun Tzu, soluția generală a fost publicată de Qin Jiushao
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
un caz special al teoremei chinezești a resturilor fusese deja descris de matematicianul și astronomul chinez Sun Tzu, soluția generală a fost publicată de Qin Jiushao în cartea sa din 1247 intitulată "Shushu Jiuzhang" (數書九章 „Tratat matematic în nouă secțiuni”). Algoritmul lui Euclid a fost descris în Europa pentru prima dată în a doua ediție a lucrării lui Bachet "Problèmes plaisants et délectables" ("Probleme plăcute și delectabile", 1624). În Europa, a fost folosit tot pentru rezolvarea de ecuații diofantice, dar și
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
descris în Europa pentru prima dată în a doua ediție a lucrării lui Bachet "Problèmes plaisants et délectables" ("Probleme plăcute și delectabile", 1624). În Europa, a fost folosit tot pentru rezolvarea de ecuații diofantice, dar și la construcția fracțiilor continue. Algoritmul lui Euclid extins a fost publicat de matematicianul englez Nicholas Saunderson, care i l-a atribuit lui Roger Cotes ca metodă de calcul eficient a fracțiilor continue. În secolul al XIX-lea, algoritmul lui Euclid a dus la dezvoltarea unor
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
diofantice, dar și la construcția fracțiilor continue. Algoritmul lui Euclid extins a fost publicat de matematicianul englez Nicholas Saunderson, care i l-a atribuit lui Roger Cotes ca metodă de calcul eficient a fracțiilor continue. În secolul al XIX-lea, algoritmul lui Euclid a dus la dezvoltarea unor noi sisteme de numere, cum ar fi întregii gaussieni și întregii eisensteinieni. În 1815, Carl Gauss a utilizat algoritmul lui Euclid pentru a demonstra factorizarea unică a întregilor gaussieni, deși lucrarea sa a
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
Cotes ca metodă de calcul eficient a fracțiilor continue. În secolul al XIX-lea, algoritmul lui Euclid a dus la dezvoltarea unor noi sisteme de numere, cum ar fi întregii gaussieni și întregii eisensteinieni. În 1815, Carl Gauss a utilizat algoritmul lui Euclid pentru a demonstra factorizarea unică a întregilor gaussieni, deși lucrarea sa a fost publicată pentru prima oară în 1832. Gauss a menționat algoritmul în "Disquisitiones Arithmeticae" (publicat la 1801), dar numai ca metodă pentru fracțiile continue. Peter Dirichlet
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
numere, cum ar fi întregii gaussieni și întregii eisensteinieni. În 1815, Carl Gauss a utilizat algoritmul lui Euclid pentru a demonstra factorizarea unică a întregilor gaussieni, deși lucrarea sa a fost publicată pentru prima oară în 1832. Gauss a menționat algoritmul în "Disquisitiones Arithmeticae" (publicat la 1801), dar numai ca metodă pentru fracțiile continue. Peter Dirichlet pare a fi fost primul care a descris algoritmul lui Euclid ca bază pentru teoria numerelor. Dirichlet a observat că multe din rezultatele teoriei numerelor
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
întregilor gaussieni, deși lucrarea sa a fost publicată pentru prima oară în 1832. Gauss a menționat algoritmul în "Disquisitiones Arithmeticae" (publicat la 1801), dar numai ca metodă pentru fracțiile continue. Peter Dirichlet pare a fi fost primul care a descris algoritmul lui Euclid ca bază pentru teoria numerelor. Dirichlet a observat că multe din rezultatele teoriei numerelor, cum ar fi unicitatea factorizării, sunt adevărate pentru toate celelalte sisteme de numere în care se poate aplica algoritmul lui Euclid. Cursurile lui Dirichlet
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]