Buod at presentasyon ng aralin Euclidean algorithm para sa paghahanap ng mga node. Pagtatanghal sa paksang "Euclid's algorithm" Paksa: Euclid's algorithm para sa paghahanap ng GCD

Upang gamitin ang preview ng mga presentasyon, lumikha ng isang Google account (account) at mag-sign in: https://accounts.google.com

Mga slide caption:

Euclid's Algorithm Euclid, sinaunang Greek mathematician. Nagtrabaho sa Alexandria noong ika-3 siglo. BC e. Ang pangunahing gawain na "Mga Simula" (15 mga libro), na naglalaman ng mga pundasyon ng sinaunang matematika, elementarya na geometry, teorya ng numero, pangkalahatang teorya ng mga relasyon at ang pamamaraan para sa pagtukoy ng mga lugar at volume, na kasama ang mga elemento ng teorya ng mga limitasyon. Malaki ang impluwensya niya sa pag-unlad ng matematika. Gumagana sa astronomiya, optika, teorya ng musika. Euclid (365-300 BC)

ALGORITHM NG EUCLID Ang algorithm ng Euclid ay isang algorithm para sa paghahanap ng pinakamalaking karaniwang divisor (GCD) ng dalawang hindi negatibong integer. Euclid (365-300 BC) Tinawag ng mga sinaunang Greek mathematician ang algorithm na ito na ἀνθυφαίρεσις o ἀνταναίρεσις - "mutual subtraction".

Pagkalkula GCD GCD = ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking bilang kung saan ang parehong orihinal na mga numero ay nahahati nang walang natitira. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Palitan ang mas malaki sa dalawang numero ng pagkakaiba sa pagitan ng mas malaki at mas maliit hanggang sa magkapantay ang mga ito. Ito ay NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Halimbawa:

STEP Operation M N Kondisyon 1 Input M 48 2 Input N 18 3 M  N 48 18, oo 4 M>N 48>18, oo 5 M:=M-N 30 6 M  N 30  18, oo 7 M>N 30 >18, oo 8 M:=M-N 12 9 M  N 12 18, oo 10 M>N 12 >18, hindi 11 N:=N-M 6 12 M  N 12  6, oo 13 M>N 12 >6 , oo 14 M:=M-N 6 15 M  N 6  6, hindi 16 Output M

programa Evklid ; var m, n: integer; simulan writeln("vved 2 chisla"); readln(m,n); habang mn magsisimula kung m>n pagkatapos m:=m-n iba n:= n-m ; wakas; write("nod=",m); matapos basahin.

0. Patakbuhin ang Evklid program sa computer. Subukan ito ng M=32, N=24; M=696, N=234. isa. Suriin kung ang dalawang ibinigay na numero ay coprime. Tandaan. Ang dalawang numero ay sinasabing coprime kung ang kanilang pinakamalaking karaniwang divisor ay 1. 2 . Hanapin ang least common multiple (LCM) ng mga numero n at m kung LCM(n, m) = n * m / gcd(n, m). 3 . Ang mga natural na bilang na m at n ay ibinibigay. Maghanap ng mga natural na numerong p at q na walang karaniwang divisors na p / q = m / n . 4. Hanapin ang GCD ng tatlong numero. Tandaan. GCD(a , b , c)= GCD(gcd(a , b), c) Mga Gawain

Preview:

Paksa: "Euclid's Algorithm"

Layunin ng Aralin:

1. Pang-edukasyon:

1. alamin kung paano gamitin ang Euclid algorithm upang mahanap ang gcd ng dalawa at tatlong numero
2. pagsama-samahin ang mga kasanayan sa paggamit ng mga istrukturang algorithm na "Branching" at "Cycle"
3. magkaroon ng karanasan sa pagsulat at pag-debug ng mga programa sa wikang programming ng Pascal

1. Pang-edukasyon:

1. pagbuo ng kalayaan at pananagutan sa pag-aaral ng bagong materyal

1. Pagbuo:

1. pag-unlad ng atensyon at analytical na pag-iisip

Plano ng aralin:

1. Oras ng pag-aayos
2. Pag-update ng kaalaman
3. Pagpapaliwanag ng bagong paksa
4. Praktikal na bahagi
5. Pagbubuod ng aralin
6. Takdang aralin.

Oras ng pag-aayos

Pagbati. Sino ang absent. Numero. Paksa ng aralin. Mga tanong sa takdang-aralin.

Pag-update ng kaalaman.

Mga Tanong:

Anong mga uri ng algorithmic na istruktura ang alam mo?

Ano ang isang linear na istraktura? (Bl-sh)

Ano ang istrakturang sumasanga? (Bl-sh)

Ano ang cyclic structure? (Bl-sh)

Anong mga uri ng cycle ang alam mo?

Paano ipinapatupad ang isang loop na may kilalang bilang ng mga pag-uulit sa wikang programming ng Pascal?

Paano ipinapatupad ang isang loop na may hindi kilalang bilang ng mga pag-uulit sa wikang programming ng Pascal?

Pagpapaliwanag ng bagong paksa (pagtatanghal)

Tungkol kay Euclid;

Ideya ng algorithm ni Euclid

Ang ideya ng algorithm na ito ay batay sa:

1. Ang property na kung M>N, pagkatapos ay GCD(M, N) = GCD(M - N, N).

Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba (ang modulus ng kanilang pagkakaiba) at ang mas maliit na numero.

Patunay: hayaang ang K ay isang karaniwang divisor ng M at N (M > N). Nangangahulugan ito na ang M \u003d mK, N \u003d nK, kung saan ang m, n ay mga natural na numero, at m > n. Pagkatapos M - N \u003d K (m - n), na nagpapahiwatig na ang K ay isang divisor ng numero M - N. Samakatuwid, ang lahat ng mga karaniwang divisors ng mga numero M at N ay mga divisors ng kanilang pagkakaiba M - N, kabilang ang pinakamalaking karaniwang divisor.

2. Pangalawang halatang ari-arian:

GCD(M, M) = M.

Para sa "manual" na pagbibilang, ganito ang hitsura ng algorithm ni Euclid:

1) kung ang mga numero ay pantay, pagkatapos ay kunin ang alinman sa mga ito bilang isang sagot, kung hindi man ay ipagpatuloy ang algorithm;

2) palitan ang mas malaking numero ng pagkakaiba sa pagitan ng mas malaki at mas maliit ng mga numero;

3) bumalik sa pagpapatupad ng talata 1.

Block diagram ng Euclid algorithm

Programa sa JS Pascal

programa Evklid;

var m, n: integer;

magsimula

writeln("vved 2 numero");

readln(m,n);

Habang ginagawa ko

Magsimula

Kung m>n

Pagkatapos m:=m-n

Iba n:=n-m;

wakas;

Write("nod=",m);

readln

wakas.

Praktikal na bahagi

Mga tanong at gawain:

1. Patakbuhin ang Evklid program sa iyong computer. Subukan ito sa M=32, N=24; M = 696, N = 234.
2. Suriin kung ang dalawang ibinigay na numero ay coprime. Tandaan. Dalawang numero ang sinasabing coprime kung ang kanilang pinakamalaking karaniwang divisor ay 1.

Pagbubuod ng aralin

Ngayon sa aralin nakilala namin ang Euclid algorithm, na nagbibigay-daan sa amin upang mahanap ang GCD ng dalawang hindi negatibong integer, nagsulat kami ng isang programa sa Pascal programming language na nagpapatupad ng algorithm na ito. Sa bahay, makakatanggap ka ng isang gawain kung saan ilalapat mo ang algorithm na ito upang mahanap ang GCD ng tatlong numero at ang LCM ng dalawang numero.

Takdang aralin.

1. Sumulat ng isang programa upang mahanap ang pinakamalaking karaniwang divisor ng tatlong numero gamit ang sumusunod na formula:

gcd(A, B, C) = gcd(gcd(A, B), C)

2. Sumulat ng programa para sa paghahanap ng least common multiple (LCM) ng dalawang numero gamit ang 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

Ang algorithm ng Euclid ay isang algorithm para sa paghahanap ng pinakamalaking karaniwang divisor (gcd) ng dalawang hindi negatibong integer. Euclid (365-300 BC) Tinawag ng mga sinaunang Greek mathematician ang algorithm na ito na ἀνθυφαίρεσις o ἀνταναίρεσις - "mutual subtraction".

slide 3

Pagkalkula ng GCD

GCD = ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking bilang kung saan ang parehong orihinal na mga numero ay nahahati nang walang natitira. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) Palitan ang mas malaki sa dalawang numero ng pagkakaiba sa pagitan ng mas malaki at maliliit na numero hanggang sa magkapantay ang mga ito. Ito ay NOD. GCD (18, 45)= GCD (18, 45-18)= GCD (18, 27)= GCD (18, 9)= = GCD(9,9)=9 Halimbawa:

slide 4

slide 5

programa Evklid; var m, n: integer; simulan writeln("vved 2 numero"); readln(m,n); habang mn magsisimula kung m>n pagkatapos m:=m-n iba n:=n-m; wakas; write("nod=",m); matapos basahin.

slide 6

0. Patakbuhin ang Evklid program sa computer. Subukan ito ng M=32, N=24; M=696, N=234. 1. Suriin kung ang dalawang ibinigay na numero ay coprime. Tandaan. Ang dalawang numero ay tinatawag na coprime kung ang kanilang pinakamalaking karaniwang divisor ay 1. 2.Hanapin ang least common multiple (LCM) ng mga numero n at m kung LCM(n, m) = n * m / gcd(n, m). 3. Ang mga natural na bilang na m at n ay ibinibigay. Maghanap ng mga natural na numerong p at q na walang karaniwang divisors na p / q = m / n. 4. Hanapin ang GCD ng tatlong numero. Tandaan. gcd(a, b, c)= gcd(gcd(a, b), c) Mga Gawain

Slide 7

Euclid, sinaunang Greek mathematician. Nagtrabaho sa Alexandria noong ika-3 siglo. BC e. Ang pangunahing gawain na "Mga Simula" (15 mga libro), na naglalaman ng mga pundasyon ng sinaunang matematika, elementarya na geometry, teorya ng numero, pangkalahatang teorya ng mga relasyon at ang pamamaraan para sa pagtukoy ng mga lugar at volume, na kasama ang mga elemento ng teorya ng mga limitasyon. Malaki ang impluwensya niya sa pag-unlad ng matematika. Gumagana sa astronomiya, optika, teorya ng musika.

Tingnan ang lahat ng mga slide

Paglalahad ng Problema Isaalang-alang ang sumusunod na problema: kinakailangan na magsulat ng isang programa para sa pagtukoy ng pinakamalaking karaniwang divisor (GCD) ng dalawang natural na numero. Alalahanin natin ang matematika. Ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking natural na bilang kung saan sila ay pantay na nahahati. Halimbawa, ang mga numero 12 at 18 ay may mga karaniwang divisors: 2, 3, 6. Ang pinakamalaking karaniwang divisor ay ang numero 6. Ito ay nakasulat tulad ng sumusunod: gcd(12,18) = 6. Tukuyin ang inisyal na data bilang M at N Ang pahayag ng problema ay ang mga sumusunod : Ibinigay: M, N Hanapin: GCD(M, N).

N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang." title="(!LANG:Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa property na kung M>N, pagkatapos ay gcd(M,N) = gcd(M - N, N) Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero." class="link_thumb"> 4 !} Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa pag-aari na kung M>N, pagkatapos GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero. N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang."> N, pagkatapos ay gcd(M,N) = gcd(M - N,N). Sa madaling salita, ang Ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at mas maliit na numero."> N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang." title="(!LANG:Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa property na kung M>N, pagkatapos ay gcd(M,N) = gcd(M - N, N) Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero."> title="Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa pag-aari na kung M>N, pagkatapos GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero."> !}

N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), kung saan sumusunod na ang K ay isang divisor ng M - N. Kaya, lahat ng karaniwang divisors ng M at N ay mga divisors" title="(!LANG:Proof Let K be a common divisor ng M at. N (M > N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m> n. Pagkatapos M - N = K(m - n), kung saan ito sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors" class="link_thumb"> 5 !} Patunay Hayaan ang K na maging karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), kung saan sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors ng kanilang pagkakaiba M - N, kabilang ang pinakamalaking karaniwang divisor. Kaya naman: GCD(M,N) = GCD(M - N,N). Ang pangalawang halatang property: GCD(M,M) = M. N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N \u003d K (m - n), kung saan sumusunod na ang K ay isang divisor ng numero M - N. Samakatuwid, ang lahat ng mga karaniwang divisors ng mga numerong M at N ay mga divisors "\u003e N). Nangangahulugan ito na M \u003d mK, N \u003d pK , kung saan ang m, n ay mga natural na numero, at m > n. Pagkatapos M - N = K(m - n), kung saan sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors ng kanilang pagkakaiba M-N, kabilang ang pinakamalaking common divisor. Kaya: GCD(M, N) = GCD(M - N, N). Ang pangalawang halatang property: GCD(M) , M) = M."> N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), kung saan sumusunod na ang K ay isang divisor ng M - N. Kaya, lahat ng karaniwang divisors ng M at N ay mga divisors" title="(!LANG:Proof Let K be a common divisor ng M at. N (M > N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m> n. Pagkatapos M - N = K(m - n), kung saan ito sumusunod na ang K ay isang divisor ng numerong M - N. Samakatuwid, ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors"> title="Patunay Hayaan ang K na maging karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N \u003d K (m - n), na nagpapahiwatig na ang K ay isang divisor ng numero M - N. Samakatuwid, ang lahat ng mga karaniwang divisors ng mga numerong M at N ay mga divisors"> !}

Programa sa Pascal Program Evklid; var M, N: integer; simulan writeln("Ipasok ang M at N"); readln(M,N); habang ang MN ay nagsisimula kung M>N pagkatapos M:=M-N iba pa N:=N-M dulo; write("HOD=",M) dulo. N pagkatapos M:=M-N iba N:=N-M dulo; write("HOD=",M) end."> N tapos M:=M-N iba N:=N-M end; write("HOD=",M) end."> N tapos M:=M-N iba N:=N-M wakas; write("HOD=",M) end." title="(!LANG:Pascal program 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 pagkatapos M:=M-N iba N:=N-M dulo; write("HOD=",M) end." title="(!LANG:Pascal program 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."> !}