Резюме и представяне на урока Евклидов алгоритъм за намиране на възли. Презентация на тема "Алгоритъм на Евклид" Тема: Алгоритъм на Евклид за намиране на GCD

За да използвате визуализацията на презентации, създайте акаунт (акаунт) в Google и влезте: https://accounts.google.com

Надписи на слайдове:

Алгоритъмът на Евклид Евклид, древногръцки математик. Работил в Александрия през 3 век. пр.н.е д. Основният труд "Начало" (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, да 30 M >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

програма Евклид ; var m, n: цяло число; begin writeln("vved 2 chisla"); readln(m,n); докато mn започва, ако m>n, тогава m:=m-n иначе n:= n-m ; край; напиши("кимване=",m); чети край.

0. Стартирайте програмата Evklid на компютъра. Тествайте го с M=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. Домашна работа.

Организиране на времето

Поздравления. Който отсъства. номер. Тема на урока. Въпроси за домашната работа.

Актуализация на знанията.

въпроси:

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

Какво е линейна структура? (Бл-ш)

Какво е разклонена структура? (Бл-ш)

Какво е циклична структура? (Бл-ш)

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

Как се реализира цикъл с известен брой повторения в езика за програмиране Pascal?

Как се реализира цикъл с неизвестен брой повторения в езика за програмиране Pascal?

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

За Евклид;

Идея за алгоритъма на Евклид

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

1. Свойството, че ако M>N, тогава GCD(M, N) = GCD(M - N, N).

С други думи, gcd на две естествени числа е равен на gcd на тяхната положителна разлика (модула на тяхната разлика) и по-малкото число.

доказателство: нека K е общ делител на M и N (M > N). Това означава, че M = mK, N = 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);

Докато mn правя

Започнете

Ако m>n

Тогава m:=m-n

Иначе n:=n-m;

край;

Напишете("кимване=",m);

readln

край.

Практическа част

Въпроси и задачи:

1. Стартирайте програмата Evklid на вашия компютър. Тествайте го на M=32, N=24; М = 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: цяло число; begin writeln("vved 2 числа"); readln(m,n); докато mn започва, ако m>n, тогава m:=m-n, иначе n:=n-m; край; напиши("кимване=",m); чети край.

слайд 6

0. Стартирайте програмата Evklid на компютъра. Тествайте го с M=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

Евклид, древногръцки математик. Работил в Александрия през 3 век. пр.н.е д. Основният труд "Начало" (15 книги), съдържащ основите на древната математика, елементарната геометрия, теорията на числата, общата теория на отношенията и метода за определяне на площи и обеми, който включва елементи от теорията на границите. Той оказа голямо влияние върху развитието на математиката. Работи по астрономия, оптика, теория на музиката.

Вижте всички слайдове

Постановка на задачата Помислете за следния проблем: изисква се да се напише програма за определяне на най-големия общ делител (НОД) на две естествени числа. Да си припомним математиката. Най-големият общ делител на две естествени числа е най-голямото естествено число, на което те се делят равномерно. Например числата 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 на тяхната положителна разлика и по-малкото число."> !}

Н). Това означава, че 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. Н). Това означава, че M = mK, N = pK, където m, n са естествени числа и m>n. Тогава M - N \u003d K (m - n), откъдето следва, че K е делител на числото M - N. Следователно всички общи делители на числата M и N са делители "\u003e 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 = 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 е общ делител на M и. N (M>N). Това означава, че M = mK, N = pK, където m, n са естествени числа и m>n. Тогава M - N \u003d K (m - n), което означава, че K е делител на числото M - N. Следователно всички общи делители на числата M и N са делители"> !}

Програма на Pascal Програма Evklid; var M, N: цяло число; begin writeln("Въведете 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) край."> N след това M:=M-N друго N:=N-M край; write("HOD=",M) end." title="(!LANG: програма Pascal Program Evklid; var M, N: цяло число; начало 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: цяло число; начало 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."> !}