Darsning qisqacha mazmuni va taqdimoti Tugunlarni topish uchun Evklid algoritmi. “Evklid algoritmi” mavzusidagi taqdimot Mavzu: GCD ni topish uchun Evklid algoritmi

Taqdimotlarni oldindan ko‘rishdan foydalanish uchun Google hisobini (hisobini) yarating va tizimga kiring: https://accounts.google.com

Slayd sarlavhalari:

Evklid algoritmi Evklid, qadimgi yunon matematigi. 3-asrda Iskandariyada ishlagan. Miloddan avvalgi e. Qadimgi matematikaning asoslarini, elementar geometriyani, sonlar nazariyasini, munosabatlarning umumiy nazariyasini va chegaralar nazariyasi elementlarini o'z ichiga olgan sohalar va hajmlarni aniqlash usulini o'z ichiga olgan asosiy asar "Boshlanishlar" (15 kitob). U matematikaning rivojlanishiga katta ta'sir ko'rsatdi. Astronomiya, optika, musiqa nazariyasi bo'yicha ishlaydi. Evklid (miloddan avvalgi 365-300 yillar)

YEVCLID ALGORITMMI Evklid algoritmi ikki manfiy bo'lmagan butun sonning eng katta umumiy bo'luvchisini (gcd) topish algoritmidir. Evklid (miloddan avvalgi 365-300 yillar) Qadimgi yunon matematiklari bu algoritmni ἀnthυυρaρestus yoki ἀnἀpanapiress - "o'zaro ayirish" deb atashgan.

Hisoblash GCD GCD = ikkita natural sonning eng katta umumiy boʻluvchisi ikkala asl son ham qoldiqsiz boʻlinadigan eng katta sondir. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Ikki sonning kattasini kattasi va kichiki orasidagi farq bilan teng bo‘lguncha almashtiring. Bu NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Misol:

QADAM Operatsion M N Holat 1 Kirish M 48 2 Kirish N 18 3 M  N 48 18, ha 4 M>N 48>18, ha 5 M:=M-N 30 6 M  N 30  18, ha 7 M>N 30 >18, ha 8 M:=M-N 12 9 M  N 12 18, ha 10 M>N 12 >18, yo‘q 11 N:=N-M 6 12 M  N 12  6, ha 13 M>N 12 >6 , ha 14 M:=M-N 6 15 M  N 6  6, yo‘q 16 Chiqish M

Evklid dasturi; var m, n: butun son; begin writeln("vved 2 chisla"); readln(m,n); while mn do begin if m>n keyin m:=m-n else n:= n-m ; oxiri; write("nod=",m); readln end.

0.Evklid dasturini kompyuterda ishga tushiring. Uni M=32, N=24 bilan tekshiring; M=696, N=234. bitta. Berilgan ikkita son koʻpaytma ekanligini tekshiring. Eslatma. Ikki sonning eng katta umumiy boʻluvchisi 1 boʻlsa, koʻp sonlar deyiladi. LCM(n, m) = n * m / gcd(n, m) bo'lsa, n va m sonlarining eng kichik umumiy karrali (LCM) toping. 3 . m va n natural sonlar berilgan. p / q = m / n bo'ladigan umumiy bo'luvchilarga ega bo'lmagan p va q natural sonlarini toping. 4. Uch sonning GCD ni toping. Eslatma. GCD(a , b , c)= GCD(gcd(a , b), c) Vazifalar

Ko‘rib chiqish:

Mavzu: "Evklid algoritmi"

Dars maqsadlari:

1. Tarbiyaviy:

1. Ikki va uchta sonning gcd ni topish uchun Evklid algoritmidan foydalanishni o'rganing
2. "Tarmoqlanish" va "Tsikl" algoritmik tuzilmalaridan foydalanish ko'nikmalarini mustahkamlash.
3. Paskal dasturlash tilida dasturlarni yozish va disk raskadrovka qilish tajribasiga ega bo'lish

1. Tarbiyaviy:

1. yangi materialni o'rganishda mustaqillik va mas'uliyatni shakllantirish

1. Rivojlanayotgan:

1. e'tibor va analitik fikrlashni rivojlantirish

Dars rejasi:

1. Tashkiliy vaqt
2. Bilimlarni yangilash
3. Yangi mavzuni tushuntirish
4. Amaliy qism
5. Darsni yakunlash
6. Uy vazifasi.

Tashkiliy vaqt

Salom. Kim yo'q. Raqam. Dars mavzusi. Uy vazifasi bo'yicha savollar.

Bilimlarni yangilash.

Savollar:

Algoritmik tuzilmalarning qanday turlarini bilasiz?

Chiziqli struktura nima? (Bl-sh)

Tarmoqli tuzilish nima? (Bl-sh)

Siklik struktura nima? (Bl-sh)

Qanday sikl turlarini bilasiz?

Paskal dasturlash tilida takroriy soni ma'lum bo'lgan sikl qanday amalga oshiriladi?

Paskal dasturlash tilida takrorlar soni noma'lum bo'lgan sikl qanday amalga oshiriladi?

Yangi mavzuni tushuntirish (taqdimot)

Evklid haqida;

Evklid algoritmining g'oyasi

Ushbu algoritm g'oyasi quyidagilarga asoslanadi:

1. Agar M>N bo'lsa, GCD(M, N) = GCD(M - N, N) xossasi.

Boshqacha qilib aytganda, ikkita natural sonning gcd si ularning musbat ayirmasi (ularning farqining moduli) va undan kichikroq sonning gcd ga teng.

Isbot: K M va N ning umumiy bo‘luvchisi bo‘lsin (M > N). Bu shuni anglatadiki, M \u003d mK, N \u003d nK, bu erda m, n - natural sonlar va m > n. Keyin M - N \u003d K (m - n), bu K M sonining bo'luvchisi ekanligini anglatadi - N. Demak, M va N sonlarining barcha umumiy bo'luvchilari M - N farqining bo'luvchilari, shu jumladan eng kattasi umumiy bo'luvchi.

2. Ikkinchi aniq xususiyat:

GCD(M, M) = M.

"Qo'lda" hisoblash uchun Evklidning algoritmi quyidagicha ko'rinadi:

1) agar raqamlar teng bo'lsa, ulardan birortasini javob sifatida qabul qiling, aks holda algoritmni davom ettiring;

2) kattaroq sonni katta va kichik sonlar orasidagi farq bilan almashtiring;

3) 1-bandni amalga oshirishga qaytish.

Evklid algoritmining blok diagrammasi

JS Pascal tilidagi dastur

Evklid dasturi;

var m, n: butun son;

boshlash

writeln("vved 2 raqam");

readln(m,n);

mn qilsa

Boshlash

Agar m>n

Keyin m:=m-n

Aks holda n:=n-m;

oxiri;

Write("nod=",m);

readln

oxiri.

Amaliy qism

Savol va vazifalar:

1. Kompyuteringizda Evklid dasturini ishga tushiring. Uni M=32, N=24 da sinab ko‘ring; M = 696, N = 234.
2. Berilgan ikkita son koʻpaytma ekanligini tekshiring. Eslatma. Ikki sonning eng katta umumiy boʻluvchisi 1 boʻlsa, koʻp sonlar deyiladi.

Darsni yakunlash

Bugun darsda ikkita manfiy bo'lmagan butun sonning GCD ni topish imkonini beruvchi Evklid algoritmi bilan tanishdik, biz Paskal dasturlash tilida ushbu algoritmni amalga oshiradigan dastur yozdik. Uyda siz uchta raqamning GCD va ikkita raqamning LCM ni topish uchun ushbu algoritmni qo'llaydigan vazifani olasiz.

Uy vazifasi.

1. Quyidagi formula yordamida uchta sonning eng katta umumiy boʻluvchisini topish dasturini tuzing:

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

2. Ikki sonning eng kichik umumiy karralini (LCM) formuladan foydalanib topish dasturini tuzing:

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

slayd 1

slayd 2

slayd 3

slayd 4

slayd 5

slayd 6

Slayd 7

slayd 2

Evklid algoritmi ikkita manfiy bo'lmagan butun sonning eng katta umumiy bo'luvchisini (gcd) topish algoritmidir. Evklid (miloddan avvalgi 365-300 yillar) Qadimgi yunon matematiklari bu algoritmni ἀnthυυρaρestus yoki ἀnἀpanapiress - "o'zaro ayirish" deb atashgan.

slayd 3

GCD hisoblash

GCD = ikkita natural sonning eng katta umumiy boʻluvchisi ikkala asl son ham qoldiqsiz boʻlinadigan eng katta sondir. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) Ikki sonning kattasini katta va kichik sonlar orasidagi farq bilan ular teng boʻlguncha almashtiring. Bu NOD. gcd(18, 45)=gcd(18,45-18)=gcd(18,27)=gcd(18,9)==gcd(9,9)=9 Misol:

slayd 4

slayd 5

Evklid dasturi; var m, n: butun son; begin writeln("vved 2 raqam"); readln(m,n); while mn do begin if m>n keyin m:=m-n else n:=n-m; oxiri; write("nod=",m); readln end.

slayd 6

0.Evklid dasturini kompyuterda ishga tushiring. Uni M=32, N=24 bilan tekshiring; M=696, N=234. 1. Berilgan ikkita son koʻpaytma ekanligini tekshiring. Eslatma. Ikki sonning eng katta umumiy boʻluvchisi 1 boʻlsa, koʻp sonli sonlar deyiladi. 2. LCM(n, m) = n * m / gcd(n, m) boʻlsa, n va m sonlarining eng kichik umumiy karrali (LCM)ni toping. 3. m va n natural sonlar berilgan. p / q = m / n bo'ladigan umumiy bo'luvchilarsiz p va q natural sonlarini toping. 4. Uch sonning GCD ni toping. Eslatma. gcd(a, b, c)= gcd(gcd(a, b), c) Vazifalar

Slayd 7

Evklid, qadimgi yunon matematigi. 3-asrda Iskandariyada ishlagan. Miloddan avvalgi e. Qadimgi matematikaning asoslarini, elementar geometriyani, sonlar nazariyasini, munosabatlarning umumiy nazariyasini va chegaralar nazariyasi elementlarini o'z ichiga olgan sohalar va hajmlarni aniqlash usulini o'z ichiga olgan asosiy asar "Boshlanishlar" (15 kitob). U matematikaning rivojlanishiga katta ta'sir ko'rsatdi. Astronomiya, optika, musiqa nazariyasi bo'yicha ishlaydi.

Barcha slaydlarni ko'rish

Muammoning bayoni Quyidagi masalani ko'rib chiqing: ikkita natural sonning eng katta umumiy bo'luvchisini (GCD) aniqlash dasturini yozish talab qilinadi. Keling, matematikani eslaylik. Ikki natural sonning eng katta umumiy boʻluvchisi ular teng boʻlinadigan eng katta natural sondir. Masalan, 12 va 18 sonlarning umumiy bo‘luvchilari bor: 2, 3, 6. Eng katta umumiy bo‘luvchi 6 soni. Bu quyidagicha yoziladi: gcd(12,18) = 6. Dastlabki ma’lumotlarni M va N deb belgilang. Muammoning bayoni quyidagicha: Berilgan: M, N Toping: GCD(M, N).

N, keyin GCD (M, N) = GCD (M - N, N). Boshqacha qilib aytadigan bo'lsak, ikkita natural sonning gcd si ularning musbat farqi va kichikroq sonning gcd ga teng." title="(!LANG:Algoritm g'oyasi Ushbu algoritm g'oyasi xossasi, agar M>N bo'lsa, gcd(M,N) = gcd( M - N, N) Boshqacha qilib aytganda, ikkita natural sonning gcd i ularning musbat ayirmasi gcd va undan kichikroq songa teng." class="link_thumb"> 4 !} Algoritm g'oyasi Ushbu algoritm g'oyasi agar M>N bo'lsa, GCD(M,N) = GCD(M - N,N) xususiyatiga asoslanadi. Boshqacha qilib aytganda, ikkita natural sonning gcd si ularning musbat farqi va undan kichikroq sonning gcd ga teng. N, keyin GCD (M, N) = GCD (M - N, N). Boshqacha qilib aytganda, ikkita natural sonning gcd si ularning musbat farqining gcd va undan kichikroq songa teng."> N, keyin gcd(M,N) = gcd(M - N,N). Boshqacha qilib aytganda, Ikki natural sonning gcd si ularning musbat farqining gcd va kichikroq soniga teng."> N, keyin GCD(M,N) = GCD(M - N,N). Boshqacha qilib aytadigan bo'lsak, ikkita natural sonning gcd si ularning musbat farqi va kichikroq sonning gcd ga teng." title="(!LANG:Algoritm g'oyasi Ushbu algoritm g'oyasi xossasi, agar M>N bo'lsa, gcd(M,N) = gcd( M - N, N) Boshqacha qilib aytganda, ikkita natural sonning gcd i ularning musbat ayirmasi gcd va undan kichikroq songa teng."> title="Algoritm g'oyasi Ushbu algoritm g'oyasi agar M>N bo'lsa, GCD(M,N) = GCD(M - N,N) xususiyatiga asoslanadi. Boshqacha qilib aytganda, ikkita natural sonning gcd si ularning musbat farqi va undan kichikroq sonning gcd ga teng."> !}

N). Bu shuni anglatadiki, M = mK, N = pK, bu erda m, n natural sonlar va m>n. U holda M - N = K(m - n), bundan kelib chiqadiki, K M - N ning bo'luvchisidir. Demak, M va N ning barcha umumiy bo'luvchilari bo'luvchilardir" title="(!LANG:Isbot K umumiy bo'lsin. M va N ning bo'luvchisi (M > N).Bu shuni anglatadiki, M = mK, N = pK, bu erda m, n natural sonlar va m> n. U holda M - N = K(m - n), qayerdan kelib chiqadiki, K M sonining bo'luvchisi - N. Demak, M va N sonlarning barcha umumiy bo'luvchilari bo'luvchilardir." class="link_thumb"> 5 !} Isbot K, M va ning umumiy bo'luvchisi bo'lsin. N (M>N). Bu shuni anglatadiki, M = mK, N = pK, bu erda m, n natural sonlar va m>n. U holda M - N = K(m - n), bundan kelib chiqadiki, K M sonining bo'luvchisi - N. Demak, M va N sonlarning barcha umumiy bo'luvchilari ularning M - N ayirmasining bo'luvchilari, shu jumladan eng kattasi ham. umumiy bo'luvchi. Demak: GCD(M,N) = GCD(M - N,N). Ikkinchi aniq xususiyat: GCD (M, M) = M. N). Bu shuni anglatadiki, M = mK, N = pK, bu erda m, n natural sonlar va m>n. Keyin M - N \u003d K (m - n), shundan kelib chiqadiki, K - M sonining bo'luvchisi - N. Demak, M va N sonlarining barcha umumiy bo'luvchilari "\u003e N" bo'luvchidir. Bu shuni anglatadiki, M \u003d mK, N \u003d pK , bu erda m, n - natural sonlar va m > n. Keyin M - N = K(m - n), bundan kelib chiqadiki, K M - N sonining bo'luvchisidir. Demak, M va N sonlarning barcha umumiy boʻluvchilari ularning M-N ayirmasining boʻluvchilari, shu jumladan eng katta umumiy boʻluvchi.Demak: GCD(M, N) = GCD(M - N, N).Ikkinchi aniq xususiyat: GCD(M) , M) = M."> N). Bu shuni anglatadiki, M = mK, N = pK, bu erda m, n natural sonlar va m>n. U holda M - N = K(m - n), bundan kelib chiqadiki, K M - N ning bo'luvchisidir. Demak, M va N ning barcha umumiy bo'luvchilari bo'luvchilardir" title="(!LANG:Isbot K umumiy bo'lsin. M va N ning bo'luvchisi (M > N).Bu shuni anglatadiki, M = mK, N = pK, bu erda m, n natural sonlar va m> n. U holda M - N = K(m - n), qayerdan kelib chiqadiki, K M sonining bo'luvchisi - N. Demak, M va N sonlarning barcha umumiy bo'luvchilari bo'luvchilardir."> title="Isbot K, M va ning umumiy bo'luvchisi bo'lsin. N (M>N). Bu shuni anglatadiki, M = mK, N = pK, bu erda m, n natural sonlar va m>n. Keyin M - N \u003d K (m - n), bu K ning M - N sonining bo'luvchisi ekanligini anglatadi. Demak, M va N sonlarining barcha umumiy bo'luvchilari bo'luvchilardir."> !}

Paskal dasturida Evklid dasturi; var M, N: integer; begin writeln("M va N ni kiriting"); readln(M,N); esa MN boshlanadi, agar M>N keyin M:=M-N boshqa N:=N-M tugaydi; yozing ("HOD=",M) end. N keyin M:=M-N boshqa N:=N-M oxiri; write("HOD=",M) end."> N keyin M:=M-N boshqa N:=N-M end; write("HOD=",M) end."> N keyin M:=M-N boshqa N:=N-M oxiri; write("HOD=",M) end." title="(!LANG:Paskal dasturi 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 keyin M:=M-N boshqa N:=N-M oxiri; write("HOD=",M) end." title="(!LANG:Paskal dasturi 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."> !}