\input style
\chapter{7 пересмотренный алгоритм евклида}
рИСКУЯ НАСКУЧИТЬ МОИМ ЧИТАТЕЛЯМ, Я ПОСВЯЩУ eЩЕ ОДНУ ГЛАВУ АЛГОРИТМУ 
еВКЛИДА. пОЛАГАЮ, ЧТО К ЭТОМУ ВРЕМЕНИ НЕКОТОРЫЕ ИЗ ЧИТАТЕЛЕЙ УЖЕ 
ЗАКОДИРУЮТ ЕГО В ВИДЕ
\prg
x, y:=X, Y;
\.{do} x\not=y \to \.{if} x>y \to x:=x-y
 \wbox y>x \to y:=y-x
\.{od};
\var{ПЕЧАТАТЬ}(x)
\grp
ГДЕ ПРЕДОХРАНИТЕЛЬ КОНСТРУКЦИИ ПОВТОРЕНИЯ ГАРАНТИРУЕТ, ЧТО 
КОНСТРУКЦИЯ ВЫБОРА НЕ ПРИВЕДЕТ К ОТКАЗУ. дРУГИЕ ЧИТАТЕЛИ ОБНАРУЖАТ, 
ЧТО ЭТОТ АЛГОРИТМ МОЖНО ЗАКОДИРОВАТЬ БОЛЕЕ ПРОСТО СЛЕДУЮЩИМ 
ОБРАЗОМ:
\prg
x,y:=X, Y;
\.{do} x>y \to x:=x-y
 \wbox y>x \to y:=y-x
\.{od};
\var{ПЕЧАТАТЬ}(x)
\grp

пОПРОБУЕМ ТЕПЕРЬ ЗАБЫТЬ ИГРУ НА ЛИСТЕ КАРТОНА И  ПОПЫТАЕМСЯ 
ИЗОБРЕСТИ ЗАНОВО АЛГОРИТМ еВКЛИДА ДЛЯ ОТЫСКАНИЯ НАИБОЛЬШЕГО ОБЩЕГО 
ДЕЛИТЕЛЯ ДВУХ ПОЛОЖИТЕЛЬНЫХ ЧИСЕЛ $X$ И $Y$. кОГДА МЫ СТАЛКИВАЕМСЯ 
С ТАКОГО РОДА ПРОБЛЕМОЙ, В  ПРИНЦИПЕ ВСЕГДА ВОЗМОЖНЫ ДВА ПОДХОДА.

пЕРВЫЙ СОСТОИТ В ТОМ, ЧТОБЫ ПЫТАТЬСЯ СЛЕДОВАТЬ ОПРЕДЕЛЕНИЮ 
ТРЕБУЕМОГО ОТВЕТА НАСТОЛЬКО БЛИЗКО, НАСКОЛЬКО ЭТО ВОЗМОЖНО. 
пО-ВИДИМОМУ, МЫ МОГЛИ БЫ СФОРМИРОВАТЬ ТАБЛИЦУ ДЕЛИТЕЛЕЙ ЧИСЛА $X$; 
ЭТА ТАБЛИЦА СОДЕРЖАЛА БЫ ТОЛЬКО КОНЕЧНОЕ ЧИСЛО ЭЛЕМЕНТОВ, СРЕДИ 
КОТОРЫХ ИМЕЛИСЬ БЫ 1 В КАЧЕСТВЕ НАИМЕНЬШЕГО И $X$ В КАЧЕСТВЕ 
НАИБОЛЬШЕГО ЭЛЕМЕНТА. (еСЛИ $X=1$, ТО НАИМЕНЬШИЙ И НАИБОЛЬШИЙ 
ЭЛЕМЕНТЫ СОВПАДУТ. зАТЕМ МЫ МОГЛИ БЫ СФОРМИРОВАТЬ ТАКЖЕ АНАЛОГИЧНУЮ 
ТАБЛИЦУ ДЕЛИТЕЛЕЙ $Y$. иЗ ЭТИХ ДВУХ ТАБЛИЦ МЫ МОГЛИ БЫ СФОРМИРОВАТЬ 
ТАБЛИЦУ ЧИСЕЛ, ПРИСУТСТВУЮЩИХ В НИХ ОБЕИХ. оНА ПРЕДСТАВЛЯЕТ СОБОЙ 
ТАБЛИЦУ \emph{ОБЩИХ} ДЕЛИТЕЛЕЙ ЧИСЕЛ $X$ И $Y$ И ОБЯЗАТЕЛЬНО 
ЯВЛЯЕТСЯ НЕПУСТОЙ, ТАК КАК СОДЕРЖИТ ЭЛЕМЕНТ 1. сЛЕДОВАТЕЛЬНО, ИЗ 
ЭТОЙ ТРЕТЬЕЙ ТАБЛИЦЫ МЫ МОЖЕМ ВЫБРАТЬ (ПОСКОЛЬКУ ОНА ТОЖЕ 
КОНЕЧНАЯ!) МАКСИМАЛЬНЫЙ ЭЛЕМЕНТ, И ОН БЫЛ БЫ  \emph{НАИБОЛЬШИМ} 
ОБЩИМ ДЕЛИТЕЛЕМ.

иНОГДА БЛИЗКОЕ СЛЕДОВАНИЕ ОПРЕДЕЛЕНИЮ, ПОДОБНОЕ ОБРИСОВАННОМУ ВЫШЕ, 
ЯВЛЯЕТСЯ ЛУЧШИМ ИЗ ТОГО, ЧТО МЫ МОЖЕМ СДЕЛАТЬ. сУЩЕСТВУЕТ, ОДНАКО, 
И ДРУГОЙ ПОДХОД, КОТОРЫЙ СТОИТ ИСПРОБОВАТЬ, ЕСЛИ МЫ ЗНАЕМ (ИЛИ 
МОЖЕМ УЗНАТЬ) СВОЙСТВА ФУНКЦИИ, ПОДЛЕЖАЩЕЙ ВЫЧИСЛЕНИЮ. мОЖЕТ 
ОКАЗАТЬСЯ, ЧТО МЫ ЗНАЕМ ТАК МНОГО СВОЙСТВ, ЧТО ОНИ В СОВОКУПНОСТИ 
ОПРЕДЕЛЯЮТ ЭТУ ФУНКЦИЮ, ТОГДА МЫ МОЖЕМ ПОПЫТАТЬСЯ ПОСТРОИТЬ ОТВЕТ, 
ИСПОЛЬЗУЯ ЭТИ СВОЙСТВА.

в СЛУЧАe НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ МЫ ЗАМЕЧАЕМ, НАПРИМЕР, ЧТО, 
ПОСКОЛЬКУ ДЕЛИТЕЛИ ЧИСЛА $-x$ ТЕ ЖЕ САМЫЕ, ЧТО И ДЛЯ  САМОГО ЧИСЛА 
$x$, $\нод(x, y)$ ОПРЕДЕЛЕН ТАКЖЕ ДЛЯ ОТРИЦАТЕЛЬНЫХ АРГУМЕНТОВ И НЕ 
МЕНЯЕТСЯ, ЕСЛИ МЫ ИЗМЕНЯЕМ ЗНАК АРГУМЕНТОВ. оН ОПРЕДЕЛЕН И ТОГДА, 
КОГДА ОДИН ИЗ АРГУМЕНТОВ РАВЕН НУЛЮ; ТАКОЙ АРГУМЕНТ ОБЛАДАЕТ 
БЕСКОНЕЧНОЙ ТАБЛИЦЕЙ ДЕЛИТЕЛЕЙ (И ПОЭТОМУ НАМ НЕ СЛЕДУЕТ ПЫТАТЬСЯ 
СТРОИТЬ ЭТУ ТАБЛИЦУ!), НО ПОСКОЛЬКУ ВТОРОЙ АРГУМЕНТ $(\not=0)$ 
ОБЛАДАЕТ КОНЕЧНОЙ ТАБЛИЦЕЙ ДЕЛИТЕЛЕЙ, ТАБЛИЦА ОБЩИХ ДЕЛИТЕЛЕЙ 
ЯВЛЯЕТСЯ ВСЕ ЖЕ НЕПУСТОЙ И КОНЕЧНОЙ. иТАК, МЫ ПРИХОДИМ К 
ЗАКЛЮЧЕНИЮ, ЧТО $\нод(x,y)$ ОПРЕДЕЛЕН ДЛЯ ВСЯКОЙ ПАРЫ $(x,y)$, 
ТАКОЙ, ЧТО $(x, y)\not=(0, 0)$. дАЛЕЕ, В СИЛУ СИММЕТРИИ ПОНЯТИЯ 
"ОБЩИЙ" НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ ЯВЛЯЕТСЯ СИММЕТРИЧНОЙ ФУНКЦИЕЙ 
СВОИХ ДВУХ АРГУМЕНТОВ. еЩЕ ОДНО НЕБОЛЬШОЕ УМСТВЕННОЕ УСИЛИЕ 
ПОЗВОЛИТ НАМ УБЕДИТЬСЯ В ТОМ, ЧТО НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ ДВУХ 
АРГУМЕНТОВ НЕ ИЗМЕНЯЕТСЯ, ЕСЛИ МЫ ЗАМЕНЯЕМ ОДИН ИЗ ЭТИХ АРГУМЕНТОВ 
ИХ СУММОЙ ИЛИ РАЗНОСТЬЮ. оБRЕДИНИВ ВСЕ ЭТИ РЕЗУЛЬТАТЫ, МЫ МОЖЕМ 
ЗАПИСАТЬ: ДЛЯ $(x,y)\not=(0,0)$
$$ 
\leqalignno{ 
\нод(x, y) &=  нод(y, x). & (А) \cr 
\нод(x, y)&=  нод(-x, y). & (Б) \cr 
\нод(x, y) &=нод(x+y, y) = нод(x-y, y)\hbox{  И Т. Д.} & (В) \cr 
\нод(x, y) &=abs(x),\hbox{ ЕСЛИ $x=y$}. & (Г) \cr 
} 
$$

пРЕДПОЛОЖИМ ДЛЯ ПРОСТОТЫ РАССУЖДЕНИЙ, ЧТО ЭТИМИ ЧЕТЫРЬМЯ СВОЙСТВАМИ 
ИСЧЕРПЫВАЮТСЯ НАШИ ПОЗНАНИЯ О ФУНКЦИИ $\нод$. дОСТАТОЧНО ЛИ ИХ? вЫ 
ВИДИТЕ, ЧТО ПЕРВЫЕ ТРИ ОТНОШЕНИЯ ВЫРАЖАЮТ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ 
ЧИСЕЛ $x$ И $y$ ЧЕРЕЗ  $\нод$ ДЛЯ ДРУГОЙ ПАРЫ, А ПОСЛЕДНЕЕ СВОЙСТВО 
ВЫРАЖАЕТ ЕГО НЕПОСРЕДСТВЕННО ЧЕРЕЗ $x$. и В ЭТОМ УЖЕ 
ПРОСМАТРИВАЮТСЯ КОНТУРЫ АЛГОРИТМА, КОТОРЫЙ ДЛЯ НАЧАЛА ОБЕСПЕЧИВАЕТ 
ИСТИННОСТЬ
$$ 
P= (\нод(X,Y)=\нод(x,y)) 
$$
(ЭТО ЛЕГКО ДОСТИГАЕТСЯ ПУТЕМ ПРИСВАИВАНИЯ "$x, y:= X, Y$"), ПОСЛЕ 
ЧЕГО МЫ "УТРАМБОВЫВАЕМ" ПАРУ ЗНАЧЕНИЙ $(x,y)$ ТАКИМ ОБРАЗОМ, ЧТОБЫ 
В СООТВЕТСТВИИ С (А), (Б) ИЛИ (В) ОТНОШЕНИЕ $P$ ОСТАВАЛОСЬ 
ИНВАРИАНТНЫМ. еСЛИ МЫ МОЖЕМ opГaНИЗОВАТЬ ЭТОТ ПРОЦЕСС УТРАМБОВКИ 
ТАК, ЧТОБЫ ДОСТИГНУТЬ СОСТОЯНИЯ, УДОВЛЕТВОРЯЮЩЕГО $x=y$, ТО, 
СОГЛАСНО (Г), МЫ НАХОДИМ ИСКОМЫЙ ОТВЕТ, ВЗЯВ АБСОЛЮТНОЕ ЗНАЧЕНИЕ 
$x$.

пОСКОЛЬКУ НАША КОНЕЧНАЯ ЦЕЛЬ СОСТОИТ В ТОМ, ЧТОБЫ ОБЕСПЕЧИТЬ ПРИ 
ИНВАРИАНТНОСТИ $P$ ИСТИННОСТЬ $x=y$, МЫ МОГЛИ БЫ ИСПЫТАТЬ В 
КАЧЕСТВЕ МОНОТОННО УБЫВАЮЩЕЙ ФУНКЦИИ ФУНКЦИЮ
$$ 
t=\abs(x-y). 
$$

чТОБЫ УПРОСТИТЬ НАШ АНАЛИЗ (ВСЕГДА ПОХВАЛЬНАЯ ЦЕЛЬ!), МЫ ОТМЕЧАЕМ, 
ЧТО ЕСЛИ НАЧАЛЬНЫЕ ЗНАЧЕНИЯ $x$ И $y$  НЕОТРИЦАТЕЛЬНЫЕ, ТО НИЧЕГО 
НЕЛЬЗЯ ВЫИГРАТЬ ВВЕДЕНИЕМ  ОТРИЦАТЕЛЬНОГО ЗНАЧЕНИЯ: ЕСЛИ 
ПРИСВАИВАНИЕ $x:=E$ ОБЕСПЕЧИЛО БЫ $x<0$, ТО ПРИСВАИВАНИЕ $x:=-E$ 
НИКОГДА НЕ ПРИВЕЛО БЫ К ПОЛУЧЕНИЮ БОЛЬШЕГО КОНЕЧНОГО ЗНАЧЕНИЯ $t$ 
(ПОТОМУ, ЧТО $y\ge 0$). пОЭТОМУ МЫ УСИЛИВАЕМ НАШЕ ОТНОШЕНИЕ $P$, 
КОТОРОЕ ДОЛЖНО СОХРАНЯТЬСЯ ИНВАРИАНТНЫМ: 
$$ 
P=(P1 \and P2) 
$$ 
ПРИ 
$$  
P1=(\нод (X, Y)=\нод (x, y)) 
$$ 
И 
$$ 
P2=(x\ge 0 \and y\ge 0) 
$$
эТО ОЗНАЧАЕТ, ЧТО МЫ ОТКАЗЫВАЕМСЯ ОТ ВСЯКОГО ИСПОЛЬЗОВАНИЯ ОПЕРАЦИЙ 
$x:=-x$ И $y:=-y$, Т.Е. ПРЕОБРАЗОВАНИЙ, ДОПУСТИМЫХ ПО СВОЙСТВУ (Б). 
нАМ ОСТАЮТСЯ ОПЕРАЦИИ
$$ 
\eqalign{ 
\hbox{ИЗ (a):}\; x,y&:=y,x\cr 
\hbox{ИЗ (В):}\;\;\;\;    x&:=x+y \;  y:=y+x\cr                                               
x&:=x-y   \; y:=y-x\cr
x&:=y-x  \;  y:=x-y\cr 
} 
$$

бУДЕМ ЗАНИМАТЬСЯ ИМИ ПО ОЧЕРЕДИ И НАЧНЕМ С  РАССМОТРЕНИЯ 
$x, y :=y, x$:
$$ 
\wp("x, y: = y, x", \abs(x-y) \le t_0) = (\abs(y-x)\le t_0) 
$$ 
ПОЭТОМУ
$$ 
t_{min} (x, y) = \abs (y-x) 
$$
СЛЕДОВАТЕЛЬНО 
$$ 
\wdec ("x, y:= y, x", \abs (x-y) ) 
= (\abs (y-x) \le \abs(x-y)-1)=F 
$$

и ЗДЕСЬ --- ДЛЯ ТЕХ, КТО НЕ ПОВЕРИЛ БЫ БЕЗ ФОРМАЛЬНОГО ВЫВОДА,---МЫ 
ДОКАЗАЛИ (ИЛИ, ЕСЛИ УГОДНО, ОБНАРУЖИЛИ) С ПОМОЩЬЮ НАШero 
ИСЧИСЛЕНИЯ, ЧТО ПРЕОБРАЗУЮЩАЯ ОПЕРАЦИЯ $x,y:=y,x$ НЕ ПРЕДСТАВЛЯЕТ 
ИНТЕРЕСА, ТАК КАК ОНА НЕ МОЖЕТ ПРИВЕСТИ К ЖЕЛАЕМОМУ ЭФФЕКТИВНОМУ 
УМЕНЬШЕНИЮ ВЫБРАННОЙ НАМИ ФУНКЦИИ  $t$.

сЛЕДУЮЩЕЙ ИСПЫТЫВАЕТСЯ ОПЕРАЦИЯ $x:=x+y$, И МЫ НАХОДИМ, СНОВА 
ПРИМЕНЯЯ ИСЧИСЛЕНИЕ ИЗ ПРЕДЫДУЩИХ ГЛАВ:
$$ 
\displaylines{ 
\wp("x:=x+y", \abs(x-y)\le t_0)=(\abs(x)\le t_0)\cr 
t_{min} (x, y)=\abs(x)=x\cr 
} 
$$
(МЫ ОГРАНИЧИВАЕМСЯ СОСТОЯНИЯМИ, УДОВЛЕТВОРЯЮЩИМИ $P$) 
$$
\eqalign{ 
\wdec("x:=x+y", \abs(x-y)) &= (t_{min}(x, y) \le t(x, y)-1)\cr 
&= (x\le \abs(x-y)-1)\cr 
&= (x+1\le \abs(x-y))\cr 
&= (x+1\le x-y \or x+1 \le y-x)\cr 
} 
$$

пОСКОЛЬКУ ИЗ $P$ СЛЕДУЕТ ОТРИЦАНИЕ ПЕРВОГО ЧЛЕНА И К ТОМУ ЖЕ 
$P \Rightarrow \wp("x:=x+y", P)$, ТО УРАВНЕНИЕ НАШЕГО ПРЕДОХРАНИТЕЛЯ
$$ 
(P \and B_j) \Rightarrow (\wp (SL_j, P) \and \wdec (SL_j, t )) 
$$
УДОВЛЕТВОРЯЕТСЯ ПОСЛЕДНИМ ЧЛЕНОМ, И МЫ НАШЛИ НАШУ ПЕРВУЮ, А ТАКЖЕ 
(ИЗ СООБРАЖЕНИЙ СИММЕТРИИ) НАШУ ВТОРУЮ ОХРАНЯЕМУЮ КОМАНДУ: 
$$ 
x+1\le y-x \to x:=x+y 
$$
И 
$$
 y+1\le x-y \to y :=y+x 
$$
аНАЛОГИЧНО МЫ НАХОДИМ (ФОРМАЛЬНЫЕ МАНИПУЛЯЦИИ ПРЕДОСТАВЛЯЮТСЯ В 
КАЧЕСТВЕ УПРАЖНЕНИЯ ПРИЛЕЖНОМУ ЧИТАТЕЛЮ)
$$ 
1\le y \and 3 * y \le 2* x-1\to x:=x-y 
$$ 
И 
$$ 
1\le x \and 3 * x \le2 * y-1\to y:=y-x
$$
И 
$$ 
 x+1\le y-x \to x:=y-x 
$$ 
И
$$
y+1\le x-y \to y:=x-y
$$

рАЗОБРАВШИСЬ В ТОМ, ЧЕГО МЫ ДОСТИГЛИ, МЫ ВЫНУЖДЕНЫ ПРИЙТИ К 
ДОСАДНОМУ ЗАКЛЮЧЕНИЮ, ЧТО СПОСОБОМ, НАМЕЧЕННЫМ В КОНЦЕ ПРЕДЫДУЩЕЙ 
ГЛАВЫ, НАМ НЕ УДАЛОСЬ РЕШИТЬ СВОЮ ЗАДАЧУ: ИЗ $P \and \non BB$ НЕ 
СЛЕДУЕТ, ЧТО $x=y$. (нАПРИМЕР, ПРИ $(x, y) = (5,7)$ ЗНАЧЕНИЯ ВСЕХ 
ПРЕДОХРАНИТЕЛЕЙ ОКАЗЫВАЮТСЯ ЛОЖНЫМИ.) мОРАЛЬ СКАЗАННОГО, 
РАЗУМЕЕТСЯ, В ТОМ, ЧТО НАШИ ШЕСТЬ ШАГОВ НЕ ВСЕГДА ОБЕСПЕЧИВАЮТ 
ТАКОЙ ПУТЬ ИЗ НАЧАЛЬНОГО СОСТОЯНИЯ В КОНЕЧНОЕ СОСТОЯНИЕ, ПРИ 
КОТОРОМ $\abs(x-y)$ МОНОТОННО УМЕНЬШАЕТСЯ. пОЭТОМУ НАМ НУЖНО 
ИСПЫТАТЬ ДРУГИЕ ВОЗМОЖНОСТИ.

дЛЯ НАЧАЛА ЗАМЕТИМ, ЧТО НЕ ПОВРЕДИТ НЕСКОЛЬКО УСИЛИТЬ УСЛОВИЕ $P2$: 
$$ 
P2=(x>0 \and y>0) 
$$
ТАК КАК НАЧАЛЬНЫЕ ЗНАЧЕНИЯ $x$ И $y$ УДОВЛЕТВОРЯЮТ ТАКОМУ УСЛОВИЮ, 
И, КРОМЕ ТОГО, НЕТ НИКАКОГО СМЫСЛА В ГЕНЕРАЦИИ РАВНОГО НУЛЮ 
ЗНАЧЕНИЯ, ПОСКОЛЬКУ ЭТО ЗНАЧЕНИЕ МОЖЕТ ВОЗНИКНУТЬ ТОЛЬКО ПРИ 
ВЫЧИТАНИИ В СОСТОЯНИИ, ГДЕ $x=y$, Т.Е. КОГДА УЖЕ ДОСТИГНУТО 
КОНЕЧНОЕ СОСТОЯНИЕ. нО ЭТО ТОЛЬКО МАЛАЯ МОДИФИКАЦИЯ; ОСНОВНАЯ 
МОДИФИКАЦИЯ ДОЛЖНА БЫТЬ СВЯЗАНА С ВВЕДЕНИЕМ НОВОЙ ФУНКЦИИ $t$, И Я 
ПРЕДЛАГАЮ ВЗЯТЬ ТАКУЮ ФУНКЦИЮ $t$, КОТОРАЯ ТОЛЬКО ОГРАНИЧЕНА СНИЗУ 
В СИЛУ ИНВАРИАНТНОСТИ $P$. оЧЕВИДНЫМ ПРИМЕРОМ ЯВЛЯЕТСЯ
$$ 
t=x+y 
$$
мЫ ВЫЯСНЯЕМ, ЧТО ДЛЯ ОДНОВРЕМЕННОГО ПРИСВАИВАИВАНИЯ
$$ 
\wdec ("x, y:=y, x", x+y) =F 
$$
И ПОЭТОМУ ОДНОВРЕМЕННОЕ ПРИСВАИВАНИЕ ОТВЕРГАЕТСЯ. 

мЫ НАХОДИМ ДЛЯ ПРИСВАИВАНИЯ $x:= x+y$
$$ 
\wdec("x:=x+y", x+y) = (y< 0) 
$$
иСТИННОСТЬ ЭТОГО ВЫРАЖЕНИЯ ИСКЛЮЧАЕТСЯ ИСТИННОСТЬЮ ИНВАРИАНТНОГО 
ОТНОШЕНИЯ $P$, А СЛЕДОВАТЕЛЬНО, ТАКОЕ ПРИСВАИВАНИЕ (НАРЯДУ С 
ПРИСВАИВАНИЕМ $y:=y+x$)  ТАКЖЕ ОТВЕРГАЕТСЯ.

оДНАКО ДЛЯ СЛЕДУЮЩЕГО ПРИСВАИВАНИЯ $x:=x-y$ МЫ НАХОДИМ 
$$ 
\wdec("x:=x-y", x+y) = (y>0) 
$$
Т. Е. УСЛОВИЕ, КОТОРОЕ, ЛОГИЧЕСКИ СЛЕДУЕТ ИЗ УСЛОВИЯ $P$ ( 
УСИЛЕННОГО МНОЮ РАДИ ЭТОГО). 

оКРЫЛЕННЫЕ НАДЕЖДОЙ, МЫ ИЗУЧАЕМ 
$$ 
\wp("x:=x-y", P) = (\нод(X, Y)=\нод(x-y, y) \and x-y > 0 \and y>0) 
$$
кРАЙНИЕ ЧЛЕНЫ МОЖНО ОТБРОСИТЬ, ПОТОМУ ЧТО ОНИ СЛЕДУЮТ ИЗ $P$, И У 
НАС ОСТАЕТСЯ СРЕДНИЙ ЧЛЕН: ИТАК, МЫ НАХОДИМ
\prg 
x>y\to x:=x-y 
\grp 
И
\prg
y>Х\to y:=y-x 
\grp
и НА ЭТОМ МЫ МОГЛИ БЫ ПРЕКРАТИТЬ ИССЛЕДОВАНИЕ, ТАК КАК, КОГДА 
ЗНАЧЕНИЯ ОБОИХ ПРЕДОХРАНИТЕЛЕЙ СТАНОВЯТСЯ ЛОЖНЫМИ, ВЫПОЛНЯЕТСЯ 
ЖЕЛАЕМОЕ НАМИ ОТНОШЕНИЕ $x=y$. еСЛИ МЫ ПРОДОЛЖИМ, ТО НАЙДЕМ ТРЕТИЙ 
И ЧЕТВЕРТЫЙ ВАРИАНТЫ:
\prg
 x>y-x \and y>x\to x:=y-x 
\grp
 И
\prg
 y>x-y \and x>y\to y:= x-y 
\grp
НО НЕ ЯСНО, ЧТО МОЖНО ВЫИГРАТЬ ИХ ВКЛЮЧЕНИЕМ.

{\bf уПРАЖНЕНИЯ.}

1. иССЛЕДУЙТЕ ПРИ ТОМ ЖЕ $P$ ВЫБОР $t=\max(x, y)$.

2. иССЛЕДУЙТЕ ПРИ ТОМ ЖЕ $P$ ВЫБОР $t=x+2*y$.

3. дОКАЖИТЕ, ЧТО ПРИ $X>0$ И $Y>0$ СЛЕДУЮЩАЯ ПРОГРАММА, ОПЕРИРУЮЩАЯ 
НАД ЧЕТЫРЬМЯ ПЕРЕМЕННЫМИ,
\prg
x, y, u, v:=X, Y, Y, X;
\.{do} x>y\to x, v:=x-y, v+u
 \wbox y>x \to y, u:= y-x, u+v
\.{od};
\var{ПЕЧАТАТЬ}((x+y)/2); \var{ПЕЧАТАТЬ}((u+v)/2)
\grp
ПЕЧАТАЕТ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ ЧИСЕЛ х И у, А СЛЕДОМ ЗА НИМ ИХ 
НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ. (кОНЕЦ УПРАЖНЕНИЙ.)

нАКОНЕЦ, ЕСЛИ НАШ МАЛЕНЬКИЙ АЛГОРИТМ ЗАПУСКАЕТСЯ ПРИ ПАРЕ $(X,Y)$, 
КОТОРАЯ НЕ УДОВЛЕТВОРЯЕТ ПРЕДПОЛОЖЕНИЮ $X>0 \and Y>0$, ТО 
ПРОИЗОЙДУТ НЕПРИЯТНОСТИ: ЕСЛИ $(X,Y)=(0, 0)$, ТО ПОЛУЧИТСЯ 
НЕПРАВИЛЬНЫЙ НУЛЕВОЙ РЕЗУЛЬТАТ, А ЕСЛИ ОДИН ИЗ АРГУМЕНТОВ 
ОТРИЦАТЕЛЬНЫЙ, ТО ЗАПУСК ПРИВЕДЕТ К БЕСКОНЕЧНОЙ РАБОТЕ. эТОГО МОЖНО 
ИЗБЕЖАТЬ, НАПИСАВ
\prg
\.{if} X>0 \and Y>0 \to x,y:=X,Y;
   \.{do} x>y\to x:=x-y\wbox y>x\to y:=y-x \.{od}; \var{ПЕЧАТАТЬ}(x) 
\.{fi}
\grp

вКЛЮЧИВ ТОЛЬКО ОДИН ВАРИАНТ В КОНСТРУКЦИЮ ВЫБОРА, МЫ ЯВНО ВЫРАЗИЛИ 
УСЛОВИЯ, ПРИ КОТОРЫХ ОЖИДАЕТСЯ РАБОТА ЭТОЙ МАЛЕНЬКОЙ ПРОГРАММЫ. в 
ТАКОМ ВИДЕ ЭТО ХОРОШО ЗАЩИЩЕННЫЙ И ДОВОЛЬНО САМОСТОЯТЕЛЬНЫЙ 
ФРАГМЕНТ, ОБЛАДАЮЩИЙ ТЕМ ПРИЯТНЫМ СВОЙСТВОМ, ЧТО ПОПЫТКА ЗАПУСКА 
ВНЕ ЕГО ОБЛАСТИ ОПРЕДЕЛЕНИЯ ПРИВЕДЕТ К НЕМЕДЛЕННОМУ ОТКАЗУ.
\bye