Расширенный итеративный алгоритм Евклида

Расширенный алгоритм Евклида

Пусть есть два отрезка. Их длины a и b – целые числа (далее, говоря о числах, считаем их всегда целыми). Скажем, a=2322, а b=654.

Если, например, отложить на прямой отрезок a, затем, в обратном направлении, три раза b, то получим отрезок длиной 360 (рис. 1.21). Действительно, a+b· ( – 3) =2322+654· ( – 3) =360.

Рис. 1.21. Пример откладывания на прямой отрезков длины a и b

Можно получить и отрезок меньшей длины. Действуем так: a· 2 +b· ( – 7) = 2322· 2 +654·(– 7) =66 – два раза откладываем отрезок a и семь раз отрезок b в обратном направлении. Возникает, как минимум, четыре вопроса.

1. Какую наименьшую длину удастся получить, «орудуя» заданными отрезками a и b?

2. Как это сделать, сколько раз взять отрезок a и сколько раз отрезок b?

3. Какой длины отрезки отмеряются с помощью a и b?

4. Если отрезок заданной длины отмеряется, то, как это сделать?

Первый вопрос

Итак, отрезок какой наименьшей длины можно получить, используя отрезки a и b?

Эксперимент. Пусть a и b – положительные, фиксированные, а x и y –произвольные целые числа. Напишем процедуру, которая перебирает числа вида a·x+b·y и находит среди них минимальное положительное.

Procedure Small (a, b: Integer; Var min: Integer);

Const k=500;

Var x, y, t: Integer;

Begin

min: =a;

For x: =-k To k Do

For y: =-k To k Do Begin

t: =a*x+b*y;

If (t> 0) And (t< min) Then min: =t;

End;

End;

Перебор ограничен константой k и выглядит несколько искусственным, но он достаточен для генерации идеи (гипотезы). Экспериментируя, заполняем таблицу (табл. 1.6).

Примечание. Убедитесь, что данные в табл. 1.6 не изменятся и при б о льших k, а гипотеза будет верна и для других a и b.

Таблица 1.6

Гипотеза. Обозначим множество всех чисел вида a·x+b·y буквой P. Возьмём min – наименьшее положительное число из P. Оказывается, это наибольший общий делитель a и b.

Второй вопрос

Как отмерить отрезок наименьшей длины? Сколько раз для этого взять отрезок a и сколько раз отрезок b?

Почти всегда срабатывает метод «грубой силы» – перебор. Эта задача не исключение. Отрезки a и b даны. Наименьшую длину d=НОД(a, b) находим по алгоритму Евклида. После этого подбираем целые x и y такие, чтобы a·x+b·y=d. Для этого ищем целое x такое, при котором и y=(d–a·x)/b также целое. Начинаем с x=0, а затем «движемся» от него по числовой прямой, в двух направлениях одновременно, с шагом 1.

Procedure Simple(a, b, d: Integer; Var x, y: Integer);

Var xn, xp: Integer;

Begin

xp: =0; xn: =0;

While ((d-a*xp) Mod b< > 0) And ((d-a*xn) Mod b< > 0) Do

Begin

xp: =xp+1;

xn: =xn-1;

End;

If (d-a*xp) Mod b=0 Then x: =xp Else x: =xn;

y: =(d-a*x) Div b;

End;

Цикл гарантированно завершится. Ведь искомое x точно есть, либо справа от нуля, либо слева.

Однако, узнать и сам НОД(a, b), и его представление в виде a·x+b·y, где x и y – целые числа, можно одновременно и без перебора. Для этого требуется изменить (расширить) стандартную версию алгоритма Евклида.

Расширенный итеративный алгоритм Евклида

Нам предстоит дополнить знакомую логику реализации алгоритма Евклида.

Procedure Euclid (a, b: Integer; Var d: Integer);

Var r: Integer;

Begin