Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» icon

Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)»



НазваниеУрок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)»
Дата конвертации07.07.2012
Размер46.33 Kb.
ТипУрок
1. /6-delitel.docУрок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)»

УРОК №6
ТЕМА «Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК)»


Цель урока:

рассмотреть алгоритмы нахождения НОД и НОК двух целых чисел.

Задачи урока:

образовательные:

изучить алгоритмы нахождения НОДа и НОКа двух чисел; реализовать эти алгоритмы на языке программирования; научиться применять этот алгоритм при решении задач;

развивающие:

развитие алгоритмического мышления, способностей к формализации, элементов системного мышления;

воспитательные:

воспитание чувства ответственности за результаты своего труда.

Материалы и оборудование к уроку:

ПК.

Тип урока:

комбинированный.

Форма проведения урока:

беседа.

План урока:

УРОК №6
ТЕМА «Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК)»

1. Поиск НОД

2. Поиск НОК

3. Задачи.


Ход урока:

1. Поиск НОД


Если a и b — два натуральных числа, и если число c таково, что a делится на с и b делится на c, то число c называют общим делителем чисел а и b. Произвольные два числа всегда обладают общим делителем. Таким делителем является число 1. Если других общих делителей нет, то числа а и b называют взаимно простыми.

Число d называют наибольшим общим делителем (НОД) чисел а и b, если 1) d является общим делителем чисел а и b; 2) d делится на любой другой общий делитель. Другими словами, d — наибольший из всех общих делителей чисел а и b.

В курсе математики приводился следующий алгоритм нахождения НОД. Необходимо разложить числа а и b на простые множители и затем выбрать те из них, которые входят и в одно, и в другое разложение. Рассмотрим пример: найти НОД (2520, 2475).

2520 2

1260 2

630 2

315 3

105 3

35 5

7 7

1


2475 3

825 3

275 5

55 5

11 11

1

Общие множители подчеркнуты. НОД(2520, 2475)= 3*3*5=45.

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


Это один из самых древних алгоритмов, он описан еще в «Началах» Евклида.

Прежде чем описать сам алгоритм, укажем несколько свойств НОД, на которые опирается алгоритм Евклида.

Пусть а и b — отличные от нуля натуральные числа, причем a>b, тогда

1) НОД(а, b)=НОД(а-b, b)

2) НОД(а, а)=а

3) НОД(а, 0)=а

Равенства 2) и 3) являются очевидными.

Равенство 1) будет доказано, если мы установим, что множество общих делителей чисел a и b совпадает со множеством общих делителей чисел a-b и b, т. е всякий общий делитель X чисел а и b является делителем чисел a-b и b, и наоборот. Если X—делитель а и b, то a=kX и b=lХ для некоторых k и l. Тогда а-b=(k-l)Х, т. е. X является общим делителем чисел a-b и b. Наоборот, пусть a-b=mХ и b=nХ для некоторых m и n. Складывая эти равенства получаем а=(n+m)X. Таким образом, Х является общим делителем а и b.

Перечисленные равенства подсказывают идею алгоритма нахождения НОД: нужно от большего числа отнимать меньшее до тех пор, пока они не станут равными, после чего НОД найдется по свойству 2).

Пример: НОД(530, 155), а=530, b=155.

а b

530 155

375 155

220 155

65 155

65 90

65 25

40 25

15 25

15 10

5 10

5 5

Алгоритм будет следующим:

нц пока а<>b

если а>b то а:=a-b

иначе b:=b—a

все

кц

NOD:=a

Если проанализировать работу данного алгоритма, то можно заметить, что одно и то же число нужно отнимать несколько раз. Этого можно избежать, если вместо нескольких вычитаний находить остаток от деления большего числа на меньшее (подумайте, почему). В этом случае свойство 1) можно записать в виде НОД(а, b)=НОД(а mod b, b). Для окончания работы алгоритма нужно воспользоваться свойством 3).

Пример: НОД(530, 155), а=530, b=155.

а b

530 155

65 155

65 25

15 25

15 10

5 10

5 0

Алгоритм будет выглядеть следующим образом:

нц пока (а<>0) и (b<>0)

если а>b то a:=mod(a, b) иначе b:=mod(b, a) все

кц

если а=0 то NOD:=b иначе NOD:=a все

2. Поиск НОК


Если а и b - два натуральных числа, и если число с таково, что с делится на а и c делится на b, то число с называют общим кратным чисел а и b. Произвольные два числа всегда обладают общим кратным. Таким кратным является число, равное произведению аb.

Число d называют наименьшим общим кратным (НОК) чисел а и b, если 1) d является общим кратным чисел а и b; 2) на d делится любое другое общее кратное. Другими словами, d—наименьшее из всех общих кратных чисел а и b.

Для нахождения НОК можно воспользоваться алгоритмом, известным из курса математики. Нужно разложить числа а и b на простые множители, а затем из двух разложений выбрать те сомножители, которые входят хотя бы в одно разложение.

Пример: НОК(52, 65)

52 2 65 5

26 2 13 13

13 13 1

1

52=2*2*13; 65=5*13; НОК(52, 65)=2*2*13*5=260. Однако применять такой алгоритм на практике не стоит по описанным выше причинам. Для нахождения НОК можно воспользоваться следующим свойством:

НОК(а, b)=а*b/НОД(а, b) (докажите самостоятельно). Для нахождения НОД следует применять алгоритм Евклида.

3. Задачи.


1. Сократить дробь а/b (а, b — натуральные числа).

Решение:

var a,b,d:word;

function nod(x,y:word):word;

var r:word;

begin

r:=x mod y;

while r<>0 do

begin

x:=y;

y:=r;

r:=x mod y;

end;

nod:=y;

end;


begin

readln(a,b);

d:=nod(a,b);

writeln(a div d,'/',b div d);

end.

2. Даны 4 целых числа а, b, с, d. Написать программу, вычисляющую сумму обыкновенных дробен a/b+c/d в виде х/у.

var a,b,c,d,nd,p,q:integer;

function nod(x,y:word):word;

var r:word;

begin

r:=x mod y;

while r<>0 do

begin

x:=y;

y:=r;

r:=x mod y;

end;

nod:=y;

end;

begin

readln(a,b,c,d);

p:=a*d+b*c;

q:=b*d;

nd:=nod(abs(p),abs(q));

writeln(p div nd,'/',q div nd);

end.

Литература:

  1. Шень А. Программирование: теоремы и задачи. — 2-е изд., испр. и доп. — М.: МЦНМО, 2004. —296 с.: ил.

  2. В.М. Котов, И.А. Волков, А.И. Лапо Методы алгоритмизации. Учебное пособие для 9 класса общеобразовательной школы с углубленным изучение информатики. — Мн. ИГП «Нар. асвета», 1997. — 160 с.: ил.

  3. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. М.: Наука, 1988.



Похожие:

Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconУрок математики 6 класс Никитина Татьяна Ивановна, учитель математики Тема урока: «Наименьшее общее кратное» Цель урока: ввести понятие наименьшего общего кратного
Перечислите методы, которыми мы пользовались раньше для нахождения кратного чисел
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconНаибольший общий делитель. Цели урока
Ввести определение наибольшего общего делителя, определение взаимно простых чисел, показать запись
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconДля нахождения наибольшего общего делителя двух натуральных чисел
Знаком «%» обозначена операция нахождения остатка от деления целых чисел (как в языке «Си»)
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconМинистерство образования Правительства Саратовской области
Новодубровка (далее Учреждение), реализующего образовательные программы начального общего, основного общего, среднего (полного) общего...
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconД. В. Федотов
...
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconМуниципальное задание
Реализация общеобразовательных программ начального общего, основного общего и среднего ( полного) общего образования
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconРуководитель му «цб моу петровского района» Поварова И. В
Моу – сош №1 (далее учреждение), реализующее образовательные программы начального общего, основного общего, среднего (полного) общего...
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconОбщее равновесие тема 13. Анализ общего равновесия и эффективность
Требует дополнительного анализа механизм перераспределения ресурсов между отдельными частями общего рынка и достижения самой высокой...
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» icon«Информатика и икт»
Федеральный компонент государственных образовательных стандартов начального общего, основного общего и среднего (полного) общего...
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconОбщие положения
Невского района Санкт-Петербурга, далее – оу, реализующим основные общеобразовательные программы начального общего, основного общего,...
Урок №6 тема «Поиск наибольшего общего делителя (нод) и наименьшего общего кратного (нок)» iconПравила школьной жизни
Обучающийся имеет право на: получение бесплатного начального общего, основного общего и среднего (полного) общего образования в пределах...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов