Evklid algoritmi doira ishg'ol bo'yicha taqdimot. "Evklid algoritmi" mavzusida taqdimot. Evklid algoritmining g'oyasi

Sinf: 6

Dars maqsadlari:

faktorizatsiya yordamida eng katta umumiy bo'luvchini topish algoritmini tuzatish;
tegishli ta'rif va tushunchalarni takrorlash;
talabalarni Evklid algoritmi bilan tanishtirish;
matematik madaniyat malakalarini shakllantirish

Uskunalar: kompyuter, proyektor, ekran.

Darslar davomida

1. Tashkiliy vaqt (o‘quvchilarning darsga tayyorgarligini tekshirish, yo‘qligini belgilash) (1 daqiqa)

2. Og'zaki ish: (6 min)

1. Mahsulotni daraja bilan almashtiring:

d) a * a * a * a * a

Hisoblang: 2 3 ; 52; 3 3 ; 10 4 .
Ifodaning qiymatini toping: (3?3?5?11): (3?11). Qanday xulosa chiqarish mumkin?
Bo'linishni bajaring a ustida b agar a=170, b=35. Tenglikni yozing, a ga nima teng.

Bu tenglikni umumiy shaklda yozing: a bo'linuvchi, b esa bo'linuvchi bo'ladi. Bo'lim q va qolgan r bo'lsin, keyin: a = bq + r , va q natural son yoki nol bo'lishi mumkin. r har qanday raqam bo'lishi mumkinmi? [ r natural son va 0 < r < b .] Agar r = 0 bo'lsa, a va b raqamlari haqida nima deyish mumkin? Butun sonlarni bo'lish - bu qoldiq bilan bo'lishning maxsus holati.

a soni b soniga qoldiqsiz bo'linish yoki bo'linishini toping va tushuntiring, agar:

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. Asosiy bilimlarni yangilash(10 daqiqa)

1) Savollar:

Raqamning bo'luvchisi nima a ?

Bosh son nima?

Sonni tub omillarga ko‘paytirish nimani anglatadi?

2, 3, 5, 9,10 ga boʻlinish belgilarini tuzing;

Bir xonali kompozit songa misol keltiring;

77 soni tub son ekanligi rostmi?

Nima uchun bitta sonni 2 ta tub omilga, ikkinchisini esa 3 ta tub omilga ajratish mumkin bo'lsa, unda bu raqamlar teng emas?

Ikki tub sonning ko‘paytmasi qaysi tub yoki qo‘shma son hisoblanadi?

Ikki yoki undan ortiq sonning eng katta umumiy boʻluvchisi nima?

Qanday sonlar ko‘p sonli sonlar deb ataladi?

GCD ni topish usullarini takrorlang: natural sonlarning GCD ni topish uchun turli xil algoritmlar mavjud.

1 usul: Agar ikkita raqam berilgan bo'lsa va ular nisbatan kichik bo'lsa, unda eng yaxshi algoritm qo'pol qidiruvdir. Biroq, katta sonlar uchun raqamlarning barcha bo'luvchilarini sanab, gcd(a;b) ni toping. a va b Jarayon mashaqqatli va ishonchsizdir.

Shuni yodda tutish kerakki, har qanday sonning gcd soni ularning eng kichigidan oshmaydi.

2 yo'l: faktoring raqamlari bo'yicha (eng keng tarqalgan) (Ilova, 1-slayd)

2) 24 va 16 raqamlarining GCD ni hisoblang.

3) Raqamlarni koeffitsientlarga ajrating: 875 va 8000 va bu raqamlarning GCD ni hisoblang.

(Misol sifatida 8000 raqamidan foydalanib, nol bilan tugaydigan raqamlarni faktoring qilishning oddiy usulini takrorlang: chunki 10=2 *5, keyin 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 *5 3)

4) Agar ularning ko'paytmasi 3000 ga teng bo'lsa, uchta raqamning GCD 15 ga teng bo'lishi mumkinmi? [ Yo'q, kabi

15 \u003d 3 * 5, ya'ni 3 raqami uchta raqamning har birining kengayishiga kiritilishi kerak. Lekin, 3000 = 2 3 * 3 * 5 3.]

5) R vazifani yeng“Sinfga darsliklar keltirildi: matematikadan 24 ta, tarixdan 36 ta va geografiyadan 48 ta. Bu kitoblardan har birida matematika, tarix va geografiya boʻyicha bir xil miqdordagi kitoblar boʻlishi uchun eng koʻp qancha toʻplam yasalishi mumkin? Har bir to'plamda nechta kitob bo'ladi?"

4. Tekshirish ishi (Ilova, 2-slayd) (6 min)

5. Yangi materialni o‘rganish (10 daqiqa)

O'qituvchi: GCD (a, b) ni topishning o'rganilgan usuli sodda, tushunarli va qulay, ammo uning sezilarli kamchiligi bor: agar berilgan raqamlar katta bo'lsa va hatto unchalik oson bo'lmagan bo'lsa, GCD (a, b) ni topish vazifasi. ancha qiyinlashadi. Bundan tashqari, ko'p mehnat qilib, biz GCD(a, b) = 1 ekanligiga ishonch hosil qilamiz va barcha ishlar behuda qilinganga o'xshaydi.

Evklid raqamlarni oldindan qayta ishlamasdan gcd(a, b) ni topishning ajoyib usulini topdi. (ilova, 3 va 4-slaydlar) Keyinchalik, bu algoritm deb nomlandi Evklid algoritmi)

Evklid algoritmi bilan tanishamiz. gcd(102;84) ni topish talab qilinsin. Bir raqamni ikkinchisiga bo'ling va qolganini toping.

Endi 84 va 18 raqamlari uchun xuddi shunday amalni bajaramiz:

Keyingi qadam 18 va 12 uchun:

Endi - 12 va 6 uchun:

0-qoldiq. Jarayon tugadi.

Bu jarayon cheksiz bo'lishi mumkin emas, chunki qoldiqlar kamayadi, qoladi manfiy bo'lmagan butun sonlar, ularning to'plami, ma'lumki, pastdan chegaralanadi:

84 >18 > 12> 6 >0

Agar siz yozma tengliklarga diqqat bilan qarasangiz, barcha raqamlar juftlarining GCD bir-biriga teng ekanligini aniqlashingiz mumkin (talabalarni o'ylashga taklif qiling - nima uchun?),

ya'ni gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. Ammo 6 raqami 0 bo'lmagan oxirgi qoldiqdir .

Haqiqatan ham, agar c a va b sonlarning ixtiyoriy umumiy bo'luvchisi bo'lsa, u holda r = a - bq c ga bo'linadi; va aksincha, agar c b va r ning ixtiyoriy umumiy bo'luvchisi bo'lsa, u holda a c ga bo'linadi. Ya'ni (a; b) va (b; r) juftlarning barcha umumiy bo'luvchilari mos keladi va shuning uchun ularning eng katta umumiy bo'luvchilari ham mos keladi.

Evklid algoritmining qulayligi, ayniqsa, yozuv shaklini jadval shaklida qo'llasak, sezilarli bo'ladi:

Ushbu planshetda asl raqamlar birinchi navbatda yozib olinadi, ongga bo'linadi, qolganlari o'ngga, shaxsiy raqamlar esa jarayon tugaguniga qadar pastki qismga yoziladi. Oxirgi bo'luvchi GCD hisoblanadi.

Shunday qilib, ikkita sonning eng katta umumiy bo'luvchisi 0 ga teng bo'lmagan oxirgi, katta sonni kichikroqqa bo'lishda qoldiq bo'ladi, ya'ni agar a = b*q + r, keyin gcd(a; b) = gcd(b; r)

Ushbu operatsiyalar ketma-ketligi deyiladi Evklid algoritmi. Ushbu algoritm raqamlarning GCD ni faktoringsiz topish imkonini beradi (ilova, 5-slayd)

6. Mashqlar (10 min)

1. Misolni ko'rib chiqish tavsiya etiladi. 323 va 437 raqamlarining GCD ni topish kerak bo'lsin. Buni tanlash yoki tub omillarga ajratish yo'li bilan amalga oshirish oson emas, chunki bu sonlarning hech biri 2, 3, 5, 7, 11 ga karrali emas. quyidagicha davom eting (

Mavzu: GCD ni topish uchun Evklid algoritmi.

Maqsadlar:avval o‘rganilgan mavzularni takrorlash, eng katta umumiy bo‘luvchi va eng kichik umumiy ko‘paytirish, Evklid algoritmi bilan tanishtirish.

O`quv maqsadlari - eng katta umumiy bo`luvchi va eng kichik umumiy karrali tushunchalarini, ularni topish qoidasini takrorlash. Evklid algoritmiga kirish. Tegishli vazifalarni yechish orqali Evklid algoritmini tuzating.

Rivojlanish vazifalari - mantiqiy fikrlashni, e'tiborni, nutq xotirasini rivojlantirish, yangi bilimlarni mustaqil ravishda kashf qilish qobiliyati, matematik qiziqish, mavzuga kognitiv qiziqish.

Ta'limning vazifalari - matematik fikrlash, o'zaro yordam, o'z-o'zini tekshirish va xatolarini tahlil qilish madaniyatini tarbiyalash.

Kartalarda ishlash

GCD yoki LCM raqamlarini toping va iborani shifrlang:

300

D: GCD (33,88)

H: NOC(9,40)

Javob: 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)

Javob: GCD (17.34)

Men: gcd (102.68)

E: GCD(18,12)

Oxirgi jadvalda qolgan raqamlar juftligini yozing

Javoblar:

300

LEKIN

Kimga

LEKIN

D: GCD(33,88)=11

G: LCM(9,40)=360

Javob: 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: gcd(18,35)=1

Javob: GCD(17.34)=17

VA: GCD(102.68)=34

E: GCD(18,12)=6

Yana 2 ta so'zni taxmin qiling

Oxirgi jadvaldagi raqamlar haqida nima deyish mumkin? Ular ko'p, ya'ni. agar bu raqamlarni tub omillarga ajratsak, ular bir xil ko'rsatkichlarga ega bo'lmaydi. Bunday raqamlarning GCD ni qanday topish mumkin? Bunday raqamlarning nod =1. Va LCMni qanday topish mumkin, LCMni topish uchun siz bu raqamlarni bir-biriga ko'paytirishingiz kerak.

Birinchi ustunda bittasi ikkinchisiga to'liq bo'linmaydigan juft raqamlar mavjud. Bular. qolgani 0 emas.

Bunday raqamlarning GCD va LCM ni qanday topdingiz? (Ushbu raqamlarni tub omillarga ajratish orqali)

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

GCD va LCM ni topish qoidasini eslang, LCM (a, c) \u003d (a * b) formulasini toping va tekshiring: 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

Yangi mavzuni o'rganish:

Qaysi juft raqamlarning GCD 6 ga teng?

6=gcd(48.18)=gcd(30.18)=gcd(12.18)

Nimani sezdingiz? 30 ga qanday erishdingiz? 48-18

12 ni qanday oldingiz? 30-18

Qachon a> b \u003d GCD (a-b, c)

Bular. GCD (a, c) v> a = GCD (a, c-a) bo'lganda

Bu tenglikni kim davom ettira oladi?

6=gcd(48.18)=gcd(30.18)=gcd(12.18) = gcd(12.6)=gcd(6.6)=6

Evklid algoritmi shu qoidaga asoslanadi.

Evklid algoritmi- ikkitasini topish uchun samarali. Algoritm birinchi marta VII va X kitoblarda tasvirlangan "" nomi bilan ataladi.

Eng oddiy holatda Evklid algoritmi musbat butun sonlar juftligiga qo'llaniladi va kichikroq va katta va kichik sonlar orasidagi yangi juftlikni hosil qiladi. Jarayon raqamlar teng bo'lguncha takrorlanadi. Topilgan son asl juftlikning eng katta umumiy boʻluvchisidir.

Qadimgi yunon matematiklari bu algoritmni "o'zaro ayirish" deb atashgan.

Ushbu usulning mohiyati quyidagicha: katta sondan kichik sonni raqamlar teng bo'lguncha ayirish, kattaroqni farq bilan almashtiring. Bu sodir bo'lgach, GCD topiladi. (Doskadagi misol - 48 va 18 raqamlari)

Birinchi savol: bu raqamlar tengmi? Yo'q, ular teng emas, shuning uchun biz kattasidan kichikni ayiramiz 48-18 = 30. 30 18 ga teng emas, ya'ni 30-18= 12, 18-12=6, 12-6=6. Ya'ni, bu harakatlarni raqamlar teng bo'lguncha bajaramiz. Demak, gcd(48,18)=6

48 va 18 raqamlarining GCD ni bilib, NOCni toping. LCM(48,18)=(48*18):6=48*3=144

Evklid algoritmi yordamida GCD(102;68) ni topamiz.

Keling, topamiz NOD (357;273)

Bu erda biz 84 sonini 3 marta va 21 raqamini uch marta ayirdik.

Qanday qilib ayirishlarni amalga oshirmasdan, bitta qatorda nechta ayirish bo'lishini aniqlash mumkin va natija qanday farq qiladi? Qanday holatlarni ko'rib chiqish kerak? ( ko'rsatma: bo'linishni eslang.)

Umumiy qoidani quyidagicha shakllantirish mumkin: agar raqam a ga bo'linmaydi b, keyin ga bo'linganda qoldig'i bilan almashtiriladi b(qachon a< b bu qoldiq a); agar a tomonidan bo'linadi b, keyin uni raqam bilan almashtiring b. Aynan bir xil qoida, almashtirish bilan a va b, uchun ham amal qiladi b. Kattaroq raqam bo'lmoq kichikga, keyin kichik birinchi qoldiqga, keyin birinchi qoldiq ikkinchi qoldiqga va hokazo, siz 0 ga erishguningizcha.0 ga teng bo'lmagan oxirgi qoldiq GCD .

GCD (357;273) toping.

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

gcd(357.273)=gcd(273.84)=gcd(84.21)=21

Evklid algoritmining qulayligi, ayniqsa, yozuv shaklini jadval shaklida qo'llasak, sezilarli bo'ladi:

Shunday qilib, ikkita sonning eng katta umumiy bo'luvchisi katta sonni kichikga bo'lishda nolga teng bo'lmagan oxirgi qoldiqdir., ya'niagar a = b *q + r, keyin gcd(a; b) = gcd(b; r)

Ushbu operatsiyalar ketma-ketligi deyiladi Evklid algoritmi.

1) Evklid algoritmidan foydalanib, raqamlarning GCD ni toping:

A) 703, 481;B) 2112 va 1680; B) 5075 va 1450 yillar

GCD(703;481)=37

GCD(2112;1680)=48

GCD(5075;1450)=

Natijalarni kompyuterda tekshiring.

Kompyuterda bolalar uchun vazifa GCD va LCM ni topish dasturidan foydalangan holda uchta raqam uchun GCD va LCM ni topishdir.

gcd(150, ____) = ____

GCD (450,315,135)=____

GCD(135, ____) = ____

GCD (2160,1350,1080)=____

GCD (1080, ____) = ____

GCD (5300,3180,2120)=____

GCD (2120, ____) = ____

(Uch yoki undan ortiq sonning GCD ni topish uchun avval ulardan ikkitasining GCD ni, so‘ngra topilgan bo‘linuvchining GCD ni va uchinchi berilgan sonni toping.

va uchinchi berilgan raqam.

7. Natijalarni kompyuterda tekshirish. Muammoni mustaqil hal qilish.

1) Xuddi shu sovg'alar sinf o'quvchilari uchun tayyorlandi. Barcha sovg'alar 120 shokolad, 280 shirinlik va 320 yong'oqdan iborat edi. Birinchi sinfda 30 dan ortiq o‘quvchi borligi ma’lum bo‘lsa, nechta o‘quvchi bor?

Javob: ___________________________________

2) Stansiyada uchta yo‘lovchi poyezdi bor: birinchisida – kupelarda 418 o‘rin, ikkinchisida – 494, uchinchisida – 456. Agar o‘rindiqlar soni bir xil bo‘lsa, har bir poyezdda nechta kupe vagon bo‘ladi. har bir mashinada va ularning umumiy soni 20 dan ortiqmi? Javob _________________________

3) 156 dona choy, 234 dona oq va 390 dona qizil atirguldan guldastalar tayyorlangan va har bir turdagi atirgulning barcha guldastalarida bir xil bo‘lgan va bunday guldastalar soni 50 tadan ortiq bo‘lgan. Bu atirgullardan nechta guldasta qilingan va nechta har bir turdagi atirgullar bitta guldastada edi? Javob ______________________

Darsning xulosasi. GCD va LCM ni qanday topish usuli bilan biz darsda uchrashdik. Evklid algoritmi. Bu usulning boshqa nomi nima? (ayirish usuli). Bu usul qanday takomillashtirildi? Bo'linish bilan katta son kichikroq songa, keyin kichik son birinchi qoldiqga, so'ngra birinchi qoldiq ikkinchi qoldiqga bo'linadi va 0 ni olmaguningizcha davom etadi. Oxirgi nolga teng bo'lmagan qoldiq GCD hisoblanadi. raqamlar.

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. Yevklid (miloddan avvalgi 365-300 yillar) Qadimgi yunon matematiklari bu algoritmni ἀnthυυρaρestis yoki ἀnἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἀἄαραρρερερτος - "o'zaro ayirma" algoritmini qadimgi yunon matematiklari 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 oʻrtasidagi 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:

STEP Operation M N Shart 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 3 >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:

Tarbiyaviy:

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

Tarbiyaviy:

yangi materialni o'rganishda mustaqillik va mas'uliyatni shakllantirish

Rivojlanayotgan:

e'tibor va analitik fikrlashni rivojlantirish

Dars rejasi:

Tashkiliy vaqt
Bilimlarni yangilash
Yangi mavzuni tushuntirish
Amaliy qism
Darsni yakunlash
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 ning M - N sonining bo'luvchisi ekanligini anglatadi. 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:

Kompyuteringizda Evklid dasturini ishga tushiring. Uni M=32, N=24 da sinab ko‘ring; M = 696, N = 234.
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)

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

slayd 1

slayd 2

slayd 3

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:

slayd 4

STEP Operation M N Shart 1 InputM 48 2 InputN 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 XulosaM

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, ular nisbatan tub son deyiladi. 2. Agar LCM(n, m) = n * m / gcd(n, m) boʻlsa, n va m sonlarining eng kichik umumiy karrali (LCM)ni toping. 3. Berilgan natural sonlar m va n. 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.

Evklid algoritmi doira ishg'ol bo'yicha taqdimot. "Evklid algoritmi" mavzusida taqdimot. Evklid algoritmining g'oyasi

Slayd sarlavhalari:

Ko‘rib chiqish:

Mavzu: "Evklid algoritmi"

Tashkiliy vaqt

Bilimlarni yangilash.