Читайте также: |
|
В» класс. Изучить методический материал, разработать алгоритм Евклида в виде блок-схемы и реализовать его в Паскаль. Выполнить задания. (мет. рек. в Приложении 1).
11 класс. Создать презентацию с анимациями на произвольную тему.
Приложение1.
Алгоритм Евклида
Наибольший общий делитель
Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.
Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:
НОД(12, 18) = 6.
Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М, N).
В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.
Идея алгоритма Евклида
Идея этого алгоритма основана на том свойстве, что если M>N, то
НОД(М, N) = НОД(М - N, N).
Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.
Легко доказать это свойство. Пусть К - общий делитель М u N (M> N). Это значит, что М = mК, N = nК, где m, n - натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.
Второе очевидное свойство:
НОД(М, М) = М.
Для "ручного" счета алгоритм Евклида выглядит так:
1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;
2) заменить большее число разностью большего и меньшего из чисел;
3) вернуться к выполнению п. 1.
Рассмотрим этот алгоритм на примере М=32, N=24:
Получили: НОД(32, 24) =НОД(8, 8) = 8, что верно.
Описание алгоритма Евклида блок-схемой
На рис. 3.12 приведена блок-схема алгоритма Евклида.
Рис. 3.12. Блок-схема алгоритма Евклида |
Структура алгоритма - цикл-пока с вложенным ветвлением. Цикл повторяется, пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.
А теперь посмотрите на трассировочную таблицу алгоритма для исходных значений М = 32, N = 24.
Шаг | Операция | M | N | Условие |
ввод М | ||||
ввод N | ||||
M ¹ N | 32 ¹ 24, да | |||
M>N | 32>24, да | |||
M:=M-N | ||||
M ¹ N | 8 ¹ 24, да | |||
M>N | 8>24, нет | |||
N:=N-M | ||||
M ¹ N | 8 ¹ 16, да | |||
M>N | 8>16, нет | |||
N:=N-M | ||||
M ¹ N | 8 ¹ 8, нет | |||
вывод M | ||||
конец |
В итоге получился верный результат.
Дата добавления: 2015-10-29; просмотров: 152 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
F Неподеленная пара | | | How the city hurts your brain |