Pamokos Euklido algoritmas mazgų paieškai santrauka ir pristatymas. Pristatymas tema "Euklido algoritmas" Tema: Euklido algoritmas ieškant GCD

Norėdami naudoti pristatymų peržiūrą, susikurkite „Google“ paskyrą (paskyrą) ir prisijunkite: https://accounts.google.com

Skaidrių antraštės:

Euklido algoritmas Euklidas, senovės graikų matematikas. III amžiuje dirbo Aleksandrijoje. pr. Kr e. Pagrindinis veikalas „Pradžia“ (15 knygų), kuriame yra senovės matematikos pagrindai, elementarioji geometrija, skaičių teorija, bendroji santykių teorija ir plotų bei tūrių nustatymo metodas, į kurį įeina ribų teorijos elementai. Jis padarė didelę įtaką matematikos raidai. Dirba su astronomija, optika, muzikos teorija. Euklidas (365–300 m. pr. Kr.)

EUKLIDO ALGORITMAS Euklido algoritmas yra dviejų neneigiamų sveikųjų skaičių didžiausio bendro daliklio (gcd) radimo algoritmas. Euklidas (365-300 m. pr. Kr.) Senovės graikų matematikai šį algoritmą pavadino ἀνθυφαίρεσις arba ἀνταναίρεσις – „abipusis atimtis“.

Skaičiavimas GCD GCD = didžiausias bendras dviejų natūraliųjų skaičių daliklis yra didžiausias skaičius, iš kurio abu pradiniai skaičiai dalijasi be liekanos. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Didesnįjį iš dviejų skaičių pakeiskite skirtumu tarp didesnio ir mažesnio, kol jie bus lygūs. Tai NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Pavyzdys:

ŽINGSNIS Veikimas M N Sąlyga 1 Įvestis M 48 2 Įvestis N 18 3 M  N 48  18, taip 4 M>N 48>18, taip 5 M:=M-N 30 6 M  N 30  18, taip 30 7 M>N >18, taip 8 M:=M-N 12 9 M  N 12 18, taip 10 M>N 12 >18, ne 11 N:=N-M 6 12 M  N 12  6, taip 13 M>N 12 >6 , taip 14 M:=M-N 6 15 M  N 6  6, ne 16 Išėjimas M

programa Evklid ; var m, n: sveikasis skaičius; begin writeln("vved 2 chisla"); readln(m,n); tuo tarpu mn prasideda, jei m>n tada m:=m-n else n:= n-m ; pabaiga; rašyti("nod=",m); skaitymo pabaiga.

0. Kompiuteryje paleiskite programą Evklid. Išbandykite su M=32, N=24; M = 696, N = 234. vienas . Patikrinkite, ar du pateikti skaičiai yra pirminiai. Pastaba. Sakoma, kad du skaičiai yra pirminiai, jei jų didžiausias bendras daliklis yra 1. 2 . Raskite skaičių n ir m mažiausiąjį bendrąjį kartotinį (LCM), jei LCM(n, m) = n * m / gcd(n, m). 3 . Pateikiami natūralieji skaičiai m ir n. Raskite natūraliuosius skaičius p ir q, kurie neturi bendrų daliklių, kad p/q = m/n. 4. Raskite trijų skaičių GCD. Pastaba. GCD(a , b , c)= GCD(gcd(a , b), c) Užduotys

Peržiūra:

Tema: "Euklido algoritmas"

Pamokos tikslai:

1. Švietimas:

1. išmokite naudoti Euklido algoritmą dviejų ir trijų skaičių gcd rasti
2. įtvirtinti įgūdžius naudojant algoritmines struktūras „Šakojimai“ ir „Cycle“
3. įgyti patirties rašant ir derinant programas Pascal programavimo kalba

1. Švietimas:

1. savarankiškumo ir atsakomybės formavimas studijuojant naują medžiagą

1. Kuriama:

1. dėmesingumo ir analitinio mąstymo ugdymas

Pamokos planas:

1. Laiko organizavimas
2. Žinių atnaujinimas
3. Naujos temos paaiškinimas
4. Praktinė dalis
5. Apibendrinant pamoką
6. Namų darbai.

Laiko organizavimas

Sveikinimai. Kurio nėra. Skaičius. Pamokos tema. Klausimai apie namų darbus.

Žinių atnaujinimas.

Klausimai:

Kokius algoritminių struktūrų tipus žinote?

Kas yra linijinė struktūra? (Bl-sh)

Kas yra išsišakojusi struktūra? (Bl-sh)

Kas yra ciklinė struktūra? (Bl-sh)

Kokius ciklų tipus žinote?

Kaip Pascal programavimo kalba realizuojamas ciklas su žinomu pakartojimų skaičiumi?

Kaip Pascal programavimo kalba realizuojamas ciklas su nežinomu pakartojimų skaičiumi?

Naujos temos paaiškinimas (pristatymas)

Apie Euklidą;

Euklido algoritmo idėja

Šio algoritmo idėja pagrįsta:

1. Savybė, kad jei M>N, tai GCD(M, N) = GCD(M - N, N).

Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo gcd (jų skirtumo moduliui) ir mažesniam skaičiui.

Įrodymas: tegul K yra bendras M ir N daliklis (M > N). Tai reiškia, kad M \u003d mK, N \u003d nK, kur m, n yra natūralūs skaičiai, o m > n. Tada M - N \u003d K (m - n), o tai reiškia, kad K yra skaičiaus M - N daliklis. Taigi visi bendrieji skaičių M ir N dalikliai yra jų skirtumo M - N dalikliai, įskaitant didžiausią bendras daliklis.

2. Antra akivaizdi savybė:

GCD(M, M) = M.

„Rankiniam“ skaičiavimui Euklido algoritmas atrodo taip:

1) jei skaičiai lygūs, kaip atsakymą paimkite bet kurį iš jų, kitu atveju tęskite algoritmą;

2) pakeisti didesnį skaičių skirtumu tarp didesnio ir mažesnio skaičių;

3) grįžti prie 1 dalies įgyvendinimo.

Euklido algoritmo blokinė schema

Programa JS Pascal

programa Evklid;

var m, n: sveikasis skaičius;

pradėti

writeln("vved 2 skaičiai");

readln(m,n);

Nors mn daro

Pradėkite

Jei m>n

Tada m:=m-n

Kitaip n:=n-m;

pabaiga;

Write("nod=",m);

readln

pabaiga.

Praktinė dalis

Klausimai ir užduotys:

1. Savo kompiuteryje paleiskite programą Evklid. Išbandykite M=32, N=24; M = 696, N = 234.
2. Patikrinkite, ar du pateikti skaičiai yra pirminiai. Pastaba. Sakoma, kad du skaičiai yra pirminiai, jei jų didžiausias bendras daliklis yra 1.

Apibendrinant pamoką

Šiandien pamokoje susipažinome su Euklido algoritmu, leidžiančiu rasti dviejų neneigiamų sveikųjų skaičių GCD, parašėme programą Pascal programavimo kalba, kuri realizuoja šį algoritmą. Namuose gausite užduotį, kurioje taikydami šį algoritmą rasite trijų skaičių GCD ir dviejų skaičių LCM.

Namų darbai.

1. Parašykite programą, kuri pagal šią formulę rastų didžiausią bendrą trijų skaičių daliklį:

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

2. Parašykite programą dviejų skaičių mažiausiajam bendrajam kartotiniui (LCM) rasti naudodami formulę:

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

skaidrė 1

skaidrė 2

skaidrė 3

skaidrė 4

skaidrė 5

skaidrė 6

7 skaidrė

skaidrė 2

Euklido algoritmas yra dviejų neneigiamų sveikųjų skaičių didžiausio bendro daliklio (gcd) radimo algoritmas. Euklidas (365-300 m. pr. Kr.) Senovės graikų matematikai šį algoritmą pavadino ἀνθυφαίρεσις arba ἀνταναίρεσις – „abipusis atimtis“.

skaidrė 3

GCD skaičiavimas

GCD = didžiausias bendras dviejų natūraliųjų skaičių daliklis yra didžiausias skaičius, iš kurio abu pradiniai skaičiai dalijasi be liekanos. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) Didesnįjį iš dviejų skaičių pakeiskite skirtumu tarp didesnių ir mažesnių skaičių, kol jie bus lygūs. Tai NOD. GCD (18, 45) = GCD (18, 45-18) = GCD (18, 27) = GCD (18, 9) = = GCD (9, 9) = 9 Pavyzdys:

skaidrė 4

skaidrė 5

programa Evklid; var m, n: sveikasis skaičius; begin writeln("vved 2 skaičiai"); readln(m,n); tuo tarpu mn prasideda, jei m>n tada m:=m-n else n:=n-m; pabaiga; rašyti("nod=",m); skaitymo pabaiga.

skaidrė 6

0. Kompiuteryje paleiskite programą Evklid. Išbandykite su M=32, N=24; M = 696, N = 234. 1. Patikrinkite, ar du pateikti skaičiai yra pirminiai. Pastaba. Du skaičiai vadinami pirminiais, jei jų didžiausias bendras daliklis yra 1. 2. Raskite skaičių n ir m mažiausią bendrą kartotinį (LCM), jei LCM(n, m) = n * m / gcd(n, m). 3. Duoti natūralieji skaičiai m ir n. Raskite natūraliuosius skaičius p ir q be bendrųjų daliklių, kad p / q = m / n. 4. Raskite trijų skaičių GCD. Pastaba. gcd(a, b, c)= gcd(gcd(a, b), c) Užduotys

7 skaidrė

Euklidas, senovės graikų matematikas. III amžiuje dirbo Aleksandrijoje. pr. Kr e. Pagrindinis veikalas „Pradžia“ (15 knygų), kuriame yra senovės matematikos pagrindai, elementarioji geometrija, skaičių teorija, bendroji santykių teorija ir plotų bei tūrių nustatymo metodas, į kurį įeina ribų teorijos elementai. Jis padarė didelę įtaką matematikos raidai. Dirba su astronomija, optika, muzikos teorija.

Peržiūrėkite visas skaidres

Uždavinio teiginys Apsvarstykite šią problemą: reikia parašyti programą dviejų natūraliųjų skaičių didžiausiam bendrajam dalikliui (GCD) nustatyti. Prisiminkime matematiką. Didžiausias bendras dviejų natūraliųjų skaičių daliklis yra didžiausias natūralusis skaičius, iš kurio jie dalijasi tolygiai. Pavyzdžiui, skaičiai 12 ir 18 turi bendrus daliklius: 2, 3, 6. Didžiausias bendras daliklis yra skaičius 6. Tai rašoma taip: gcd(12,18) = 6. Pradinius duomenis pažymėkite kaip M ir N Problemos teiginys yra toks: Duota: M, N Rasti: GCD(M, N).

N, tada GCD(M,N) = GCD(M – N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd." title="(!LANG:Algoritmo idėja Šio algoritmo idėja pagrįsta savybė, kad jei M>N, tai gcd(M,N) = gcd( M - N, N) Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesniojo skaičiaus gcd." class="link_thumb"> 4 !} Algoritmo idėja Šio algoritmo idėja pagrįsta savybe, kad jei M>N, tai GCD(M,N) = GCD(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd. N, tada GCD(M,N) = GCD(M – N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd."> N, tada gcd(M,N) = gcd(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd."> N, tada GCD(M,N) = GCD(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd." title="(!LANG:Algoritmo idėja Šio algoritmo idėja pagrįsta savybė, kad jei M>N, tai gcd(M,N) = gcd( M - N, N) Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesniojo skaičiaus gcd."> title="Algoritmo idėja Šio algoritmo idėja pagrįsta savybe, kad jei M>N, tai GCD(M,N) = GCD(M - N,N). Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo ir mažesnio skaičiaus gcd."> !}

N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N = K(m - n), iš ko išplaukia, kad K yra M - N daliklis. Vadinasi, visi bendrieji M ir N dalikliai yra dalikliai" title="(!LANG:Proof Tegu K yra bendras M ir. N daliklis (M > N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m> n. Tada M - N = K(m - n), iš kur jis iš to seka, kad K yra skaičiaus M – N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai" class="link_thumb"> 5 !}Įrodymas Tegul K yra bendras M ir daliklis. N (M>N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N = K(m - n), iš ko išplaukia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra jų skirtumo M - N dalikliai, įskaitant didžiausią bendras daliklis. Vadinasi: GCD(M,N) = GCD(M – N,N). Antroji akivaizdi savybė: GCD(M,M) = M. N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N \u003d K (m - n), iš to išplaukia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai "\u003e N). Tai reiškia, kad M \u003d mK, N \u003d pK , kur m, n yra natūralūs skaičiai, o m > n. Tada M - N = K(m - n), tai reiškia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra jų skirtumo M-N dalikliai, įskaitant didžiausią bendrąjį daliklį. Vadinasi: GCD(M, N) = GCD(M - N, N). Antroji akivaizdi savybė: GCD(M) , M) = M."> N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N = K(m - n), iš ko išplaukia, kad K yra M - N daliklis. Vadinasi, visi bendrieji M ir N dalikliai yra dalikliai" title="(!LANG:Proof Tegu K yra bendras M ir. N daliklis (M > N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m> n. Tada M - N = K(m - n), iš kur jis iš to seka, kad K yra skaičiaus M – N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai"> title="Įrodymas Tegul K yra bendras M ir daliklis. N (M>N). Tai reiškia, kad M = mK, N = pK, kur m, n yra natūralieji skaičiai, o m>n. Tada M - N \u003d K (m - n), o tai reiškia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra dalikliai"> !}

Programa Pascal programoje Evklid; var M, N: sveikasis skaičius; begin writeln ("Įveskite M ir N"); readln(M,N); tuo tarpu MN prasideda, jei M>N, tada M:=M-N kitaip N:=N-M pabaiga; rašyti("HOD=",M) pabaiga. N, tada M:=M-N, kitaip N:=N-M galas; rašyti("HOD=",M) pabaiga."> N, tada M:=M-N kitaip N:=N-M pabaiga; rašyti("HOD=",M) pabaiga."> N, tada M:=M-N kitaip N:=N-M pabaiga; write("HOD=",M) end." title="(!LANG:Pascal programa 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, tada M:=M-N, kitaip N:=N-M galas; write("HOD=",M) end." title="(!LANG:Pascal programa 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."> !}