Rezumatul și prezentarea lecției Algoritmul euclidian pentru găsirea nodurilor. Prezentare pe tema „Algoritmul lui Euclid” Subiect: Algoritmul lui Euclid pentru găsirea GCD

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)

slide 1

slide 2

slide 3

slide 4

slide 5

slide 6

Slide 7

slide 2

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

calculul 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. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) Înlocuiți cea mai mare dintre cele două numere cu diferența dintre numerele mai mari și cele mai mici până când acestea 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

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 între prime 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. Sunt date 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.

Vizualizați toate diapozitivele

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."> !}