Конспект та презентація уроку алгоритм евкліда для знаходження нід. Презентація на тему "Алгоритм Евкліда" Тема: Алгоритм Евкліда для знаходження НОД

Щоб користуватися попереднім переглядом презентацій, створіть собі обліковий запис Google і увійдіть до нього: https://accounts.google.com

Підписи до слайдів:

АЛГОРИТМ ЕВКЛІДА, давньогрецький математик. Працював в Олександрії у 3 ст. до зв. е. Головна праця "Початку" (15 книг), що містить основи античної математики, елементарної геометрії, теорії чисел, загальної теорії відносин та методу визначення площ та обсягів, що включав елементи теорії меж. Вплинув на розвиток математики. Роботи з астрономії, оптики, теорії музики. Евклід (365-300 до. н. е.)

Алгоритм Евкліда Алгоритм Евкліда - це алгоритм знаходження найбільшого загального дільника (НД) двох цілих невід'ємних чисел. Евклід (365-300 до. н. е.) Давньогрецькі математики називали цей алгоритм ἀνθυφαίρεσις або ἀνταναίρεσις - «взаємне віднімання».

Обчислення НОД НОД = найбільший загальний дільник двох натуральних чисел - це найбільше число, на яке обидва вихідні числа діляться без залишку. НОД(a , b)= НОД(a-b, b)= НОД(a, b-a) Замінюємо більше двох чисел різницею більшого і меншого до того часу, що вони стануть рівні. Це і є НОД. НОД (18 , 45) = НОД (18 , 45-18) = НОД (18 , 27) = НОД (18 , 9) = = НОД (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 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

program Evklid; var m, n: integer; begin writeln ("vved 2 chisla"); readln (m, n); while mn do begin якщо m>n then m:=m-n else n:= n-m ; end; write ("nod=",m); readln end.

0. Виконайте на комп'ютері програму Evklid. Протестуйте її при значеннях М = 32, N = 24; M = 696, N = 234. 1 . Перевірити, чи два дані числа взаємно простими. Примітка. Два числа називаються взаємно простими, якщо їхній найбільший спільний дільник дорівнює 1. 2 . Знайти найменше загальне кратне (НОК) чисел n і m, якщо НОК(n, m) = n * m / НОД (n, m). 3 . Дано натуральні числа m і n. Знайти такі натуральні p і q, що не мають спільних дільників, що p/q = m/n. 4. Знайти НОД трьох чисел. Примітка. НОД(a , b , c)= НОД(НОД(a , b), c) Завдання

Попередній перегляд:

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

Цілі уроку:

1. Освітні:

1. навчитися застосовувати алгоритм Евкліда для знаходження НОД двох та трьох чисел
2. закріпити навички щодо використання алгоритмічних структур «Розгалуження» та «Цикл»
3. отримати досвід написання та налагодження програм мовою програмування Паскаль

1. Виховна:

1. формування самостійності та відповідальності щодо нового матеріалу

1. Розвиваюча:

1. розвиток уваги та аналітичного мислення

План уроку:

1. Організаційний момент
2. Актуалізація знань
3. Пояснення нової теми
4. Практична частина
5. Підбиття підсумків уроку
6. Домашнє завдання.

Організаційний момент

Вітання. Хто відсутній. Число. Тема урока. Питання щодо домашнього завдання.

Актуалізація знань.

Запитання:

Які типи алгоритмічних структур ви знаєте?

Яка структура називається лінійною? (Бл-сх)

Яка структура називається такою, що розгалужується? (Бл-сх)

Яка структура називається циклічною? (Бл-сх)

Які види циклів ви знаєте?

Як реалізується мовою програмування Паскаль цикл із відомим числом повторень?

Як реалізується мовою програмування Паскаль цикл із невідомим числом повторень?

Пояснення нової теми (презентація)

Про Евкліда;

Ідея алгоритму Евкліда

Ідея цього алгоритму заснована на:

1. Властивість, що й M>N, то НОД(М, N) = НОД(М - N, N).

Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їхньої позитивної різниці (модуля їхньої різниці) і меншого числа.

Доведення: нехай До - спільний дільник М та N (M> N). Це означає, що М = mК, N = nК, де m, n – натуральні числа, причому m > n. Тоді М - N = К(m - n), звідки випливає, що К - дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками їхньої різниці М - N, у тому числі і найбільший спільний дільник.

2.Друга очевидна властивість:

НОД(М, М) = М.

Для "ручного" рахунку алгоритм Евкліда виглядає так:

1) якщо числа рівні, то взяти будь-яке з них як відповідь, інакше продовжити виконання алгоритму;

2) замінити більшу кількість різницею більшого та меншого з чисел;

3) повернутись до виконання п. 1.

Блок-схема алгоритму Евкліда

Програма на ЯП Паскаль

program Evklid;

var m, n: integer;

begin

writeln ("vved 2 chisla");

readln (m, n);

While mn do

Begin

If m>n

Then m:=m-n

Else n:=n-m;

End;

Write ("nod =", m);

readln

end.

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

Запитання та завдання:

1. Виконайте на комп'ютері програму Evklid. Протестуйте її на значеннях М = 32, N = 24; М=696, N=234.
2. Перевірити, чи два дані числа взаємно простими. Примітка. Два числа називаються взаємно простими, якщо найбільший загальний дільник дорівнює 1.

Підбиття підсумків уроку

Сьогодні на уроці ми познайомилися з алгоритмом Евкліда, що дозволяє знаходити НОД двох цілих невід'ємних чисел, написали програму мовою програмування Паскаль, що реалізує цей алгоритм. На будинок ви отримаєте завдання, в якому ви застосовуватимете даний алгоритм для знаходження НОД трьох чисел та НОК двох чисел.

Домашнє завдання.

1. Складіть програму знаходження найбільшого загального дільника трьох чисел, використовуючи таку формулу:

НОД(А, В, С) = НОД(НД(А, В), С)

2.Складіть програму знаходження найменшого загального кратного (НОК) двох чисел, використовуючи формулу:

А  В = НОД(А, В)  НОК(А, В)

Cлайд 1

Cлайд 2

Cлайд 3

Cлайд 4

Cлайд 5

Cлайд 6

Cлайд 7

Слайд 2

Алгоритм Евкліда - це алгоритм знаходження найбільшого загального дільника (НД) двох цілих невід'ємних чисел. Евклід (365-300 до. н. е.) Давньогрецькі математики називали цей алгоритм ἀνθυφαίρεσις або ἀνταναίρεσις - «взаємне віднімання».

Слайд 3

Обчислення НОД

НОД = найбільший загальний дільник двох натуральних чисел - це найбільше число, на яке обидва вихідні числа діляться без залишку. НОД(a,b)= НОД(a-b, b)= НОД(a, b-a) Замінюємо більше двох чисел різницею більшого і меншого до того часу, що вони стануть рівні. Це і є НОД. НОД (18, 45) = НОД (18, 45-18) = НОД (18, 27) = НОД (18, 9) = = НОД (9,9) = 9 Приклад:

Слайд 4

Слайд 5

program Evklid; var m, n: integer; begin writeln ("vved 2 chisla"); readln (m, n); while mn do begin якщо m>n then m:=m-n else n:=n-m; end; write ("nod=",m); readln end.

Слайд 6

0.Виконайте на комп'ютері програму Evklid. Протестуйте її при значеннях М = 32, N = 24; M = 696, N = 234. 1. Перевірити, чи два дані числа взаємно простими. Примітка. Два числа називаються взаємно простими, якщо їх найбільший спільний дільник дорівнює 1. 2. Знайти найменше загальне кратне (НОК) чисел n і m, якщо НОК(n, m) = n * m / НОД (n, m). 3. Дані натуральні числа m та n. Знайти такі натуральні p і q, що не мають спільних дільників, що p/q = m/n. 4. Знайти НОД трьох чисел. Примітка. НОД (a, b, c) = НОД (НОД (a, b), c) Завдання

Слайд 7

ЕВКЛІД, давньогрецький математик. Працював в Олександрії у 3 ст. до зв. е. Головна праця "Початку" (15 книг), що містить основи античної математики, елементарної геометрії, теорії чисел, загальної теорії відносин та методу визначення площ та обсягів, що включав елементи теорії меж. Вплинув на розвиток математики. Роботи з астрономії, оптики, теорії музики.

Переглянути всі слайди

Постановка Завдання Розглянемо таку задачу: потрібно скласти програму визначення найбільшого загального дільника (НД) двох натуральних чисел. Згадаймо математику. Найбільший спільний дільник двох натуральних чисел – це найбільше натуральне число, на яке вони діляться націло. Наприклад, у чисел 12 та 18 є спільні дільники: 2, 3, 6. Найбільшим загальним дільником є ​​число 6. Це записується так: НОД(12,18) = 6. Позначимо вихідні дані як М та N. Постановка задачі виглядає наступним чином : Дано: М, N Знайти: НОД(М, N).

N, то НОД (М, N) = НОД (М - N, N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці і меншого числа." М - N, N) Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці та меншого числа." class="link_thumb"> 4 !}Ідея алгоритму Ідея цього алгоритму полягає в тому властивості, що й M>N, то НОД(М,N) = НОД(М - N,N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їхньої позитивної різниці та меншого числа. N, то НОД (М, N) = НОД (М - N, N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці і меншого числа."> N, то НОД(М,N) = НОД(М - N,N). меншого числа."> N, то НОД(М,N) = НОД(М - N,N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці і меншого числа." М - N, N) Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їх позитивної різниці та меншого числа."> title="Ідея алгоритму Ідея цього алгоритму полягає в тому властивості, що й M>N, то НОД(М,N) = НОД(М - N,N). Інакше кажучи, НОД двох натуральних чисел дорівнює НОД їхньої позитивної різниці та меншого числа."> !}

N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки випливає, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками" title="(!LANG:Доказ Нехай До спільний дільник М і.) N (M>N) Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т> п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками" class="link_thumb"> 5 !}Доказ Нехай До спільного дільника М і. N (M>N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки випливає, що К дільник числа М - N. Отже, всі загальні дільники чисел М і N є дільниками їх різниці M-N, у тому числі й найбільший спільний дільник. Звідси: НОД (М, N) = НОД (М - N, N). Друга очевидна властивість: НОД(М, М) = М. N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі загальні дільники чисел М і N є дільниками"> N). Це означає, що М = тК, N = пК , де т, п натуральні числа, причому т> п. Тоді М - N = К (т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками їх різниці M-N, у тому числі і найбільший спільний дільник.Звідси: НОД(М, N) = НОД(М - N,N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки випливає, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками" title="(!LANG:Доказ Нехай До спільний дільник М і.) N (M>N) Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т> п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками"> title="Доказ Нехай До спільного дільника М і. N (M>N). Це означає, що М = тК, N = пК, де т, п натуральні числа, причому т>п. Тоді М - N = К(т - п), звідки слідує, що К дільник числа М - N. Отже, всі спільні дільники чисел М і N є дільниками"> !}

Програма мовою Паскаль Program Evklid; var М, 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 then M:=M-N else N:=N-M end; write("HOD=",M) end."> N then M:=M-N else N:=N-M end; write("HOD=",M) end."> N then M:=M-N else N:=N-M end; write("HOD=",M) end." title="(!LANG:Програма мовою Паскаль Program Evklid; var М, 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 then M:=M-N else N:=N-M end; write("HOD=",M) end." title="(!LANG:Програма мовою Паскаль Program Evklid; var М, 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."> !}