Презентация за заемане на кръга Евклидов алгоритъм. Презентация на тема "Алгоритъм на Евклид". Идея за алгоритъма на Евклид

клас: 6

Цели на урока:

фиксирайте алгоритъма за намиране на най-големия общ делител с помощта на факторизация;
повторете свързани дефиниции и понятия;
запознаване на учениците с алгоритъма на Евклид;
за формиране на умения за математическа култура

Оборудване: компютър, проектор, екран.

По време на занятията

1. Организационен момент (проверка на готовността на учениците за урока, отбелязване на отсъстващи) (1 мин.)

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

1. Заменете продукта със степен:

г) a * a * a * a * a

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

Запишете това равенство в общ вид: a ще се дели, а b ще бъде делител. Нека частното е q и остатъкът r, тогава: a = bq + r , и q може да бъде или естествено число, или нула. Може ли r да бъде произволно число? [ r е естествено число, а 0 < r < b .] Какво може да се каже за числата a и b, ако r = 0? Целочисленото деление е специален случай на деление с остатък.

Разберете и обяснете дали числото a се дели на числото b без остатък, ако:

а) а = 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.

цели:повторете предварително проучените теми Най-голям общ делител и най-малко общо множество, запознайте се с алгоритъма на Евклид.

Учебни цели - да се повторят понятията за най-голям общ делител и най-малко общо кратно, правилото за намирането им. Въведение в алгоритъма на Евклид. Поправете алгоритъма на Евклид, като решите съответните задачи.

Задачи за развитие - развитието на логическото мислене, вниманието, паметта на речта, способността за самостоятелно откриване на нови знания, математическото любопитство, познавателния интерес към предмета.

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

Работете върху карти

Намерете GCD или LCM числа и дешифрирайте фразата:

300

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)

M: NOC (25.12)

T: NOC(4,8,16)

H: NOC (12,40)

B: GCD (18,35)

A: GCD(17.34)

I: gcd (102.68)

E: GCD(18,12)

В последната таблица запишете останалите двойки числа

Отговори:

300

НО

Да се

НО

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

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

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

Познавайки 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

Така най-големият общ делител на две числа е последният ненулев остатък при разделяне на по-голямото число на по-малкото., т.еако 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

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

Алгоритъмът на Евклид Евклид, древногръцки математик. Работил в Александрия през 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) Задачи

Визуализация:

Тема: "Алгоритъмът на Евклид"

Цели на урока:

Образователни:

научете как да използвате алгоритъма на Евклид, за да намерите gcd на две и три числа
затвърдете уменията за използване на алгоритмичните структури "Разклоняване" и "Цикъл"
придобиете опит в писането и отстраняването на грешки в програми на езика за програмиране Pascal

Образователни:

формиране на самостоятелност и отговорност при изучаване на нов материал

Разработване:

развитие на вниманието и аналитичното мислене

План на урока:

Организиране на времето
Актуализация на знанията
Обяснение на новата тема
Практическа част
Обобщаване на урока
Домашна работа.

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

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

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

въпроси:

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

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

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

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

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

Как се реализира цикъл с известен брой повторения в езика за програмиране 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

край.

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

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

Стартирайте програмата Evklid на вашия компютър. Тествайте го на M=32, N=24; М = 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)

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

слайд 1

слайд 2

слайд 3

слайд 4

СТЪПКА Операция 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 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: цяло число; 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 книги), съдържащ основите на древната математика, елементарната геометрия, теорията на числата, общата теория на отношенията и метода за определяне на площи и обеми, който включва елементи от теорията на границите. Той оказа голямо влияние върху развитието на математиката. Работи по астрономия, оптика, теория на музиката.

Презентация за заемане на кръга Евклидов алгоритъм. Презентация на тема "Алгоритъм на Евклид". Идея за алгоритъма на Евклид

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

Визуализация:

Тема: "Алгоритъмът на Евклид"

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

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