Алгоритм Евклида Цель



Скачать 54.98 Kb.
Дата30.11.2012
Размер54.98 Kb.
ТипДокументы

Алгоритм Евклида

Цель:

Виды циклов

[править] Безусловные циклы


Иногда в программах используются циклы, выход из которых не предусмотрен логикой программы. Такие циклы называются безусловными, или бесконечными. Специальных синтаксических средств для создания бесконечных циклов, ввиду их нетипичности, языки программирования не предусматривают, поэтому такие циклы создаются с помощью конструкций, предназначенных для создания обычных (или условных) циклов. Для обеспечения бесконечного повторения проверка условия в таком цикле либо отсутствует (если позволяет синтаксис, как, например, в цикле LOOP…END LOOP языка Ада), либо заменяется константным значением (while true do … в Паскале).

[править] Цикл с предусловием


Цикл с предусловием — цикл, который выполняется пока истинно некоторое условие, указанное перед его началом. Это условие проверяется до выполнения тела цикла, поэтому тело может быть не выполнено ни разу (если условие с самого начала ложно). В большинстве процедурных языков программирования реализуется оператором while, отсюда его второе название — while-цикл. На языке Pascal цикл с предусловием имеет следующий вид:

while <условие> do begin

<тело программы>

end;

Цикл с постусловием


Цикл с постусловием — цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл реализует оператор repeat..until;
Pascal:

repeat

<тело цикла>

until <условие>

Наибольший общий делитель


Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 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

Условие

1

ввод М

32

 

 

2

ввод N

 

24

 

3

M  N

 

 

32  24, да

4

M>N

 

 

32>24, да

5

M:=M-N

8

 

 

6

M  N

 

 

8  24, да

7

M>N

 

 

8>24, нет

8

N:=N-M

 

16

 

9

M  N

 

 

8  16, да

10

M>N

 

 

8>16, нет

11

N:=N-M

 

8

 

12

M  N

 

 

8  8, нет

13

вывод M

8

 

 

14

конец

 

 

 

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

Программа на АЯ и на Паскале


Запишем алгоритм на АЯ и программу на Паскале.

алг Евклид
цел М, N
нач
     вывод " Введите М и N" ввод М, N
     пока М N, повторять
     нц
          если M>N
          то M:=M-N
          иначе N:=N-M
          кв
     кц
     вывод "НОД=",М
кон

Program Evklid;

Uses crt;
var M, N,K: integer;
begin

Clr scr;
     writeln('Введите М и N,K');
     readln(M, N,K);
     while M< >N do
          begin
               if M>N

               then M:=M-N
               else N:=N-M
     end;

while M< >K do
          begin
               if M>K
               then M:=M-K
               else K:=K-M
     end;
          write('Н0Д=',М);

Readln;
end.

Похожие:

Алгоритм Евклида Цель iconПонятие алгоритма
Ом в III веке до нашей эры алгоритм нахождения наибольшего общего де­лителя двух чисел (алгоритм Евклида). Вплоть до начала XX века...
Алгоритм Евклида Цель icon«Циклические алгоритмы. Алгоритм Евклида»
Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (нод) двух целых неотрицательных чисел
Алгоритм Евклида Цель iconТеория чисел
Алгоритм Евклида и его сложность. Теорема Ламе. Расширенный алгоритм Евклида. ([1],, [3],, [2], 3, [4], )
Алгоритм Евклида Цель iconРасширенный алгоритм Евклида
Ля (нод) был открыт древнегреческими математиками и известен как алгоритм “взаимного вычитания”. И хотя упоминание об этом алгоритме...
Алгоритм Евклида Цель iconДата проведения урока Тема урока Содержание темы (перечень того, что изучается) Формы контроля
Алгоритм Евклида (линейное представление нод, критерий взаимной простоты двух чисел). Алгоритм Евклида для определения соизмеримости...
Алгоритм Евклида Цель icon1 Алгоритм Евклида 1 Применение алгоритма Евклида 2 Математическая проблема календаря 2 Анализ алгоритма Евклида 3 Евклидовы кольца 4 Аналоги чисел Фибоначчи Заключение Список использованных источников
Один из героев великого французского писателя Мольера, месье Журден, был страшно удивлён, узнав, что всю жизнь пользуется прозой....
Алгоритм Евклида Цель iconА. В. Устинов 1/2 года Делимость целых чисел. Деление с остатком. Алгоритм Евклида нахождения наибольшего общего делителя. Решение
Делимость целых чисел. Деление с остатком. Алгоритм Евклида нахождения наибольшего общего делителя. Решение линейных уравнений в...
Алгоритм Евклида Цель iconВосстановление информации в задаче разделения секрета для гиперкомплексных числовых систем 2-го порядка с помощью алгоритма Евклида
Рассмотрены примеры восстановления секрета, используя алгоритм Евклида при представлении информации в гиперкомплексных числовых системах...
Алгоритм Евклида Цель iconАлгоритм Евклида и его сложность
Рассмотрим математические вопросы, связанные с шифрами, использующие операции с целыми числами. Обозначим n – множество натуральных...
Алгоритм Евклида Цель iconСистемы с открытым ключом. Алгоритм Евклида и его сложность
Рассмотрим математические вопросы, связанные с шифрами, использующие операции с целыми числами. Обозначим n – множество натуральных...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org