Prezentare pentru ocuparea algoritmului euclidian al cercului. Prezentare pe tema „Algoritmul lui Euclid”. Ideea algoritmului lui Euclid

Clasă: 6

Obiectivele lecției:

• reparați algoritmul pentru găsirea celui mai mare divizor comun folosind factorizarea;
• repeta definițiile și conceptele conexe;
• introducerea elevilor în algoritmul Euclid;
• pentru a forma deprinderile culturii matematice

Echipament: calculator, proiector, ecran.

În timpul orelor

1. Moment de organizare (verificarea gradului de pregătire a elevilor pentru lecție, notarea absentei) (1 min.)

2. Lucrare orală: (6 min)

1. Înlocuiți produsul cu un grad:

d) a * a * a * a * a

1. Calculați: 2 3 ; 52; 3 3 ; 10 4 .
2. Aflați valoarea expresiei: (3?3?5?11): (3?11). Ce concluzie se poate trage?
3. Efectuați împărțirea A pe b dacă a=170, b=35. Notați egalitatea, ceea ce este egal cu a.

Scrieți această egalitate în formă generală: a va fi divizibil, iar b va fi divizor. Fie câtul q și restul r, atunci: a = bq + r , iar q poate fi fie un număr natural, fie zero. Poate fi orice număr? [ r este un număr natural și 0 < r < b .] Ce se poate spune despre numerele a și b dacă r = 0? Împărțirea întregului este un caz special de împărțire cu un rest.

4. Aflați și explicați dacă numărul a este divizibil cu numărul b fără rest dacă:

a) a = 2 3 * 3 * 5 * 7;

b) a \u003d 2 4 * 3 * 5 7;

b = 2 7 * 3 * 5 4

c) a \u003d 2 * 3 4 * 5 * 13;

b = 2 * 3 3 * 5 * 11.

3. Actualizarea cunoștințelor de bază(10 minute)

1) Întrebări:

Ce este un divizor de numere A ?

Ce este un număr prim?

Ce înseamnă factorizarea unui număr în factori primi?

Formulați semne de divizibilitate cu 2, 3, 5, 9,10;

Dați un exemplu de număr compus dintr-o singură cifră;

Este adevărat că numărul 77 este un număr prim?

De ce, dacă un număr poate fi descompus în 2 factori primi, iar celălalt în 3 factori primi, atunci aceste numere nu sunt egale?

Care număr, prim sau compus, este produsul a două numere prime?

Care este cel mai mare divizor comun a două sau mai multe numere?

Ce numere se numesc coprime?

Repetă moduri de a găsi GCD: Există diferiți algoritmi pentru găsirea GCD al numerelor naturale.

1 cale: Dacă sunt date două numere și sunt relativ mici, atunci cel mai bun algoritm este căutarea prin forță brută. Cu toate acestea, pentru numere mari, găsiți mcd(a;b) prin enumerarea tuturor divizorilor numerelor Ași b Procesul este laborios și nesigur.

Este util să ne amintim că mcd-ul oricărui număr de numere nu îl depășește pe cel mai mic dintre ele.

2 moduri: prin factorizarea numerelor (cel mai frecvent) (Anexă, slide1)

2) Calculați GCD-ul numerelor 24 și 16.

3) Factorizează numerele: 875 și 8000 și calculează GCD-ul acestor numere.

(Folosind numărul 8000 ca exemplu, repetați un mod mai simplu de factorizare a numerelor care se termină cu zerouri: deoarece 10=2 *5, apoi 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 *5 3)

4) Poate MCD a trei numere să fie egal cu 15 dacă produsul lor este egal cu 3000? [ Nu, la fel de

15 \u003d 3 * 5, ceea ce înseamnă că numărul 3 trebuie inclus în extinderea fiecăruia dintre cele trei numere. Dar, 3000 = 2 3 * 3 * 5 3 .]

5) P mănâncă sarcina„La clasă au fost aduse manuale: 24 la matematică, 36 la istorie și 48 la geografie. Care este cel mai mare număr de seturi care se poate face din aceste cărți astfel încât fiecare să conțină același număr de cărți la matematică, istorie și geografie? Câte cărți vor fi în fiecare set?"

4. Lucrare de verificare (Anexă, slide 2) (6 min)

5. Învățarea de materiale noi (10 min)

Profesor: Metoda studiată de a găsi GCD(a, b) este simplă, de înțeles și convenabilă, dar are un dezavantaj semnificativ: dacă numerele date sunt mari și chiar nu sunt foarte ușor de factorizat, atunci sarcina de a găsi GCD(a, b) devine destul de dificil. În plus, se poate dovedi că, după ce am muncit din greu, ne vom asigura că GCD(a, b) = 1 și se pare că toată munca a fost făcută în zadar.

Euclid a găsit o modalitate minunată de a găsi mcd(a, b) fără nicio preprocesare a numerelor. (Anexă, diapozitivele 3 și 4) Ulterior, acest algoritm a devenit cunoscut ca algoritmul lui Euclid)

Să facem cunoștință cu algoritmul Euclid. Să fie necesar să se găsească gcd(102;84). Împărțiți un număr la altul și găsiți restul.

Acum să facem aceeași operație pentru numerele 84 și 18:

Următorul pas este pentru 18 și 12:

Acum - pentru 12 și 6:

0-reziduu. Procesul s-a încheiat.

Acest proces nu poate fi infinit, deoarece reziduurile scad, ramanand numere întregi nenegative, a căror mulțime, după cum se știe, este mărginită de jos:

84 >18 > 12> 6 >0

Dacă te uiți îndeaproape la egalitățile scrise, poți stabili că GCD-urile tuturor perechilor de numere sunt egale între ele (invitați elevii să se gândească - de ce?),

adică gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. Dar numărul 6 este ultimul rest non-0 .

Într-adevăr, dacă c este un divizor comun arbitrar al numerelor a și b, atunci r = a - bq este divizibil cu c; și invers, dacă c este un divizor comun arbitrar al lui b și r, atunci a este divizibil cu c. Adică toți divizorii comuni ai perechilor (a; b) și (b; r) coincid și, prin urmare, cei mai mari divizori comuni ai lor coincid.

Comoditatea algoritmului lui Euclid devine deosebit de remarcabilă dacă aplicăm forma notației sub forma unui tabel:

În această tabletă, numerele originale sunt mai întâi notate, împărțite în minte, scriind resturile în dreapta, iar cele private în jos, până la sfârșitul procesului. Ultimul divizor este GCD.

Astfel, cel mai mare divizor comun a două numere este ultimul rest, nu egal cu 0, la împărțirea unui număr mai mare la unul mai mic, adică dacă a = b*q + r, atunci mcd(a; b) = mcd(b; r)

Această secvență de operații este numită algoritmul lui Euclid. Acest algoritm vă permite să găsiți GCD-ul numerelor fără a le factoriza (Anexa, slide 5)

6. Exerciții (10 min)

1. Este indicat să luați în considerare un exemplu. Să fie necesar să găsim MCD al numerelor 323 și 437. Nu este ușor să faceți acest lucru prin selecție sau descompunere în factori primi, deoarece niciunul dintre aceste numere nu este multiplu al lui 2, 3, 5, 7, 11. Noi procedați după cum urmează (

Subiect: Algoritmul lui Euclid pentru găsirea GCD.

Obiective:repetați subiectele studiate anterior Cel mai mare divizor comun și cel mai mic multiplu comun, introduceți algoritmul lui Euclid.

Obiective de învățare - să repeți conceptele de cel mai mare divizor comun și cel mai mic multiplu comun, regula de a le găsi. Introducere în algoritmul lui Euclid. Remediați algoritmul lui Euclid rezolvând sarcinile corespunzătoare.

Sarcini de dezvoltare - dezvoltarea gândirii logice, atenția, memoria vorbirii, capacitatea de a descoperi în mod independent noi cunoștințe, curiozitatea matematică, interesul cognitiv pentru subiect.

Sarcinile educației sunt de a cultiva o cultură a gândirii matematice, asistență reciprocă, autoexaminare și analiza greșelilor cuiva.

Lucrați pe cărți

Găsiți numere GCD sau LCM și descifrați expresia:

34

16

300

6

1

12

2

34

11

17

D: GCD(33,88)

H: NOC(9,40)

A: NOK(14,42)

E: GCD(48,18)

R: NOC(17,5)

C: GCD(48,24)

K: GCD (72,12)

L: GCD(20,14)

E: GCD(30,18)

M: NOC(25,12)

T: NOC(4,8,16)

H: NOC(12,40)

B: GCD(18,35)

A: GCD(17,34)

I: gcd(102,68)

E: GCD(18,12)

În ultimul tabel, notează perechile de numere rămase

Raspunsuri:

34

16

300

6

1

12

2

34

11

17

DAR

L

G

O

R

Și

T

M

E

LA

La

L

Și

D

DAR

D: GCD(33,88)=11

G: LCM(9,40)=360

A: LCM(14,42)=42

E: GCD(48,18)=6

P: LCM(17,5)=85

C: GCD(48,24)=24

K: GCD (72,12)=12

L: GCD(20,14)=2

E: GCD(30,18)=6

M: LCM(25,12)=300

T: LCM(4,8,16)=16

H: LCM(12,40)=120

B: mcd(18,35)=1

A: GCD(17,34)=17

ȘI: GCD(102,68)=34

E: GCD(18,12)=6

Ghiciți încă 2 cuvinte

Ce se poate spune despre numerele din ultimul tabel? Sunt coprime, adică. dacă descompunem aceste numere în factori primi, atunci ei nu vor avea aceiași factori. Cum să găsiți GCD-ul unor astfel de numere? Nod de astfel de numere =1. Și cum să găsiți LCM, pentru a găsi LCM, trebuie să înmulțiți aceste numere unele cu altele.

În prima coloană sunt perechi de numere, în care unul dintre ele nu este complet divizibil cu celălalt. Acestea. restul nu este 0.

Cum ați găsit GCD și LCM ale unor astfel de numere. (Prin descompunerea acestor numere în factori primi)

LCM(12,40)=2 3 *3*5=120

Amintiți-vă regula pentru găsirea GCD și LCM, găsiți și verificați formula LCM (a, c) \u003d (a * b): GCD (a, b)

3 *3*11=264

LCM (a, b) \u003d (a * b): GCD (a, b)

264=(33*88):11=3*88=264

LCM(20,14)=2 2 *5*7=140

LCM (a, b) \u003d (a * b): GCD (a, b)

140=(20*14):2=10*14=140

GCD(12,40)=2 2 =4

LCM (a, b) \u003d (a * b): GCD (a, b)

120=(12*40):4=3*4=120

Explorarea unui subiect nou:

MCD din ce perechi de numere este 6?

6=mcd(48,18)=mcd(30,18)=mcd(12,18)

Ce ai observat? Cum ai luat 30? 48-18

Cum ai luat 12? 30-18

Când a> b \u003d GCD (a-b, c)

Acestea. GCD (a, c) Când v> a = GCD (a, c-a)

Cine poate continua această egalitate?

6=mcd(48.18)=mcd(30.18)=mgcd(12.18) = mcd(12.6)=mgcd(6.6)=6

Algoritmul lui Euclid se bazează pe această regulă.

algoritmul lui Euclid- eficient pentru a găsi două . Algoritmul este numit după, care l-a descris pentru prima dată în cărțile VII și X "".

În cel mai simplu caz, algoritmul lui Euclid este aplicat unei perechi de numere întregi pozitive și generează o nouă pereche care constă dintr-un număr mai mic și între un număr din ce în ce mai mare. Procesul se repetă până când numerele sunt egale. Numărul găsit este cel mai mare divizor comun al perechii originale.

Matematicienii greci antici au numit acest algoritm „scădere reciprocă”.

Esența acestei metode este următoarea: scădeți numărul mai mic din numărul mai mare până când numerele sunt egale, înlocuindu-l pe cel mai mare cu diferența. Odată ce se întâmplă acest lucru, GCD-ul este găsit. (Exemplu pe tablă - numerele 48 și 18)

Prima întrebare este, sunt aceste numere egale? Nu, ele nu sunt egale, prin urmare îi scadem pe cel mai mic din cel mai mare 48-18 = 30. 30 nu este egal cu 18, ceea ce înseamnă 30-18= 12, 18-12=6, 12-6=6. Adică, efectuăm aceste acțiuni până când numerele sunt egale. Prin urmare, mcd(48,18)=6

Cunoscând GCD-ul numerelor 48 și 18, găsiți NOC. LCM(48,18)=(48*18):6=48*3=144

Să găsim GCD(102;68) folosind algoritmul lui Euclid.

Sa gasim NOD (357;273)

Aici am scăzut numărul 84 de 3 ori și numărul 21 de trei ori.

Cum, fără a face scăderi, să afli câte scăderi vor fi într-o serie și ce diferență va fi rezultatul? Ce cazuri trebuie luate în considerare? ( indicaţie: amintiți-vă împărțirea.)

Regula generală poate fi formulată astfel: dacă numărul A nedivizibil cu b, apoi este înlocuit cu restul său atunci când este împărțit la b(când A< b acest rest este A); dacă A impartit de b, apoi înlocuiți-l cu un număr b. Exact aceeași regulă, cu o permutare Ași b, este valabil si pentru b. Număr mai mare divide la cel mai mic, apoi cel mai mic la primul rest, apoi primul rest la al doilea rest și așa mai departe, până când obțineți 0. Apoiultimul rest care nu este egal cu 0 este GCD .

Găsiți GCD (357;273).

357 273 273 84 84 21 GCD (357; 273) = 21

273 1 252 3 21 4

84 21 0

357=1*273+84 273=3*84+21 84=4*21

mcd(357,273)=mcd(273,84)=mcd(84,21)=21

Comoditatea algoritmului lui Euclid devine deosebit de remarcabilă dacă aplicăm forma notației sub forma unui tabel:

În această tabletă, numerele originale sunt mai întâi notate, împărțite în minte, scriind resturile în dreapta, iar cele private în jos, până la sfârșitul procesului. Ultimul divizor este GCD.

Astfel, cel mai mare divizor comun a două numere este ultimul rest diferit de zero atunci când se împarte numărul mai mare la cel mai mic., adicădacă a = b *q + r, atunci mcd(a; b) = mcd(b; r)

Această secvență de operații este numită algoritmul lui Euclid.

1) Folosind algoritmul Euclid, găsiți GCD-ul numerelor:

A) 703, 481; B) 2112 și 1680; B) 5075 și 1450

GCD(703;481)=37

GCD(2112;1680)=48

GCD(5075;1450)=

Verificați rezultatele pe computer.

Sarcina copiilor pe computer este să găsească GCD și LCM pentru trei numere folosind programul pentru găsirea GCD și LCM.

mcd(150, ____) = ____

GCD(450.315.135)=____

GCD(135, ____) = ____

GCD(2160,1350,1080)=____

GCD (1080, ____) = ____

GCD(5300,3180,2120)=____

GCD (2120, ____) = ____

(Pentru a găsi MCD a trei sau mai multe numere, găsiți mai întâi MCD a oricăror două dintre ele, apoi MCD al divizorului găsit și al treilea număr dat.

iar al treilea număr dat.

7. Verificarea rezultatelor pe un computer. Rezolvarea independentă a problemelor.

1) Au fost pregătite aceleași cadouri pentru elevii clasei. Toate cadourile au inclus 120 de ciocolată, 280 de dulciuri și 320 de nuci. Câți elevi sunt în clasa I dacă se știe că sunt mai mult de 30?

Răspuns:________________________

2) În gară sunt trei trenuri de călători: în primul - 418 locuri în vagoane compartiment, în al doilea - 494, iar în al treilea - 456. Câte vagoane compartiment sunt în fiecare tren dacă există același număr de locuri. în fiecare mașină și numărul lor total este mai mare de 20? Răspuns _________________________

3) S-au făcut buchete din 156 de ceai, 234 de trandafiri albi și 390 de trandafiri roșii, iar în toate buchetele de trandafiri de fiecare tip au fost în mod egal și numărul acestor buchete a fost mai mare de 50. Câte buchete s-au făcut din acești trandafiri și câte trandafiri de fiecare tip au fost într-un singur buchet? Răspuns_________________

Rezumatul lecției. Cu ce ​​mod de a găsi GCD și LCM ne-am întâlnit în lecție. algoritmul lui Euclid. Care este alt nume pentru această metodă? (metoda scăderii). Cum a fost îmbunătățită această metodă? Cu împărțirea, numărul mai mare este împărțit la numărul mai mic, apoi numărul mai mic la primul rest, apoi primul rest la al doilea rest și așa mai departe, până când obțineți 0. Ultimul rest diferit de zero este MCD al numerele.

Pentru a utiliza previzualizarea prezentărilor, creați un cont Google (cont) și conectați-vă: https://accounts.google.com

Subtitrările diapozitivelor:

Algoritmul lui Euclid Euclid, matematician grec antic. A lucrat la Alexandria în secolul al III-lea. î.Hr e. Lucrarea principală „Începuturi” (15 cărți), care conține bazele matematicii antice, geometria elementară, teoria numerelor, teoria generală a relațiilor și metoda de determinare a suprafețelor și volumelor, care cuprindea elemente ale teoriei limitelor. A avut o mare influență asupra dezvoltării matematicii. Lucrări de astronomie, optică, teoria muzicii. Euclid (365-300 î.Hr.)

ALGORITMUL LUI EUCLID Algoritmul lui Euclid este un algoritm pentru găsirea celui mai mare divizor comun (mcd) a două numere întregi nenegative. Euclid (365-300 î.Hr.) Matematicienii greci antici au numit acest algoritm ἀνθυφαίρεσις sau ἀνταναίρεσις - „scădere reciprocă”.

Calcul GCD GCD = cel mai mare divizor comun a două numere naturale este cel mai mare număr cu care ambele numere originale sunt divizibile fără rest. mcd(a , b)= mcd(a-b, b)= mcd(a, b-a) Înlocuiți cel mai mare dintre cele două numere cu diferența dintre cel mai mare și mai mic până când sunt egale. Acesta este NOD. mcd(18, 45) = mcd(18, 45-18) = mcd(18, 27) = mcd(18, 9) = =mcd(9,9)=9 Exemplu:

PAS Funcționare M N Condiție 1 Intrare M 48 2 Intrare N 18 3 M  N 48 18, da 4 M>N 48>18, da 5 M:=M-N 30 6 M  N 30  18, da 7 M>N 30 >18, da 8 M:=M-N 12 9 M  N 12 18, da 10 M>N 12 >18, nu 11 N:=N-M 6 12 M  N 12  6, da 13 M>N 12 >6 , da 14 M:=M-N 6 15 M  N 6  6, nu 16 Ieșire M

programul Evklid ; var m, n: întreg; begin writeln("vved 2 chisla"); readln(m,n); în timp ce mn începe dacă m>n atunci m:=m-n altfel n:= n-m ; Sfârşit; scrie ("nod=",m); readln sfârşitul.

0. Rulați programul Evklid pe computer. Testați-l cu M=32, N=24; M=696, N=234. unu . Verificați dacă două numere date sunt coprime. Notă. Se spune că două numere sunt între prime dacă cel mai mare divizor comun al lor este 1. 2 . Aflați cel mai mic multiplu comun (LCM) al numerelor n și m dacă LCM(n, m) = n * m / mcd(n, m). 3 . Sunt date numere naturale m și n. Aflați numere naturale p și q care nu au divizori comuni astfel încât p / q = m / n . 4. Găsiți GCD-ul a trei numere. Notă. GCD(a, b, c)= GCD(gcd(a, b), c) Sarcini

Previzualizare:

Subiect: „Algoritmul lui Euclid”

Obiectivele lecției:

1. Educational:

1. învață cum să folosești algoritmul Euclid pentru a găsi mcd-ul a două și trei numere
2. consolidarea abilităților de utilizare a structurilor algoritmice „Branching” și „Cycle”
3. dobândiți experiență în scrierea și depanarea programelor în limbajul de programare Pascal

1. Educational:

1. formarea independenței și a responsabilității în studiul materialelor noi

1. În curs de dezvoltare:

1. dezvoltarea atenției și gândirii analitice

Planul lecției:

1. Organizarea timpului
2. Actualizare de cunoștințe
3. Explicarea noului subiect
4. Partea practică
5. Rezumând lecția
6. Teme pentru acasă.

Organizarea timpului

Salutari. Cine este absent. Număr. Subiectul lecției. Întrebări despre teme.

Actualizare de cunoștințe.

Întrebări:

Ce tipuri de structuri algoritmice cunoașteți?

Ce este o structură liniară? (B-sh)

Ce este o structură ramificată? (B-sh)

Ce este o structură ciclică? (B-sh)

Ce tipuri de cicluri cunoașteți?

Cum este implementată o buclă cu un număr cunoscut de repetări în limbajul de programare Pascal?

Cum este implementată o buclă cu un număr necunoscut de repetări în limbajul de programare Pascal?

Explicarea unui subiect nou (prezentare)

Despre Euclid;

Ideea algoritmului lui Euclid

Ideea acestui algoritm se bazează pe:

1. Proprietatea că dacă M>N, atunci GCD(M, N) = GCD(M - N, N).

Cu alte cuvinte, mcd-ul a două numere naturale este egal cu mcd-ul diferenței lor pozitive (modulul diferenței lor) și al numărului mai mic.

Dovada: fie K un divizor comun al lui M și N (M > N). Aceasta înseamnă că M \u003d mK, N \u003d nK, unde m, n sunt numere naturale și m > n. Apoi M - N \u003d K (m - n), ceea ce implică că K este un divizor al numărului M - N. Prin urmare, toți divizorii comuni ai numerelor M și N sunt divizori ai diferenței lor M - N, inclusiv cel mai mare divizor comun.

2.A doua proprietate evidentă:

GCD(M, M) = M.

Pentru numărarea „manuală”, algoritmul lui Euclid arată astfel:

1) dacă numerele sunt egale, atunci luați oricare dintre ele ca răspuns, altfel continuați algoritmul;

2) înlocuiți numărul mai mare cu diferența dintre numărul mai mare și cel mai mic dintre numere;

3) revenirea la punerea în aplicare a alineatului 1.

Diagrama bloc a algoritmului Euclid

Program în JS Pascal

programul Evklid;

var m, n: întreg;

ÎNCEPE

writeln("vved 2 numere");

readln(m,n);

În timp ce mn fac

ÎNCEPE

Dacă m>n

Atunci m:=m-n

Altfel n:=n-m;

Sfârşit;

Scrie ("nod=",m);

readln

Sfârşit.

Partea practică

Întrebări și sarcini:

1. Rulați programul Evklid pe computer. Testați-l pe M=32, N=24; M = 696, N = 234.
2. Verificați dacă două numere date sunt coprime. Notă. Se spune că două numere sunt între prime dacă cel mai mare divizor comun al lor este 1.

Rezumând lecția

Astăzi în lecție ne-am familiarizat cu algoritmul Euclid, care ne permite să găsim GCD-ul a două numere întregi nenegative, am scris un program în limbajul de programare Pascal care implementează acest algoritm. Acasă, vei primi o sarcină în care vei aplica acest algoritm pentru a găsi GCD-ul a trei numere și LCM-ul a două numere.

Teme pentru acasă.

1. Scrieți un program pentru a găsi cel mai mare divizor comun al trei numere folosind următoarea formulă:

mcd(A, B, C) = mcd(mcd(A, B), C)

2. Scrieți un program pentru găsirea celui mai mic multiplu comun (LCM) a două numere folosind formula:

A  B \u003d GCD (A, B)  LCM (A, B)

Enunțarea problemei Luați în considerare următoarea problemă: este necesar să se scrie un program pentru determinarea celui mai mare divizor comun (MCD) a două numere naturale. Să ne amintim de matematică. Cel mai mare divizor comun al două numere naturale este cel mai mare număr natural cu care acestea sunt divizibile egal. De exemplu, numerele 12 și 18 au divizori comuni: 2, 3, 6. Cel mai mare divizor comun este numărul 6. Acesta se scrie după cum urmează: mcd(12,18) = 6. Notați datele inițiale ca M și N Enunțul problemei este după cum urmează: Dat: M, N Găsiți: GCD(M, N).

N, apoi GCD(M,N) = GCD(M - N,N). Cu alte cuvinte, mcd-ul a două numere naturale este egal cu mcd-ul diferenței lor pozitive și al numărului mai mic." title="(!LANG:Ideea algoritmului Ideea acestui algoritm se bazează pe proprietate că dacă M>N, atunci mcd(M,N) = mcd( M - N, N) Cu alte cuvinte, mcd a două numere naturale este egal cu mcd a diferenței lor pozitive și a numărului mai mic." class="link_thumb"> 4 !} Ideea algoritmului Ideea acestui algoritm se bazează pe proprietatea că dacă M>N, atunci GCD(M,N) = GCD(M - N,N). Cu alte cuvinte, mcd a două numere naturale este egal cu mcd a diferenței lor pozitive și a numărului mai mic. N, apoi GCD(M,N) = GCD(M - N,N). Cu alte cuvinte, mcd a două numere naturale este egal cu mcd a diferenței lor pozitive și a numărului mai mic."> N, apoi mcd(M,N) = mcd(M - N,N). Cu alte cuvinte, mcd a două numere naturale este egal cu mcd a diferenței lor pozitive și a numărului mai mic."> N, apoi GCD(M,N) = MCD(M - N,N). Cu alte cuvinte, mcd-ul a două numere naturale este egal cu mcd-ul diferenței lor pozitive și al numărului mai mic." title="(!LANG:Ideea algoritmului Ideea acestui algoritm se bazează pe proprietate că dacă M>N, atunci mcd(M,N) = mcd( M - N, N) Cu alte cuvinte, mcd a două numere naturale este egal cu mcd a diferenței lor pozitive și a numărului mai mic."> title="Ideea algoritmului Ideea acestui algoritm se bazează pe proprietatea că dacă M>N, atunci GCD(M,N) = GCD(M - N,N). Cu alte cuvinte, mcd a două numere naturale este egal cu mcd a diferenței lor pozitive și a numărului mai mic."> !}

N). Aceasta înseamnă că M = mK, N = pK, unde m, n sunt numere naturale și m>n. Atunci M - N = K(m - n), de unde rezultă că K este un divizor al lui M - N. Prin urmare, toți divizorii comuni ai lui M și N sunt divizori" title="(!LANG:Proof Fie K un comun comun divizor al lui M și N (M > N). Aceasta înseamnă că M = mK, N = pK, unde m, n sunt numere naturale și m> n. Atunci M - N = K(m - n), de unde rezultă că K este un divizor al numărului M - N. Prin urmare, toți divizorii comuni ai numerelor M și N sunt divizori" class="link_thumb"> 5 !} Demonstrație Fie K un divizor comun al lui M și. N (M>N). Aceasta înseamnă că M = mK, N = pK, unde m, n sunt numere naturale și m>n. Atunci M - N = K(m - n), de unde rezultă că K este un divizor al numărului M - N. Prin urmare, toți divizorii comuni ai numerelor M și N sunt divizori ai diferenței lor M - N, inclusiv cel mai mare. divizor comun. Prin urmare: GCD(M,N) = GCD(M - N,N). A doua proprietate evidentă: GCD(M,M) = M. N). Aceasta înseamnă că M = mK, N = pK, unde m, n sunt numere naturale și m>n. Atunci M - N \u003d K (m - n), de unde rezultă că K este un divizor al numărului M - N. Prin urmare, toți divizorii comuni ai numerelor M și N sunt divizori "\u003e N). Aceasta înseamnă că M \u003d mK, N \u003d pK , unde m, n sunt numere naturale și m > n. Atunci M - N = K(m - n), de unde rezultă că K este un divizor al numărului M - N. Prin urmare, toți divizorii comuni ai numerelor M și N sunt divizori ai diferenței lor M-N, inclusiv cel mai mare divizor comun. Prin urmare: GCD(M, N) = MCD(M - N, N). A doua proprietate evidentă: MCD(M). , M) = M."> N). Aceasta înseamnă că M = mK, N = pK, unde m, n sunt numere naturale și m>n. Atunci M - N = K(m - n), de unde rezultă că K este un divizor al lui M - N. Prin urmare, toți divizorii comuni ai lui M și N sunt divizori" title="(!LANG:Proof Fie K un comun comun divizor al lui M și N (M > N). Aceasta înseamnă că M = mK, N = pK, unde m, n sunt numere naturale și m> n. Atunci M - N = K(m - n), de unde rezultă că K este un divizor al numărului M - N. Prin urmare, toți divizorii comuni ai numerelor M și N sunt divizori"> title="Demonstrație Fie K un divizor comun al lui M și. N (M>N). Aceasta înseamnă că M = mK, N = pK, unde m, n sunt numere naturale și m>n. Atunci M - N \u003d K (m - n), ceea ce implică că K este un divizor al numărului M - N. Prin urmare, toți divizorii comuni ai numerelor M și N sunt divizori"> !}

Program în Pascal Program Evklid; var M, N: întreg; begin writeln ("Introduceți M și N"); readln(M,N); în timp ce MN începe dacă M>N, atunci M:=M-N altfel N:=N-M se termină; scrie ("HOD=",M) final. N apoi M:=M-N altfel N:=N-M capăt; scrie("HOD=",M) final."> N apoi M:=M-N altfel N:=N-M sfârşit; scrie ("HOD=",M) sfârşit."> N apoi M:=M-N altfel N:=N-M Sfârşit; write("HOD=",M) end." title="(!LANG:Programul Pascal Program Evklid; var M, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N apoi M:=M-N altfel N:=N-M capăt; write("HOD=",M) end." title="(!LANG:Programul Pascal Program Evklid; var M, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}

slide 1

slide 2

ALGORITMUL LUI EUCLID Algoritmul lui Euclid este un algoritm pentru găsirea celui mai mare divizor comun (mcd) a două numere întregi nenegative. Euclid (365-300 î.Hr.) Matematicienii greci antici au numit acest algoritm ἀνθυφαίρεσις sau ἀνταναίρεσις - „scădere reciprocă”.

slide 3

Calcul GCD GCD = cel mai mare divizor comun a două numere naturale este cel mai mare număr cu care ambele numere originale sunt divizibile fără rest. mcd(a, b)= mcd(a-b, b)= mcd(a, b-a) Înlocuiți cel mai mare dintre cele două numere cu diferența dintre cel mai mare și mai mic până când sunt egale. Acesta este NOD. mcd(18, 45) = mcd(18, 45-18) = mcd(18, 27)=mcd(18, 9) ==mcd(9,9)=9 Exemplu:

slide 4

PAS Funcționare M N Condiție 1 IntrareM 48 2 IntrareN 18 3 M N 48 18,da 4 M>N 48>18,da 5 M:=M-N 30 6 M N 30 18,da 7 M>N 30>18,da 8 M:= L-N 12 9 M N 12 18 da 10 M>N 12>18 nu 11 N:=N-M 6 12 M N 12 6 da 13 M>N 12>6 da 14 M:=M-N 6 15 M N 6 6 nu 16 ConcluzieM

slide 5

programul Evklid; var m, n: întreg; start writeln("vved 2 numere"); readln(m,n); în timp ce mn începe dacă m>n atunci m:=m-n altfel n:=n-m; Sfârşit; scrie ("nod=",m); readln sfârşitul.

slide 6

0. Rulați programul Evklid pe computer. Testați-l cu M=32, N=24; M=696, N=234. 1. Verificați dacă două numere date sunt coprime. Notă. Două numere se numesc prime relativ dacă cel mai mare divizor comun al lor este 1. 2. Aflați cel mai mic multiplu comun (MCM) al numerelor n și m dacă LCM(n, m) = n * m / mcd(n, m). 3. Datele numere naturale m și n. Găsiți numere naturale p și q fără divizori comuni astfel încât p / q = m / n. 4. Găsiți GCD-ul a trei numere. Notă. gcd(a, b, c)= gcd(gcd(a, b), c) Sarcini

Slide 7

Euclid, matematician grec antic. A lucrat la Alexandria în secolul al III-lea. î.Hr e. Lucrarea principală „Începuturi” (15 cărți), care conține bazele matematicii antice, geometria elementară, teoria numerelor, teoria generală a relațiilor și metoda de determinare a suprafețelor și volumelor, care cuprindea elemente ale teoriei limitelor. A avut o mare influență asupra dezvoltării matematicii. Lucrări de astronomie, optică, teoria muzicii.