Резиме и презентација на часот Евклидов алгоритам за пронаоѓање јазли. Презентација на тема „Евклидов алгоритам“ Тема: Евклидов алгоритам за пронаоѓање на ГЦД

За да го користите прегледот на презентациите, креирајте сметка на 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) Задачи

Преглед:

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

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

1. Образовни:

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

1. Образовни:

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

1. Развивање:

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

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

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

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

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

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

Прашања:

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

Што е линеарна структура? (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);

читај

крај.

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

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

1. Извршете ја програмата Evklid на вашиот компјутер. Тестирајте го на M=32, N=24; M = 696, N = 234.
2. Проверете дали два дадени броеви се сопрости. Забелешка. За два броја се вели дека се сопрости ако нивниот најголем заеднички делител е 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)

слајд 1

слајд 2

слајд 3

слајд 4

слајд 5

слајд 6

Слајд 7

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

слајд 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 книги), кое ги содржи основите на античката математика, елементарната геометрија, теоријата на броеви, општата теорија на односите и методот за определување области и волумени, во кој биле вклучени елементи на теоријата на граници. Имаше големо влијание врз развојот на математиката. Работи на астрономија, оптика, музичка теорија.

Прикажи ги сите слајдови

Изјавување на проблемот Разгледајте го следниот проблем: потребно е да се напише програма за определување на најголемиот заеднички делител (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."> !}