Презентација за окупацијата на кругот Евклидов алгоритам. Презентација на тема „Евклидовиот алгоритам“. Идејата за Евклидовиот алгоритам

Класа: 6

Цели на лекцијата:

поправете го алгоритмот за наоѓање на најголемиот заеднички делител со помош на раздвојување;
повторување поврзани дефиниции и концепти;
да ги запознае учениците со Евклидовиот алгоритам;
да се формираат вештините на математичката култура

Опрема: компјутер, проектор, екран.

За време на часовите

1. Организациски момент (проверка на подготвеноста на учениците за часот, означување отсутни) (1 мин)

2. Усна работа: (6 мин.)

1. Заменете го производот со степен:

г) a * a * a * a * a

Пресметај: 2 3 ; 52; 3 3 ; 10 4 .
Најдете ја вредноста на изразот: (3?3?5?11): (3?11). Каков заклучок може да се извлече?
Изведете поделба ана бако a=170, b=35. Запишете ја еднаквоста, што е еднакво на a.

Напиши ја оваа еднаквост во општа форма: a ќе биде делив, а b ќе биде делител. Нека количникот е q, а остатокот r, тогаш: a = bq + r , а q може да биде или природен број или нула. Дали r може да биде кој било број? [ r е природен број, а 0 < r < b .] Што може да се каже за броевите a и b ако r = 0? Целобројното делење е посебен случај на делење со остаток.

Откријте и објаснете дали бројот a е делив со бројот 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) Пресметајте го GCD на броевите 24 и 16.

3) Факторизирајте ги броевите: 875 и 8000 и пресметајте го GCD на овие броеви.

(Користејќи го бројот 8000 како пример, повторете поедноставен начин на факторингирање броеви кои завршуваат на нули: бидејќи 10=2 *5, потоа 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 *5 3)

4) Дали GCD на три броја може да биде еднаков на 15 ако нивниот производ е еднаков на 3000? [ бр, како

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; и обратно, ако c е произволен заеднички делител на b и r, тогаш a е делив со c. Односно, сите заеднички делители на паровите (a; b) и (b; r) се совпаѓаат, па оттука и нивните најголеми заеднички делители се совпаѓаат.

Погодноста на Евклидовиот алгоритам станува особено забележлива ако ја примениме формата на ознаката во форма на табела:

Во овој таблет прво се запишуваат оригиналните броеви, поделени во умот, запишувајќи ги останатите десно, а приватните на дното, додека не заврши процесот. Последниот делител е GCD.

Така, најголемиот заеднички делител на два броја е последниот, не еднаков на 0, остаток кога се дели поголем број со помал, т.е. ако a = b*q + r, потоа gcd(a; b) = gcd(b; r)

Оваа низа на операции се нарекува Евклидовиот алгоритам. Овој алгоритам ви овозможува да го пронајдете GCD на броеви без нивно факторингирање (Додаток, слајд 5)

6. Вежби (10 мин.)

1. Препорачливо е да се разгледа пример. Нека биде неопходно да се најде GCD на броевите 323 и 437. Не е лесно да се направи тоа со избор или распаѓање на прости множители, бидејќи ниту еден од овие броеви не е множител на 2, 3, 5, 7, 11. Ние постапи на следниов начин (

Тема: Евклидовиот алгоритам за пронаоѓање на ГЦД.

Цели:повторете ги претходно проучуваните теми Најголем заеднички делител и најмало заедничко повеќекратно, воведете го Евклидовиот алгоритам.

Цели на учењето - да се повторат поимите за најголем заеднички делител и најмал заеднички множител, правило за нивно наоѓање. Вовед во Евклидовиот алгоритам. Поправете го Евклидовиот алгоритам со решавање на соодветните задачи.

Развојни задачи - развој на логично размислување, внимание, меморија на говорот, способност за самостојно откривање на нови знаења, математичка љубопитност, когнитивен интерес за предметот.

Задачите на образованието се да негува култура на математичко размислување, меѓусебно помагање, самоиспитување и анализа на сопствените грешки.

Работете на картички

Најдете ги GCD или LCM броевите и дешифрирајте ја фразата:

300

D: GCD (33,88)

H: NOC (9,40)

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

М: НОК (25.12)

Т: NOC (4,8,16)

H: NOC (12.40)

B: GCD (18,35)

О: GCD (17.34)

I: gcd (102,68)

E: GCD (18,12)

Во последната табела запишете ги преостанатите парови броеви

Одговори:

300

НО

До

НО

D: GCD (33,88) = 11

G: LCM (9,40) = 360

О: LCM (14,42) = 42

E: GCD(48,18)=6

P: LCM (17,5) = 85

C: GCD(48,24)=24

К: ГЦД (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

Б: gcd (18,35) = 1

О: GCD (17,34) = 17

И: GCD(102,68)=34

Е: GCD(18,12)=6

Погодете уште 2 збора

Што може да се каже за бројките во последната табела? Тие се coprime, т.е. ако ги разложиме овие броеви на прости множители, тогаш тие нема да ги имаат истите множители. Како да се најде GCD на таквите броеви? Климање на таквите броеви =1. И како да го пронајдете LCM, за да го најдете LCM, треба да ги помножите овие броеви еден со друг.

Во првата колона се парови на броеви, во кои еден од нив не е делив со другиот целосно. Оние. остатокот не е 0.

Како ги најдовте GCD и LCM на таквите броеви. (Со разложување на овие броеви на прости множители)

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

Потсетете се на правилото за наоѓање GCD и LCM, пронајдете ја и проверете ја формулата LCM (a, b) \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

Знаејќи го GCD на броевите 48 и 18, пронајдете го NOC. 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; Б) 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

Наслов на слајдови:

Евклидовиот алгоритам Евклид, старогрчки математичар. Работел во Александрија во III век. п.н.е д. Главното дело „Почетоци“ (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 >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 Излез М

програма Евклид ; var m, n: цел број; започнете да пишувате ("vved 2 chisla"); readln(m,n); додека mn почнуваат ако m>n тогаш m:=m-n друго n:= n-m ; крај; write("nod=",m); читај на крај.

0. Стартувај ја програмата Evklid на компјутерот. Тестирајте го со М=32, N=24; М=696, N=234. еден . Проверете дали два дадени броеви се сопрости. Забелешка. За два броја се вели дека се сопрости ако нивниот најголем заеднички делител е 1. 2 . Најдете го најмалиот заеднички множител (LCM) на броевите n и m ако LCM(n, m) = n * m / gcd(n, m). 3 . Дадени се природните броеви m и n. Најдете ги природните броеви p и q кои немаат заеднички делители така што p/q = m/n. 4. Најдете го GCD од три броја. Забелешка. GCD(a, b, c)= GCD(gcd(a, b), c) Задачи

Преглед:

Тема: „Евклидовиот алгоритам“

Цели на лекцијата:

Образовни:

Научете како да го користите Евклидовиот алгоритам за да го пронајдете gcd на два и три броја
консолидирајте ги вештините за користење на алгоритамските структури „Разгранување“ и „Циклус“
стекнете искуство во пишување и дебагирање програми на програмскиот јазик Pascal

Образовни:

формирање на независност и одговорност во изучувањето на новиот материјал

Развивање:

развој на внимание и аналитичко размислување

План за лекција:

Време на организирање
Ажурирање на знаењето
Објаснување на новата тема
Практичен дел
Сумирајќи ја лекцијата
Домашна работа.

Време на организирање

поздрав. Кој е отсутен. Број. Тема на лекцијата. Прашања за домашна работа.

Ажурирање на знаењето.

Прашања:

Какви видови алгоритамски структури знаете?

Што е линеарна структура? (Bl-sh)

Што е разгранувачка структура? (Bl-sh)

Што е циклична структура? (Bl-sh)

Какви видови циклуси знаете?

Како се спроведува циклус со познат број повторувања во програмскиот јазик Pascal?

Како се спроведува циклус со непознат број повторувања во програмскиот јазик Pascal?

Објаснување на нова тема (презентација)

За Евклид;

Идејата за Евклидовиот алгоритам

Идејата на овој алгоритам се заснова на:

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

програма Евклид;

var m, n: цел број;

започне

writeln ("vved 2 броеви");

readln(m,n);

Додека мн прават

Започнете

Ако m>n

Тогаш m:=m-n

Друго n:=n-m;

крај;

Write("nod=",m);

читај

крај.

Практичен дел

Прашања и задачи:

Извршете ја програмата Evklid на вашиот компјутер. Тестирајте го на M=32, N=24; M = 696, N = 234.
Проверете дали два дадени броеви се сопрости. Забелешка. За два броја се вели дека се сопрости ако нивниот најголем заеднички делител е 1.

Сумирајќи ја лекцијата

Денес на лекцијата се запознавме со Евклидовиот алгоритам, кој ни овозможува да го најдеме GCD на два ненегативни цели броеви, напишавме програма во програмскиот јазик Pascal кој го имплементира овој алгоритам. Дома, ќе добиете задача во која ќе го примените овој алгоритам за да го пронајдете GCD на три броја и LCM на два броја.

Домашна работа.

1. Напишете програма за наоѓање на најголемиот заеднички делител на три броја користејќи ја следната формула:

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

2. Напишете програма за наоѓање на најмал заеднички множител (LCM) од два броја со помош на формулата:

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

Изјавување на проблемот Разгледајте го следниот проблем: потребно е да се напише програма за определување на најголемиот заеднички делител (GCD) на два природни броја. Да се потсетиме на математиката. Најголемиот заеднички делител на два природни броја е најголемиот природен број со кој тие се рамномерно деливи. На пример, броевите 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 е заеднички делител на М и. 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 = 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 се делители"> title="Доказ Нека K е заеднички делител на М и. N (M>N). Ова значи дека M = mK, N = pK, каде што m, n се природни броеви и m>n. Потоа M - N \u003d K (m - n), што имплицира дека K е делител на бројот M - N. Оттука, сите заеднички делители на броевите M и N се делители"> !}

Програма во Паскал програма Евклид; var M, N: цел број; започнете со пишување („Внесете M и N“); readln(M,N); додека MN почнуваат ако M>N тогаш M:=M-N друго N:=N-M крај; write("HOD=",M) крај. N потоа M:=M-N друго N:=N-M крај; write("HOD=",M) end."> N потоа M:=M-N друго N:=N-M крај; write("HOD=",M) end."> N потоа M:=M-N друго N:=N-M крај; write("HOD=",M) end." title="(!LANG:Pascal програма програма Evklid; var M, N: integer; start 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 програма програма Evklid; var M, N: integer; start 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

слајд 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

ЧЕКОР Операција M N Состојба 1 ВлезМ 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 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 ЗаклучокM

слајд 5

програма Евклид; var m, n: цел број; започнете со пишување ("введи 2 броеви"); readln(m,n); додека mn почнуваат ако m>n тогаш m:=m-n друго n:=n-m; крај; write("nod=",m); читај на крај.

слајд 6

0. Стартувај ја програмата Evklid на компјутерот. Тестирајте го со М=32, N=24; М=696, N=234. 1. Проверете дали два дадени броја се сопрости. Забелешка. Два броја се нарекуваат релативно прости ако нивниот најголем заеднички делител е 1. 2. Најдете го најмалиот заеднички множител (LCM) на броевите n и m ако LCM(n, m) = n * m / gcd(n, m). 3. Дадени се природните броеви m и n. Најдете ги природните броеви p и q без заеднички делители така што p / q = m / n. 4. Најдете го GCD од три броја. Забелешка. gcd(a, b, c)= gcd(gcd(a, b), c) Задачи

Слајд 7

Евклид, антички грчки математичар. Работел во Александрија во III век. п.н.е д. Главното дело „Почетоци“ (15 книги), кое ги содржи основите на античката математика, елементарната геометрија, теоријата на броеви, општата теорија на односите и методот за определување области и волумени, во кој биле вклучени елементи на теоријата на граници. Имаше големо влијание врз развојот на математиката. Работи на астрономија, оптика, музичка теорија.

Презентација за окупацијата на кругот Евклидов алгоритам. Презентација на тема „Евклидовиот алгоритам“. Идејата за Евклидовиот алгоритам

Наслов на слајдови:

Преглед:

Тема: „Евклидовиот алгоритам“

Време на организирање

Ажурирање на знаењето.