Протокол работы алгоритма евклида таблица как считать

Обновлено: 24.05.2024

- Что такое факториал и какова его расчетная формула?

- Как работает цикл с предусловием?

Проверка д/з: № 7 к § 12.7

Слайд 8 (При объяснении нового материала используется презентация)

Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.

Пусть M и N одновременно не равные нулю целые неотрицательные числа и пусть M ≥ N . Если M = N , то НОД ( M , M )= M , а если M ≠ N , то для чисел M и N выполняется равенство

НОД (M, N) = НОД ( M-N, N ).

Например, пусть х=12, а у=18.

НОД(12,18) = НОД(12,6) = НОД(6,6).

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

Написать программу нахождения наибольшего общего делителя двух неотрицательных чисел.

Блок-схема алгоритма Евклида ( Слайд 9 )

Для решения данной задачи воспользуемся циклом с предусловием:

Program Evklid;

Var M, N : Integer;

Writeln (' Введите два числа ');

While M<>N do

If M>N Then M:=M – N Else N:=N-M;

Для проверки правильности работы составленного алгоритма, составим трассировочную таблицу алгоритма для исходных данных M =32, N =24

Домашняя работа: вычислить сумму всех положительных целых чисел, не превышающих данного натурального числа N . ( Слайд 10 )

Практическая работа оценивается.

Правильность программ проверим путем тестирования на компьютере.

Практическая работа ( Слайд 10 )

№ 7 – домашнее задание (может быть проверено визуально в рабочих тетрадях)

Выполнить на компьютере программу Evklid . Протестировать ее на значениях

M =32, N =24 (Ответ: 8) ; M =696, N =234 (Ответ: 6) .

Домашнее задание: ( Слайд 11 )

§ 12.6, 12.7 (читать, отвечать на вопросы: №1-6 устно, № 8, 10, 11* письменно)

№ 8 : Дано целое число Х и натуральное N . Составить алгоритм вычисления Х N . Проверить алгоритм трассировкой. Написать программу на Паскале.

№ 10 : Составить программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:

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

№ 11 *: Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

А×В = НОД(А,В) × НОК(А,В).

* - дополнительное задание, не являющееся обязательным.


Полный текст материала Циклические алгоритмы. Алгоритм Евклида. смотрите в скачиваемом файле.
На странице приведен фрагмент.

Спасибо за Вашу оценку. Если хотите, чтобы Ваше имя
стало известно автору, войдите на сайт как пользователь
и нажмите Спасибо еще раз. Ваше имя появится на этой стрнице.


Есть мнение?
Оставьте комментарий

Упражнения на технику чтения и понимания прочитанного

Тонкости и секреты работы в Яндекс.Почте

Как работать с детьми с СДВГ в обычном классе?

1 Спам

0 Спам

Отправляя материал на сайт, автор безвозмездно, без требования авторского вознаграждения, передает редакции права на использование материалов в коммерческих или некоммерческих целях, в частности, право на воспроизведение, публичный показ, перевод и переработку произведения, доведение до всеобщего сведения — в соотв. с ГК РФ. (ст. 1270 и др.). См. также Правила публикации конкретного типа материала. Мнение редакции может не совпадать с точкой зрения авторов.

Для подтверждения подлинности выданных сайтом документов сделайте запрос в редакцию.

О работе с сайтом

Мы используем cookie.

Публикуя материалы на сайте (комментарии, статьи, разработки и др.), пользователи берут на себя всю ответственность за содержание материалов и разрешение любых спорных вопросов с третьми лицами.

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

Если вы обнаружили, что на нашем сайте незаконно используются материалы, сообщите администратору — материалы будут удалены.

Расширенный алгоритм Евклида может вычислить НОД (a, b) и в то же самое время вычислить значения s и t . Алгоритм и процесс такого вычисления показан на рис. 2.8.

Здесь расширенный алгоритм Евклида использует те же самые шаги, что и простой алгоритм Евклида . Однако в каждом шаге мы применяем три группы вычислений вместо одной. Алгоритм использует три набора переменных: r , s и t .

На каждом шаге переменные r1 , r2 и r используются так же, как в алгоритме Евклида. Переменным r1 и r2 присваиваются начальные значения a и b соответственно. Переменным s1 и s2 присваиваются начальные значения 1 и 0 соответственно. Переменным t1 и t2 присваиваются начальные значения 0 и 1 , соответственно. Вычисления r , s и t одинаковы, но с одним отличием. Хотя r — остаток от деления r1 на r2 , такого соответствия в других двух группах вычислений нет. Есть только одно частное, q , которое вычисляется как r1/r2 и используется для других двух вычислений.

Дано a = 161 и b = 28 , надо найти НОД (a, b) и значения s и t .

Для отображения алгоритма мы используем следующую таблицу:

Мы получаем НОД (161, 28) = 7 , s = –1 и t = 6 . Ответы могут быть проверены, как это показано ниже.

Дано a = 17 и b = 0 , найти НОД (a, b) и значения s и t .

Для отображения алгоритма мы используем таблицу.

Обратите внимание, что нам не надо вычислять q , r и s . Первое значение r2 соответствует условию завершения алгоритма. Мы получаем НОД (17, 0) = 17 , s = 1 и t = 0 . Это показывает, почему мы должны придавать начальные значения s1 — 1 и t1 — 0 . Ответы могут быть проверены так, как это показано ниже:

Даны a = 0 и b = 45 , найти НОД (a, b) и значения s и t .

Для отображения алгоритма мы используем следующую таблицу:

Мы получаем НОД (0,45) = 45 , s = 0 и t = 1 . Отсюда ясно, что мы должны инициализировать s2 равным 0 , а t2 — равным 1 . Ответ может быть проверен, как это показано ниже:

Линейные диофантовы уравнения

Хотя очень важное приложение расширенного алгоритма Евклида будет рассмотрено далее, здесь мы остановимся на другом приложении — "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c . Мы должны найти значения целых чисел для x и y , которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b) . Если d†c , то уравнение не имеет решения. Если d|c , то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.

Частное решение

Если d|c , то можно найти частное решение вышеупомянутого уравнения, используя следующие шаги.

  1. Преобразуем уравнение к a1x + b1y = c1 , разделив обе части уравнения на d . Это возможно, потому, что d делит a , b , и c в соответствии с предположением.
  2. Найти s и t в равенстве a1s + b1t = 1 , используя расширенный алгоритм Евклида .
  3. Частное решение может быть найдено:
Общие решения

После нахождения частного решения общие решения могут быть найдены:

Найти частные и общие решения уравнения 21x + 14y = 35 .

Мы имеем d = НОД (21, 14) = 7 . При 7|35 уравнение имеет бесконечное число решений. Мы можем разделить обе стороны уравнения на 7 и получим уравнение 3x + 2y = 5 . Используя расширенный алгоритм Евклида , мы находим s и t , такие, что 3s + 2t = 1 . Мы имеем S = 1 и t = –1 . Решения будут следующие:

Поэтому решения будут следующие (5, –5) , (7, –8) , (9, –11) .

Мы можем легко проверить, что каждое из этих решений удовлетворяет первоначальному уравнению.

Рассмотрим очень интересное приложение решения диофантовых уравнений в реальной жизни. Мы хотим найти различные комбинации объектов, имеющих различные значения. Например, мы хотим обменять денежный чек 100$ на некоторое число банкнот 20$ и несколько банкнот по 5$ . Имеется много вариантов, которые мы можем найти, решая соответствующее диофантово уравнение 20x + 5y = 100 . Обозначим d = НОД (20, 5) = 5 и 5|100 . Уравнение имеет бесконечное число решений, но в этом случае приемлемы только несколько из них (только те ответы, в которых и x и y являются неотрицательными целыми числами). Мы делим обе части уравнения на 5 , чтобы получить 4x + y = 20 , и решаем уравнение 4s + t = 1 . Мы можем найти s = 0 и t = 1 , используя расширенный алгоритм Эвклида. Частное решение : = 0 \times 20 = 0" />
и = 1 \times 20 = 20" />
. Общие решения с неотрицательными x и y — (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0) . Остальная часть решений неприемлема, потому что y становится отрицательным. Кассир в банке должен спросить, какую из вышеупомянутых комбинаций мы хотим. Первое число в скобках обозначает число банкнот по 20$ ; второе число обозначает число банкнот по 5$ .

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

Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:

Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М, N).

В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.

Идея алгоритма Евклида

Идея этого алгоритма основана на том свойстве, что если M>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
кв
кц
вывод "НОД 300">Program Evklid;
var M, N: integer;
begin
writeln('Введите М и N');
readln(M, N);
while M<>N do
begin
if M>N
then M:=M-N
else N:=N-M
end;
write('Н0Д=',М)
end.

1. Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.

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

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

У алгоритма Эвклида, описанного в предыдущем параграфе, есть еще один вариант, более мощный. Мощный в данном случае не означает более быстрый. Достоинство нового варианта в том, что наибольший общий делитель — лишь часть выходных данных. Пусть натуральные числа, их наибольший общий делитель. Расширенный алгоритм Эвклида подсчитывает не только но и два целых числа таких, что

Отметим, что (за исключением нескольких тривиальных случаев) если а оказывается положительным, то отрицательное, и наоборот.

Напомним, что алгоритм Эвклида состоит из последовательности делений с остатком. Наибольший общий множитель представляет собой последний ненулевой остаток в этой последовательности. Значит, нам надо найти способ записывать последний ненулевой остаток в виде (6.1).

Суть алгоритма Кнута в том, что нам не следует ждать, пока мы дойдем до последнего ненулевого остатка; вместо этого нам стоит записывать в таком виде каждый из получающихся остатков. Такие действия должны приводить, по-видимому, к большому количеству дополнительной работы. Как мы увидим позднее, это не совсем так.

Предположим, что для вычисления наибольшего общего делителя чисел мы выполнили последовательность делений (5.1). Перепишем ее, сопровождая каждую операцию записью предполагаемого представления остатка:

Числа мы и хотим определить. Необходимую информацию удобно свести в таблицу:

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

Что же мы хотим сделать? Мы хотим заполнить столбцы Предположим на минуту, что мы получили таблицу заполненной до некоторой, скажем до строки. Для заполнения строки необходимо прежде всего разделить на . В результате получатся первые два элемента строки. Не будем забывать, что Таким образом,

Из строчек мы можем взять значения Можно записать

Подставляя эти значения в (6.3), получаем

Заметим, что для вычисления нам понадобились только частное и данные из двух строк таблицы, непосредственно предшествующих Вот почему алгоритм Кнута такой эффективный. Для заполнения очередной строки достаточно знать две строчки, непосредственно предшествующие ей; все остальные строчки хранить не обязательно.

Итак, мы получили рекуррентную процедуру. Все, что необходимо — это научиться ее запускать. Именно для этого мы

Поэтому можно просто положить

и процедуру можно запускать.

В результате цепочки делений с остатком мы получим равенство и вычислим такие целые числа что

Значит Заметим, что, зная мы можем найти по формуле

Поэтому достаточно вычислять только первые три столбца таблицы.

Приведем численный пример. Если то (полная) таблица выглядит так:

Пришло время разобраться, почему алгоритм дает правильный ответ и почему он завершает свою работу. Как и подразумевается названием, расширенный алгоритм Эвкли-да представляет собой просто алгоритм Эвклида из предыдущего параграфа, дополненный инструкциями для вычисления значений Поэтому он останавливается, и наибольший общий делитель составляет часть выходных данных. Кроме того, в каждой строке числа из столбцов а; и у удовлетворяют равенству типа (6.1), в котором число заменено остатком из соответствующей строки. В частности, равенство (6.1) выполняется, если в качестве а и 0 взять числа из столбцов строки, отвечающей последнему ненулевому остатку. Расширенный алгоритм Эвклида приводит к следующей теореме.

Теорема. Пусть наибольший общий делитель натуральных чисел Тогда существуют такие целые числа что

Заметим, что пара чисел упомянутая в теореме, не единственная. На самом деле таких пар бесконечно много. Например, возьмем для которых и рассмотрим какое-нибудь целое к. Тогда, как несложно проверить,

Приложив столько усилий к вычислению разумно задаться вопросом, для чего эти числа могут понадобиться. Проще всего добраться до ответа, продолжая читать эту книгу. Знание этих чисел необходимо для получения большого числа принципиально важных результатов, включая выбор ключей в системе шифрования RSA.

Читайте также: