Евклид алгоритмі шеңберінің сабағына арналған презентация. «Евклид алгоритмі» тақырыбына презентация. Евклид алгоритмінің идеясы

Сынып: 6

Сабақтың мақсаттары:

• көбейткіштерге бөлу арқылы ең үлкен ортақ бөлгішті табу алгоритмін бекіту;
• байланысты анықтамалар мен ұғымдарды қайталау;
• оқушыларды Евклид алгоритмімен таныстыру;
• математикалық мәдениет дағдыларын қалыптастыру

Құрал-жабдықтар: компьютер, проектор, экран.

Сабақтар кезінде

1. Ұйымдастыру кезеңі (оқушылардың сабаққа дайындығын тексеру, жоқ деп бағалау) (1 мин)

2. Ауызша жұмыс: (6 мин)

1. Өнімді дәрежемен ауыстырыңыз:

г) а * а * а * а * а

1. Есептеңіз: 2 3 ; 52; 3 3 ; 10 4 .
2. Өрнектің мәнін табыңыз: (3?3?5?11): (3?11). Қандай қорытынды жасауға болады?
3. Бөлуді орындау аүстінде б a=170 болса, b=35. Теңдікті жаз, не тең а.

Бұл теңдікті жалпы түрде жазыңыз: а бөлінгіш болады, ал б бөлгіш болады. Бөлшек q, ал қалдық r болсын, онда: a = bq + r , және q натурал сан немесе нөл болуы мүмкін. r кез келген сан бола ала ма? [ r – натурал сан, ал 0 < r < b .] Егер r = 0 болса, a және b сандары туралы не айтуға болады? Бүтін бөлу - қалдықпен бөлудің ерекше жағдайы.

4. а саны b санына қалдықсыз бөлінетінін анықтаңыз және түсіндіріңіз, егер:

а) a = 2 3 * 3 * 5 * 7;

б) a \u003d 2 4 * 3 * 5 7;

b = 2 7 * 3 * 5 4

в) a \u003d 2 * 3 4 * 5 * 13;

b = 2 * 3 3 * 5 * 11.

3. Негізгі білімді жаңарту(10 минут)

1) Сұрақтар:

Санның бөлгіші дегеніміз не а ?

Жай сан дегеніміз не?

Санды жай көбейткіштерге көбейту нені білдіреді?

2, 3, 5, 9,10-ға бөлінгіштік белгілерін тұжырымда;

Бір таңбалы құрама санға мысал келтір;

77 саны жай сан екені рас па?

Неліктен бір санды 2 жай көбейткішке, ал екіншісін 3 жай көбейткішке ыдыратуға болатын болса, онда бұл сандар тең емес?

Қандай сан, жай немесе құрама, екі жай санның көбейтіндісі?

Екі немесе одан да көп сандардың ең үлкен ортақ бөлгіші қандай?

Қандай сандар екіжақты сандар деп аталады?

GCD табу жолдарын қайталаңыз: натурал сандардың GCD табудың әртүрлі алгоритмдері бар.

1 жол:Егер екі сан берілсе және олар салыстырмалы түрде аз болса, онда ең жақсы алгоритм дөрекі күшпен іздеу болып табылады. Дегенмен, үлкен сандар үшін сандардың барлық бөлгіштерін тізімдеу арқылы gcd(a;b) табыңыз. ажәне бПроцесс қиын және сенімсіз.

Кез келген санның gcd саны олардың ең кішісінен аспайтынын есте ұстаған жөн.

2 жол:факторингтік сандар бойынша (ең таралған) (Қосымша, слайд 1)

2) 24 және 16 сандарының GCD есептеңіз.

3) Сандарды көбейткіштерге бөліңіз: 875 және 8000 және осы сандардың GCD-ін есептеңіз.

(Мысал ретінде 8000 санын пайдаланып, нөлмен аяқталатын сандарды көбейтудің қарапайым әдісін қайталаңыз: 10=2 *5 болғандықтан, содан кейін 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 *5 3)

4) Үш санның GCD көбейтіндісі 3000-ға тең болса, 15-ке тең бола ала ма? [ Жоқ, сияқты

15 \u003d 3 * 5, яғни 3 саны үш санның әрқайсысының кеңеюіне қосылуы керек. Бірақ, 3000 = 2 3 * 3 * 5 3.]

5) П тапсырманы жеу"Сыныпқа оқулықтар әкелінді: математикадан - 24, тарихтан - 36 және географиядан - 48. Әрқайсысында математика, тарих және география бойынша кітаптардың саны бірдей болуы үшін бұл кітаптардан ең көп қанша жинақ жасауға болады? Әр жинақта қанша кітап болады?»

4. Тексеру жұмысы (қосымша, слайд 2) (6 мин)

5. Жаңа материалды меңгеру (10 мин)

Мұғалім: GCD(a, b) табудың зерттелетін әдісі қарапайым, түсінікті және ыңғайлы, бірақ оның айтарлықтай кемшілігі бар: егер берілген сандар үлкен болса, тіпті оңай көбейткіштерге жіктелмеген болса, онда GCD(a, b) табу міндеті қойылады. айтарлықтай қиынға соғады. Сонымен қатар, біз көп жұмыс жасай отырып, GCD(a, b) = 1 екеніне көз жеткіземіз және барлық жұмыс босқа орындалған сияқты.

Евклид сандарды алдын ала өңдеусіз gcd(a, b) табудың тамаша әдісін тапты. (Қосымша, 3 және 4 слайдтар)Кейіннен бұл алгоритм ретінде белгілі болды Евклид алгоритмі)

Евклид алгоритмімен танысайық. gcd(102;84) табу керек болсын. Бір санды екіншісіне бөліп, қалғанын табыңыз.

Енді 84 және 18 сандарына бірдей амалды орындайық:

Келесі қадам 18 және 12 үшін:

Енді - 12 және 6 үшін:

0- қалдық. Процесс аяқталды.

Бұл процесс шексіз болуы мүмкін емес, өйткені қалдықтар азаяды, қалады Теріс емес бүтін сандар, олардың жиыны, белгілі болғандай, төменнен шектеледі:

84 >18 > 12> 6 >0

Жазбаша теңдіктерге мұқият қарасаңыз, барлық сандар жұптарының GCD бір-біріне тең екенін анықтауға болады (оқушыларды ойлануға шақырыңыз - неге?),

яғни gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. Бірақ 6 саны 0 емес соңғы қалдық .

Шынында да, егер c a және b сандарының ерікті ортақ бөлгіші болса, онда r = a - bq с-ке бөлінеді; және керісінше, егер c b және r санының ерікті ортақ бөлгіші болса, а саны с-ға бөлінеді. Яғни (a; b) және (b; r) жұптарының барлық ортақ бөлгіштері сәйкес келеді, демек олардың ең үлкен ортақ бөлгіштері де сәйкес келеді.

Евклид алгоритмінің ыңғайлылығы, егер кесте түрінде белгілеу формасын қолдансақ, әсіресе байқалады:

Бұл планшетте бастапқы сандар алдымен жазылады, санада бөлінеді, қалғандары оңға, ал жеке сандар процесс аяқталғанша төменгі жағына жазылады. Соңғы бөлгіш - GCD.

Сонымен, екі санның ең үлкен ортақ бөлгіші 0-ге тең емес соңғысы, үлкен санды кішіге бөлгендегі қалдық, яғни егер a = b*q + r, онда gcd(a; b) = gcd(b; r)

Бұл әрекеттер тізбегі деп аталады Евклид алгоритмі. Бұл алгоритм сандарды көбейтусіз GCD табуға мүмкіндік береді (қосымша, слайд 5)

6. Жаттығулар (10 мин)

1. Мысал қарастырған жөн. 323 және 437 сандарының GCD табу қажет болсын. Мұны таңдау немесе жай көбейткіштерге бөлу арқылы жасау оңай емес, өйткені бұл сандардың ешқайсысы 2, 3, 5, 7, 11-ге еселік емес. келесідей жалғастырыңыз (

Тақырыбы: Евклидтің GCD табу алгоритмі.

Мақсаттар:бұрын өткен тақырыптарды қайталау Ең үлкен ортақ бөлгіш және ең кіші ортақ еселік, Евклид алгоритмімен таныстыру.

Оқыту мақсаты – ең үлкен ортақ бөлгіш және ең кіші ортақ еселік ұғымдарын, оларды табу ережесін қайталау. Евклид алгоритмімен таныстыру. Сәйкес тапсырмаларды шешу арқылы Евклид алгоритмін түзетіңіз.

Дамытушылық міндеттері – логикалық ойлауын, зейінін, сөйлеуді есте сақтауын, жаңа білімді өз бетімен ашуға дағдыландыру, математикалық қызығушылықты, пәнге деген танымдық қызығушылығын арттыру.

Тәрбиенің міндеттері математикалық ойлау, өзара көмек көрсету, өзін-өзі сынау және өз қателерін талдау мәдениетін тәрбиелеу.

Карталармен жұмыс

GCD немесе LCM нөмірлерін табыңыз және сөйлемді шешіңіз:

34

16

300

6

1

12

2

34

11

17

D: GCD(33,88)

H: NOC(9,40)

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

М: NOC(25.12)

Т: NOC(4,8,16)

H: NOC(12,40)

B: GCD(18,35)

A: GCD(17,34)

Мен: gcd (102,68)

E: GCD(18,12)

Соңғы кестеде қалған сандар жұптарын жазыңыз

Жауаптары:

34

16

300

6

1

12

2

34

11

17

БІРАҚ

Л

Г

О

Р

Және

Т

М

Е

AT

Кімге

Л

Және

D

БІРАҚ

D: GCD(33,88)=11

G: LCM(9,40)=360

A: 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

М: LCM(25,12)=300

Т: LCM(4,8,16)=16

H: LCM(12,40)=120

B: gcd(18,35)=1

A: GCD(17.34)=17

ЖӘНЕ: GCD(102.68)=34

E: GCD(18,12)=6

Тағы 2 сөз тап

Соңғы кестедегі сандар туралы не айтуға болады? Олар копрайм, яғни. егер бұл сандарды жай көбейткіштерге бөлсек, онда олардың бірдей көбейткіштері болмайды. Мұндай сандардың GCD-ін қалай табуға болады? Мұндай сандардың түйіні =1. Ал LCM-ді қалай табуға болады, LCM-ді табу үшін бұл сандарды бір-біріне көбейту керек.

Бірінші бағанда бірі екіншісіне толық бөлінбейтін жұп сандар берілген. Анау. қалғаны 0 емес.

Мұндай сандардың GCD және LCM-ін қалай таптыңыз? (Осы сандарды жай көбейткіштерге бөлу арқылы)

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

GCD және LCM табу ережесін еске түсіріңіз, LCM (a, c) \u003d (a * b) формуласын табыңыз және тексеріңіз: 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

Жаңа тақырыпты пысықтау:

Қандай сандар жұбының GCD саны 6?

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

Не байқадыңыз? 30-ға қалай жеттіңіз? 48-18

12-ні қалай алдың? 30-18

a> b \u003d GCD (a-b, c) болғанда

Анау. GCD (a, c) v> a = GCD (a, c-a) болғанда

Бұл теңдікті кім жалғастыра алады?

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

Евклид алгоритмі осы ережеге негізделген.

Евклид алгоритмі- екі табу үшін тиімді. Алгоритм оны алғаш рет VII және X кітаптарында сипаттаған «» атымен аталған.

Ең қарапайым жағдайда Евклид алгоритмі оң бүтін сандар жұбына қолданылады және кішірек саннан және үлкен және кіші санның арасында тұратын жаңа жұпты жасайды. Процесс сандар тең болғанша қайталанады. Табылған сан бастапқы жұптың ең үлкен ортақ бөлгіші болып табылады.

Ежелгі грек математиктері бұл алгоритмді «өзара азайту» деп атаған.

Бұл әдістің мәні мынада: сандар тең болғанша үлкен саннан кіші санды алып тастаңыз, үлкенін айырмамен ауыстырыңыз. Бұл орын алғаннан кейін GCD табылады. (Тақтадағы мысал – 48 және 18 сандары)

Бірінші сұрақ: бұл сандар тең бе? Жоқ, олар тең емес, сондықтан үлкенінен кішісін алып тастаймыз 48-18 = 30. 30 18-ге тең емес, бұл 30-18= 12, 18-12=6, 12-6=6 дегенді білдіреді. Яғни, бұл әрекеттерді сандар тең болғанша орындаймыз. Демек, gcd(48,18)=6

48 және 18 сандарының GCD-ін біле отырып, ҰОҚ-ны табыңыз. LCM(48,18)=(48*18):6=48*3=144

Евклид алгоритмін пайдаланып GCD(102;68) табайық.

Табайық NOD (357;273)

Мұнда біз 84 санын 3 рет, ал 21 санын үш рет алып тастадық.

Алу амалдарын жасамай, бір қатарда қанша азайту болатынын қалай білуге ​​болады және нәтиже қандай айырмашылық болады? Қандай жағдайларды қарастыру керек? ( көрсеткіш: бөлуді есте сақтаңыз.)

Жалпы ережені былай тұжырымдауға болады: егер сан абойынша бөлінбейді б, содан кейін оны бөлгенде оның қалдығымен ауыстырылады б(Егер а< ббұл қалдық а); егер абөлінген б, содан кейін оны санмен ауыстырыңыз б. Дәл сол ереже, ауыстырумен ажәне б, үшін де жарамды б. Үлкенірек сан бөлу кішіге, содан кейін кіші бірінші қалдыққа, содан кейін бірінші қалдық екінші қалдыққа және т.с.с. 0 алынғанша.0-ге тең емес соңғы қалдық - GCD .

GCD (357;273) табыңыз.

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

Евклид алгоритмінің ыңғайлылығы, егер кесте түрінде белгілеу формасын қолдансақ, әсіресе байқалады:

Бұл планшетте бастапқы сандар алдымен жазылады, санада бөлінеді, қалғандары оңға, ал жеке сандар процесс аяқталғанша төменгі жағына жазылады. Соңғы бөлгіш - GCD.

Осылайша, екі санның ең үлкен ортақ бөлгіші үлкен санды кішіге бөлген кездегі нөлдік емес соңғы қалдық болып табылады., яғниегер a = b *q + r, онда gcd(a; b) = gcd(b; r)

Бұл әрекеттер тізбегі деп аталады Евклид алгоритмі.

1) Евклид алгоритмін пайдаланып, сандардың GCD-ін табыңыз:

А) 703, 481;В) 2112 және 1680; B) 5075 және 1450

GCD(703;481)=37

GCD(2112;1680)=48

GCD(5075;1450)=

Нәтижелерді компьютерде тексеріңіз.

Компьютердегі балаларға арналған тапсырма GCD және LCM табу бағдарламасының көмегімен үш санға арналған GCD және LCM табу болып табылады.

gcd(150, ____) = ____

GCD(450,315,135)=____

GCD(135, ____) = ____

GCD(2160,1350,1080)=____

GCD (1080, ____) = ____

GCD(5300,3180,2120)=____

GCD (2120, ____) = ____

(Үш немесе одан да көп сандардың GCD-ін табу үшін алдымен олардың кез келген екеуінің GCD-ін, содан кейін табылған бөлгіштің GCD-ін және үшінші берілген санды табыңыз.

және үшінші берілген сан.

7. Нәтижелерді компьютерде тексеру. Мәселелерді өз бетінше шешу.

1) Сынып оқушылары үшін де осындай сыйлықтар дайындалды. Барлық сыйлықтар 120 шоколад, 280 тәтті және 320 жаңғақ болды. Бірінші сыныпта 30-дан астам оқушы бар екені белгілі болса, неше оқушы бар?

Жауабы: ___________________________________

2) Станцияда үш жолаушылар пойызы бар: біріншісінде – купе вагондарында – 418 орын, екіншісінде – 494, үшіншісінде – 456. Орындар саны бірдей болса, әр пойызда қанша купе вагоны бар. әрбір вагонда және олардың жалпы саны 20-дан астам? Жауабы ________________________________

3) 156 шайдан, 234 ақ және 390 қызыл раушан гүлінен гүл шоқтары жасалды және әр түрдегі раушан гүлінің барлық шоқтарында бірдей болды және мұндай гүл шоқтарының саны 50-ден астам болды. Осы раушан гүлдерінен неше гүл шоқтары жасалды және қанша әр түрдегі раушан гүлдері бір букетте болды ма? Жауап_________________

Сабақты қорытындылау. Біз сабақта GCD және LCM табудың қандай әдісімен кездестік. Евклид алгоритмі. Бұл әдіс басқаша қалай аталады? (азайту әдісі). Бұл әдіс қалай жетілдірілді? Бөлу кезінде үлкен сан кіші санға бөлінеді, содан кейін кіші сан бірінші қалдыққа, содан кейін бірінші қалдық екінші қалдыққа бөлінеді және 0 алынғанша жалғасады. Соңғы нөлдік емес қалдық GCD болып табылады. сандар.

Презентацияларды алдын ала қарау мүмкіндігін пайдалану үшін Google есептік жазбасын (есептік жазбасын) жасап, жүйеге кіріңіз: https://accounts.google.com

Слайдтар тақырыбы:

Евклид алгоритмі Евклид, ежелгі грек математигі. 3 ғасырда Александрияда жұмыс істеді. BC e. Ежелгі математика негіздерін, элементар геометрияны, сандар теориясын, қатынастардың жалпы теориясын және шекаралар теориясының элементтерін қамтитын аудандар мен көлемдерді анықтау әдістемесін қамтитын негізгі еңбек «Бастаулар» (15 кітап). Математиканың дамуына зор ықпал етті. Астрономия, оптика, музыка теориясы бойынша жұмыс істейді. Евклид (б.з.б. 365-300)

ЕВКЛИД АЛГОРИТМІ Евклид алгоритмі – екі теріс емес бүтін санның ең үлкен ортақ бөлгішін (gcd) табуға арналған алгоритм. Евклид (б.з.д. 365-300 жж.) Ежелгі грек математиктері бұл алгоритмді ἀνθυφαίρεσις немесе ἀνταναίρεσις – «өзара алу» деп атаған.

Есептеу GCD GCD = екі натурал санның ең үлкен ортақ бөлгіші бастапқы екі сан да қалдықсыз бөлінетін ең үлкен сан. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Екі санның үлкенін үлкені мен кішісінің айырмасымен ауыстырыңыз, олар тең болғанша. Бұл NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 Мысал:

ҚАДАМ операциясы M N Шарт 1 кіріс M 48 2 кіріс N 18 3 M  N 48 18, иә 4 M>N 48>18, иә 5 M:=M-N 30 6 M  N 30  18, иә 7 M>N 3 >18, иә 8 M:=M-N 12 9 M  N 12 18, иә 10 M>N 12 >18, жоқ 11 N:=N-M 6 12 M  N 12  6, иә 13 M>N 12 >6 , иә 14 M:=M-N 6 15 M  N 6  6, жоқ 16 M шығысы

Evklid бағдарламасы; var m, n: бүтін; begin writeln("vved 2 chisla"); readln(m,n); while mn do begin if m>n болса, m:=m-n else n:= n-m ; Соңы; write("nod=",m); readln end.

0.Компьютерде Evklid бағдарламасын іске қосыңыз. Оны M=32, N=24 арқылы тексеріңіз; M=696, N=234. бір . Берілген екі санның қос жай екенін тексеріңіз. Ескерту. Екі санның ең үлкен ортақ бөлгіші 1 болса, екі санды қос жай сандар деп атайды. LCM(n, m) = n * m / gcd(n, m) болса, n және m сандарының ең кіші ортақ еселігін (LCM) табыңыз. 3 . m және n натурал сандары берілген. p / q = m / n болатындай ортақ бөлгіштері жоқ p және q натурал сандарын табыңыз. 4. Үш санның GCD-ін табыңыз. Ескерту. GCD(a , b , c)= GCD(gcd(a , b), c) Тапсырмалар

Алдын ала қарау:

Тақырыбы: «Евклид алгоритмі»

Сабақтың мақсаттары:

1. Тәрбиелік:

1. екі және үш санның gcd табу үшін Евклид алгоритмін қолдануды үйрену
2. «Тармақтану» және «Цикл» алгоритмдік құрылымдарын қолдану дағдыларын бекіту
3. Паскаль программалау тілінде бағдарламаларды жазу және жөндеу тәжірибесін алу

1. Тәрбиелік:

1. жаңа материалды меңгеруде дербестік пен жауапкершілікті қалыптастыру

1. Әзірлеуші:

1. зейінін және аналитикалық ойлауын дамыту

Сабақ жоспары:

1. Ұйымдастыру уақыты
2. Білімді жаңарту
3. Жаңа тақырыпты түсіндіру
4. Практикалық бөлім
5. Сабақты қорытындылау
6. Үй тапсырмасы.

Ұйымдастыру уақыты

Сәлем. Кім жоқ. Сан. Сабақтың тақырыбы. Үй тапсырмасы бойынша сұрақтар.

Білімді жаңарту.

Сұрақтар:

Алгоритмдік құрылымдардың қандай түрлерін білесіз?

Сызықтық құрылым дегеніміз не? (Bl-sh)

Тармақталған құрылым дегеніміз не? (Bl-sh)

Циклдік құрылым дегеніміз не? (Bl-sh)

Циклдің қандай түрлерін білесіз?

Паскаль программалау тілінде белгілі қайталану саны бар цикл қалай орындалады?

Паскаль программалау тілінде қайталану саны белгісіз цикл қалай жүзеге асады?

Жаңа тақырыпты түсіндіру (презентация)

Евклид туралы;

Евклид алгоритмінің идеясы

Бұл алгоритмнің идеясы мыналарға негізделген:

1. Егер M>N болса, онда GCD(M, N) = GCD(M - N, N) болатын қасиет.

Басқаша айтқанда, екі натурал санның gcd мәні олардың оң айырмасының (олардың айырмасының модулі) және кіші санның gcd-іне тең.

Дәлелдеу: K M мен N-нің ортақ бөлгіші болсын (M > N). Бұл M \u003d mK, N \u003d nK дегенді білдіреді, мұндағы m, n - натурал сандар және m > n. Сонда M - N \u003d K (m - n), бұл K санының M - N санының бөлгіші екенін білдіреді. Демек, M және N сандарының барлық ортақ бөлгіштері олардың M - N айырмасының, соның ішінде ең үлкенінің бөлгіштері болып табылады. ортақ бөлгіш.

2. Екінші айқын қасиет:

GCD(M, M) = M.

«Қолмен» санау үшін Евклид алгоритмі келесідей көрінеді:

1) егер сандар тең болса, онда олардың кез келгенін жауап ретінде қабылдаңыз, әйтпесе алгоритмді жалғастырыңыз;

2) үлкен санды сандардың үлкені мен кішісінің айырмасына ауыстыру;

3) 1-тармақты іске асыруға оралу.

Евклид алгоритмінің блок-схемасы

JS Pascal тіліндегі бағдарлама

Evklid бағдарламасы;

var m, n: бүтін;

БАСТА

writeln("2 саны берілген");

readln(m,n);

М.н жасаған кезде

БАСТА

Егер m>n

Сонда m:=m-n

Басқа n:=n-m;

Соңы;

Write("nod=",m);

readln

Соңы.

Практикалық бөлім

Сұрақтар мен тапсырмалар:

1. Компьютерде Evklid бағдарламасын іске қосыңыз. Оны M=32, N=24 бойынша сынау; М = 696, N = 234.
2. Берілген екі санның қос жай екенін тексеріңіз. Ескерту. Екі санның ең үлкен ортақ бөлгіші 1-ге тең болса, екі санды жай сандар деп атайды.

Сабақты қорытындылау

Бүгін сабақта біз екі теріс емес бүтін санның GCD-ін табуға мүмкіндік беретін Евклид алгоритмімен таныстық, осы алгоритмді жүзеге асыратын Паскаль программалау тілінде программа жаздық. Үйде сіз үш санның GCD және екі санның LCM табу үшін осы алгоритмді қолданатын тапсырма аласыз.

Үй тапсырмасы.

1. Келесі формула бойынша үш санның ең үлкен ортақ бөлгішін табу программасын жазыңыз:

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

2. Формула арқылы екі санның ең кіші ортақ еселігін (LCM) табу программасын жаз:

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

Есептің қойылымы Мына есепті қарастырайық: екі натурал санның ең үлкен ортақ бөлгішін (ЖБ) анықтау программасын жазу қажет. Математиканы еске түсірейік. Екі натурал санның ең үлкен ортақ бөлгіші - олар біркелкі бөлінетін ең үлкен натурал сан. Мысалы, 12 және 18 сандарының ортақ бөлгіштері бар: 2, 3, 6. Ең үлкен ортақ бөлгіш 6 саны. Ол былай жазылады: gcd(12,18) = 6. Бастапқы деректерді M және N деп белгілеңіз. Мәселе мәлімдемесі келесідей: Берілген: M, N Табыңыз: GCD(M, N).

N, онда GCD(M,N) = GCD(M - N,N). Басқаша айтқанда, екі натурал санның gcd мәні олардың оң айырмасының gcd және кішірек санға тең." title="(!LANG:Алгоритм идеясы Бұл алгоритмнің идеясы мынаған негізделген: қасиеті, егер M>N болса, онда gcd(M,N) = gcd( M - N, N) Басқаша айтқанда, екі натурал санның gcd олардың оң айырмасының gcd және кіші санға тең." class="link_thumb"> 4 !}Алгоритм идеясы Бұл алгоритм идеясы егер M>N болса, онда GCD(M,N) = GCD(M - N,N) қасиетіне негізделген. Басқаша айтқанда, екі натурал санның gcd мәні олардың оң айырмасының және кіші санның gcd-іне тең. N, онда GCD(M,N) = GCD(M - N,N). Басқаша айтқанда, екі натурал санның gcd мәні олардың оң айырмасының gcd және кіші санға тең."> N, онда gcd(M,N) = gcd(M - N,N). Басқаша айтқанда, Екі натурал санның gcd мәні олардың оң айырмасының және кіші санның gcd-іне тең."> N, онда GCD(M,N) = GCD(M - N,N). Басқаша айтқанда, екі натурал санның gcd мәні олардың оң айырмасының gcd және кішірек санға тең." title="(!LANG:Алгоритм идеясы Бұл алгоритмнің идеясы мынаған негізделген: қасиеті, егер M>N болса, онда gcd(M,N) = gcd( M - N, N) Басқаша айтқанда, екі натурал санның gcd олардың оң айырмасының және кіші санның gcd-ге тең."> title="Алгоритм идеясы Бұл алгоритм идеясы егер M>N болса, онда GCD(M,N) = GCD(M - N,N) қасиетіне негізделген. Басқаша айтқанда, екі натурал санның gcd мәні олардың оң айырмасының және кіші санның gcd-іне тең."> !}

N). Бұл M = mK, N = pK дегенді білдіреді, мұндағы m, n - натурал сандар және m>n. Сонда M - N = K(m - n), бұл K-ның M - N-нің бөлгіші екенін білдіреді. Демек, M және N-нің барлық ортақ бөлгіштері бөлгіштер" title="(!LANG:Дәлелдеу K ортақ бөлгіш болсын. M және N (M > N).Бұл M = mK, N = pK дегенді білдіреді, мұндағы m, n - натурал сандар және m> n. Сонда M - N = K(m - n), қайдан шығады K - M санының бөлгіші - N. Демек, M және N сандарының барлық ортақ бөлгіштері бөлгіштер." class="link_thumb"> 5 !}Дәлелдеу K мен M санының ортақ бөлгіші болсын. N (M>N). Бұл M = mK, N = pK дегенді білдіреді, мұндағы m, n - натурал сандар және m>n. Сонда M - N = K(m - n), бұдан K санының M - N санының бөлгіші екендігі шығады. Демек, M және N сандарының барлық ортақ бөлгіштері олардың M - N айырмасының, соның ішінде ең үлкенінің бөлгіштері болып табылады. ортақ бөлгіш. Демек: GCD(M,N) = GCD(M - N,N). Екінші айқын қасиет: GCD(M,M) = M. N). Бұл M = mK, N = pK дегенді білдіреді, мұндағы m, n - натурал сандар және m>n. Содан кейін M - N \u003d K (m - n), осыдан K - M санының бөлгіші - N. Демек, M және N сандарының барлық ортақ бөлгіштері бөлгіш болып табылады "\u003e N). Бұл дегеніміз M \u003d mK, N \u003d pK , мұндағы m, n - натурал сандар және m > n. Сонда M - N = K(m - n), осыдан K - M - N санының бөлгіші екендігі шығады. Демек, M және N сандарының барлық ортақ бөлгіштері олардың айырмасының M-N бөлгіштері, соның ішінде ең үлкен ортақ бөлгіш.Осыдан: GCD(M, N) = GCD(M - N, N).Екінші айқын қасиет: GCD(M) , M) = M."> N). Бұл M = mK, N = pK дегенді білдіреді, мұндағы m, n - натурал сандар және m>n. Сонда M - N = K(m - n), бұл K-ның M - N-нің бөлгіші екенін білдіреді. Демек, M және N-ның барлық ортақ бөлгіштері бөлгіштер" title="(!LANG:Дәлелдеу K ортақ бөлгіш болсын. М және N (M > N).Бұл M = mK, N = pK дегенді білдіреді, мұндағы m, n - натурал сандар және m> n. Сонда M - N = K(m - n), қайдан шығады K - M санының бөлгіші - N. Демек, M және N сандарының барлық ортақ бөлгіштері бөлгіштер."> title="Дәлелдеу K мен M санының ортақ бөлгіші болсын. N (M>N). Бұл M = mK, N = pK дегенді білдіреді, мұндағы m, n - натурал сандар және m>n. Сонда M - N \u003d K (m - n), бұл K санының M - N санының бөлгіші екенін білдіреді. Демек, M және N сандарының барлық ортақ бөлгіштері бөлгіштер болып табылады."> !}

Паскаль тіліндегі бағдарлама Evklid; var M, N: бүтін; begin writeln («M және N енгізіңіз»); readln(M,N); ал MN басталады, егер M>N болса, M:=M-N басқа N:=N-M аяқталады; жазу("HOD=",M) соңы. N онда M:=M-N басқа N:=N-M соңы; write("HOD=",M) end."> N содан кейін M:=M-N басқа N:=N-M соңы; write("HOD=",M) соңы."> N содан кейін M:=M-N басқа N:=N-M Соңы; write("HOD=",M) end." title="(!LANG: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 онда M:=M-N басқа N:=N-M соңы; write("HOD=",M) end." title="(!LANG: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."> !}

слайд 1

слайд 2

ЕВКЛИД АЛГОРИТМІ Евклид алгоритмі – екі теріс емес бүтін санның ең үлкен ортақ бөлгішін (gcd) табуға арналған алгоритм. Евклид (б.з.д. 365-300 жж.) Ежелгі грек математиктері бұл алгоритмді ἀνθυφαίρεσις немесе ἀνταναίρεσις – «өзара алу» деп атаған.

слайд 3

Есептеу GCD GCD = екі натурал санның ең үлкен ортақ бөлгіші бастапқы екі сан да қалдықсыз бөлінетін ең үлкен сан. gcd(a, b)= gcd(a-b, b)= gcd(a, b-a) Екі санның үлкенін үлкені мен кішісінің айырмасымен олар тең болғанша ауыстыр. Бұл NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27)=gcd(18, 9) ==gcd(9,9)=9 Мысал:

слайд 4

STEP операция M N Шарт 1 InputM 48 2 InputN 18 3 M N 48 18, иә 4 M>N 48>18, иә 5 M:=M-N 30 6 M N 30 18, иә 7 M>N 30>18, иә 8 M:= M-N 12 9 M N 12 18 иә 10 M>N 12>18 жоқ 11 N:=N-M 6 12 M N 12 6 иә 13 M>N 12>6 иә 14 M:=M-N 6 15 M N 6 6 жоқ 16 ҚорытындыМ

слайд 5

Evklid бағдарламасы; var m, n: бүтін; begin writeln("2 санды толтырды"); readln(m,n); while mn do begin if m>n болса, m:=m-n else n:=n-m; Соңы; write("nod=",m); readln end.

слайд 6

0.Компьютерде Evklid бағдарламасын іске қосыңыз. Оны M=32, N=24 арқылы тексеріңіз; M=696, N=234. 1. Берілген екі санның қос жай екенін тексеріңіз. Ескерту. Екі сан салыстырмалы жай деп аталады, егер олардың ең үлкен ортақ бөлгіші 1 болса. 2. LCM(n, m) = n * m / gcd(n, m) болса, n және m сандарының ең кіші ортақ еселігін (LCM) табыңыз. 3. m және n натурал сандары берілген. p / q = m / n болатындай ортақ бөлгіштері жоқ p және q натурал сандарын табыңыз. 4. Үш санның GCD-ін табыңыз. Ескерту. gcd(a, b, c)= gcd(gcd(a, b), c) Тапсырмалар

Слайд 7

Евклид, ежелгі грек математигі. 3 ғасырда Александрияда жұмыс істеді. BC e. Ежелгі математика негіздерін, элементар геометрияны, сандар теориясын, қатынастардың жалпы теориясын және шекаралар теориясының элементтерін қамтитын аудандар мен көлемдерді анықтау әдістемесін қамтитын негізгі еңбек «Бастаулар» (15 кітап). Математиканың дамуына зор ықпал етті. Астрономия, оптика, музыка теориясы бойынша жұмыс істейді.