\input style
\chapter{7 peresmotrennyj algoritm evklida}
rISKUYA NASKUCHITX MOIM CHITATELYAM, YA POSVYASHCHU eSHCHE ODNU GLAVU ALGORITMU 
eVKLIDA. pOLAGAYU, CHTO K |TOMU VREMENI NEKOTORYE IZ CHITATELEJ UZHE 
ZAKODIRUYUT EGO V VIDE
\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{PECHATATX}(x)
\grp
GDE PREDOHRANITELX KONSTRUKCII POVTORENIYA GARANTIRUET, CHTO 
KONSTRUKCIYA VYBORA NE PRIVEDET K OTKAZU. dRUGIE CHITATELI OBNARUZHAT, 
CHTO |TOT ALGORITM MOZHNO ZAKODIROVATX BOLEE PROSTO SLEDUYUSHCHIM 
OBRAZOM:
\prg
x,y:=X, Y;
\.{do} x>y \to x:=x-y
 \wbox y>x \to y:=y-x
\.{od};
\var{PECHATATX}(x)
\grp

pOPROBUEM TEPERX ZABYTX IGRU NA LISTE KARTONA I  POPYTAEMSYA 
IZOBRESTI ZANOVO ALGORITM eVKLIDA DLYA OTYSKANIYA NAIBOLXSHEGO OBSHCHEGO 
DELITELYA DVUH POLOZHITELXNYH CHISEL $X$ I $Y$. kOGDA MY STALKIVAEMSYA 
S TAKOGO RODA PROBLEMOJ, V  PRINCIPE VSEGDA VOZMOZHNY DVA PODHODA.

pERVYJ SOSTOIT V TOM, CHTOBY PYTATXSYA SLEDOVATX OPREDELENIYU 
TREBUEMOGO OTVETA NASTOLXKO BLIZKO, NASKOLXKO |TO VOZMOZHNO. 
pO-VIDIMOMU, MY MOGLI BY SFORMIROVATX TABLICU DELITELEJ CHISLA $X$; 
|TA TABLICA SODERZHALA BY TOLXKO KONECHNOE CHISLO |LEMENTOV, SREDI 
KOTORYH IMELISX BY 1 V KACHESTVE NAIMENXSHEGO I $X$ V KACHESTVE 
NAIBOLXSHEGO |LEMENTA. (eSLI $X=1$, TO NAIMENXSHIJ I NAIBOLXSHIJ 
|LEMENTY SOVPADUT. zATEM MY MOGLI BY SFORMIROVATX TAKZHE ANALOGICHNUYU 
TABLICU DELITELEJ $Y$. iZ |TIH DVUH TABLIC MY MOGLI BY SFORMIROVATX 
TABLICU CHISEL, PRISUTSTVUYUSHCHIH V NIH OBEIH. oNA PREDSTAVLYAET SOBOJ 
TABLICU \emph{OBSHCHIH} DELITELEJ CHISEL $X$ I $Y$ I OBYAZATELXNO 
YAVLYAETSYA NEPUSTOJ, TAK KAK SODERZHIT |LEMENT 1. sLEDOVATELXNO, IZ 
|TOJ TRETXEJ TABLICY MY MOZHEM VYBRATX (POSKOLXKU ONA TOZHE 
KONECHNAYA!) MAKSIMALXNYJ |LEMENT, I ON BYL BY  \emph{NAIBOLXSHIM} 
OBSHCHIM DELITELEM.

iNOGDA BLIZKOE SLEDOVANIE OPREDELENIYU, PODOBNOE OBRISOVANNOMU VYSHE, 
YAVLYAETSYA LUCHSHIM IZ TOGO, CHTO MY MOZHEM SDELATX. sUSHCHESTVUET, ODNAKO, 
I DRUGOJ PODHOD, KOTORYJ STOIT ISPROBOVATX, ESLI MY ZNAEM (ILI 
MOZHEM UZNATX) SVOJSTVA FUNKCII, PODLEZHASHCHEJ VYCHISLENIYU. mOZHET 
OKAZATXSYA, CHTO MY ZNAEM TAK MNOGO SVOJSTV, CHTO ONI V SOVOKUPNOSTI 
OPREDELYAYUT |TU FUNKCIYU, TOGDA MY MOZHEM POPYTATXSYA POSTROITX OTVET, 
ISPOLXZUYA |TI SVOJSTVA.

v SLUCHAe NAIBOLXSHEGO OBSHCHEGO DELITELYA MY ZAMECHAEM, NAPRIMER, CHTO, 
POSKOLXKU DELITELI CHISLA $-x$ TE ZHE SAMYE, CHTO I DLYA  SAMOGO CHISLA 
$x$, $\nod(x, y)$ OPREDELEN TAKZHE DLYA OTRICATELXNYH ARGUMENTOV I NE 
MENYAETSYA, ESLI MY IZMENYAEM ZNAK ARGUMENTOV. oN OPREDELEN I TOGDA, 
KOGDA ODIN IZ ARGUMENTOV RAVEN NULYU; TAKOJ ARGUMENT OBLADAET 
BESKONECHNOJ TABLICEJ DELITELEJ (I PO|TOMU NAM NE SLEDUET PYTATXSYA 
STROITX |TU TABLICU!), NO POSKOLXKU VTOROJ ARGUMENT $(\not=0)$ 
OBLADAET KONECHNOJ TABLICEJ DELITELEJ, TABLICA OBSHCHIH DELITELEJ 
YAVLYAETSYA VSE ZHE NEPUSTOJ I KONECHNOJ. iTAK, MY PRIHODIM K 
ZAKLYUCHENIYU, CHTO $\nod(x,y)$ OPREDELEN DLYA VSYAKOJ PARY $(x,y)$, 
TAKOJ, CHTO $(x, y)\not=(0, 0)$. dALEE, V SILU SIMMETRII PONYATIYA 
"OBSHCHIJ" NAIBOLXSHIJ OBSHCHIJ DELITELX YAVLYAETSYA SIMMETRICHNOJ FUNKCIEJ 
SVOIH DVUH ARGUMENTOV. eSHCHE ODNO NEBOLXSHOE UMSTVENNOE USILIE 
POZVOLIT NAM UBEDITXSYA V TOM, CHTO NAIBOLXSHIJ OBSHCHIJ DELITELX DVUH 
ARGUMENTOV NE IZMENYAETSYA, ESLI MY ZAMENYAEM ODIN IZ |TIH ARGUMENTOV 
IH SUMMOJ ILI RAZNOSTXYU. oB®EDINIV VSE |TI REZULXTATY, MY MOZHEM 
ZAPISATX: DLYA $(x,y)\not=(0,0)$
$$ 
\leqalignno{ 
\nod(x, y) &=  nod(y, x). & (A) \cr 
\nod(x, y)&=  nod(-x, y). & (B) \cr 
\nod(x, y) &=nod(x+y, y) = nod(x-y, y)\hbox{  I T. D.} & (V) \cr 
\nod(x, y) &=abs(x),\hbox{ ESLI $x=y$}. & (G) \cr 
} 
$$

pREDPOLOZHIM DLYA PROSTOTY RASSUZHDENIJ, CHTO |TIMI CHETYRXMYA SVOJSTVAMI 
ISCHERPYVAYUTSYA NASHI POZNANIYA O FUNKCII $\nod$. dOSTATOCHNO LI IH? vY 
VIDITE, CHTO PERVYE TRI OTNOSHENIYA VYRAZHAYUT NAIBOLXSHIJ OBSHCHIJ DELITELX 
CHISEL $x$ I $y$ CHEREZ  $\nod$ DLYA DRUGOJ PARY, A POSLEDNEE SVOJSTVO 
VYRAZHAET EGO NEPOSREDSTVENNO CHEREZ $x$. i V |TOM UZHE 
PROSMATRIVAYUTSYA KONTURY ALGORITMA, KOTORYJ DLYA NACHALA OBESPECHIVAET 
ISTINNOSTX
$$ 
P= (\nod(X,Y)=\nod(x,y)) 
$$
(|TO LEGKO DOSTIGAETSYA PUTEM PRISVAIVANIYA "$x, y:= X, Y$"), POSLE 
CHEGO MY "UTRAMBOVYVAEM" PARU ZNACHENIJ $(x,y)$ TAKIM OBRAZOM, CHTOBY 
V SOOTVETSTVII S (A), (B) ILI (V) OTNOSHENIE $P$ OSTAVALOSX 
INVARIANTNYM. eSLI MY MOZHEM opGaNIZOVATX |TOT PROCESS UTRAMBOVKI 
TAK, CHTOBY DOSTIGNUTX SOSTOYANIYA, UDOVLETVORYAYUSHCHEGO $x=y$, TO, 
SOGLASNO (G), MY NAHODIM ISKOMYJ OTVET, VZYAV ABSOLYUTNOE ZNACHENIE 
$x$.

pOSKOLXKU NASHA KONECHNAYA CELX SOSTOIT V TOM, CHTOBY OBESPECHITX PRI 
INVARIANTNOSTI $P$ ISTINNOSTX $x=y$, MY MOGLI BY ISPYTATX V 
KACHESTVE MONOTONNO UBYVAYUSHCHEJ FUNKCII FUNKCIYU
$$ 
t=\abs(x-y). 
$$

chTOBY UPROSTITX NASH ANALIZ (VSEGDA POHVALXNAYA CELX!), MY OTMECHAEM, 
CHTO ESLI NACHALXNYE ZNACHENIYA $x$ I $y$  NEOTRICATELXNYE, TO NICHEGO 
NELXZYA VYIGRATX VVEDENIEM  OTRICATELXNOGO ZNACHENIYA: ESLI 
PRISVAIVANIE $x:=E$ OBESPECHILO BY $x<0$, TO PRISVAIVANIE $x:=-E$ 
NIKOGDA NE PRIVELO BY K POLUCHENIYU BOLXSHEGO KONECHNOGO ZNACHENIYA $t$ 
(POTOMU, CHTO $y\ge 0$). pO|TOMU MY USILIVAEM NASHE OTNOSHENIE $P$, 
KOTOROE DOLZHNO SOHRANYATXSYA INVARIANTNYM: 
$$ 
P=(P1 \and P2) 
$$ 
PRI 
$$  
P1=(\nod (X, Y)=\nod (x, y)) 
$$ 
I 
$$ 
P2=(x\ge 0 \and y\ge 0) 
$$
eTO OZNACHAET, CHTO MY OTKAZYVAEMSYA OT VSYAKOGO ISPOLXZOVANIYA OPERACIJ 
$x:=-x$ I $y:=-y$, T.E. PREOBRAZOVANIJ, DOPUSTIMYH PO SVOJSTVU (B). 
nAM OSTAYUTSYA OPERACII
$$ 
\eqalign{ 
\hbox{IZ (a):}\; x,y&:=y,x\cr 
\hbox{IZ (V):}\;\;\;\;    x&:=x+y \;  y:=y+x\cr                                               
x&:=x-y   \; y:=y-x\cr
x&:=y-x  \;  y:=x-y\cr 
} 
$$

bUDEM ZANIMATXSYA IMI PO OCHEREDI I NACHNEM S  RASSMOTRENIYA 
$x, y :=y, x$:
$$ 
\wp("x, y: = y, x", \abs(x-y) \le t_0) = (\abs(y-x)\le t_0) 
$$ 
PO|TOMU
$$ 
t_{min} (x, y) = \abs (y-x) 
$$
SLEDOVATELXNO 
$$ 
\wdec ("x, y:= y, x", \abs (x-y) ) 
= (\abs (y-x) \le \abs(x-y)-1)=F 
$$

i ZDESX --- DLYA TEH, KTO NE POVERIL BY BEZ FORMALXNOGO VYVODA,---MY 
DOKAZALI (ILI, ESLI UGODNO, OBNARUZHILI) S POMOSHCHXYU NASHero 
ISCHISLENIYA, CHTO PREOBRAZUYUSHCHAYA OPERACIYA $x,y:=y,x$ NE PREDSTAVLYAET 
INTERESA, TAK KAK ONA NE MOZHET PRIVESTI K ZHELAEMOMU |FFEKTIVNOMU 
UMENXSHENIYU VYBRANNOJ NAMI FUNKCII  $t$.

sLEDUYUSHCHEJ ISPYTYVAETSYA OPERACIYA $x:=x+y$, I MY NAHODIM, SNOVA 
PRIMENYAYA ISCHISLENIE IZ PREDYDUSHCHIH GLAV:
$$ 
\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 
} 
$$
(MY OGRANICHIVAEMSYA SOSTOYANIYAMI, UDOVLETVORYAYUSHCHIMI $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 
} 
$$

pOSKOLXKU IZ $P$ SLEDUET OTRICANIE PERVOGO CHLENA I K TOMU ZHE 
$P \Rightarrow \wp("x:=x+y", P)$, TO URAVNENIE NASHEGO PREDOHRANITELYA
$$ 
(P \and B_j) \Rightarrow (\wp (SL_j, P) \and \wdec (SL_j, t )) 
$$
UDOVLETVORYAETSYA POSLEDNIM CHLENOM, I MY NASHLI NASHU PERVUYU, A TAKZHE 
(IZ SOOBRAZHENIJ SIMMETRII) NASHU VTORUYU OHRANYAEMUYU KOMANDU: 
$$ 
x+1\le y-x \to x:=x+y 
$$
I 
$$
 y+1\le x-y \to y :=y+x 
$$
aNALOGICHNO MY NAHODIM (FORMALXNYE MANIPULYACII PREDOSTAVLYAYUTSYA V 
KACHESTVE UPRAZHNENIYA PRILEZHNOMU CHITATELYU)
$$ 
1\le y \and 3 * y \le 2* x-1\to x:=x-y 
$$ 
I 
$$ 
1\le x \and 3 * x \le2 * y-1\to y:=y-x
$$
I 
$$ 
 x+1\le y-x \to x:=y-x 
$$ 
I
$$
y+1\le x-y \to y:=x-y
$$

rAZOBRAVSHISX V TOM, CHEGO MY DOSTIGLI, MY VYNUZHDENY PRIJTI K 
DOSADNOMU ZAKLYUCHENIYU, CHTO SPOSOBOM, NAMECHENNYM V KONCE PREDYDUSHCHEJ 
GLAVY, NAM NE UDALOSX RESHITX SVOYU ZADACHU: IZ $P \and \non BB$ NE 
SLEDUET, CHTO $x=y$. (nAPRIMER, PRI $(x, y) = (5,7)$ ZNACHENIYA VSEH 
PREDOHRANITELEJ OKAZYVAYUTSYA LOZHNYMI.) mORALX SKAZANNOGO, 
RAZUMEETSYA, V TOM, CHTO NASHI SHESTX SHAGOV NE VSEGDA OBESPECHIVAYUT 
TAKOJ PUTX IZ NACHALXNOGO SOSTOYANIYA V KONECHNOE SOSTOYANIE, PRI 
KOTOROM $\abs(x-y)$ MONOTONNO UMENXSHAETSYA. pO|TOMU NAM NUZHNO 
ISPYTATX DRUGIE VOZMOZHNOSTI.

dLYA NACHALA ZAMETIM, CHTO NE POVREDIT NESKOLXKO USILITX USLOVIE $P2$: 
$$ 
P2=(x>0 \and y>0) 
$$
TAK KAK NACHALXNYE ZNACHENIYA $x$ I $y$ UDOVLETVORYAYUT TAKOMU USLOVIYU, 
I, KROME TOGO, NET NIKAKOGO SMYSLA V GENERACII RAVNOGO NULYU 
ZNACHENIYA, POSKOLXKU |TO ZNACHENIE MOZHET VOZNIKNUTX TOLXKO PRI 
VYCHITANII V SOSTOYANII, GDE $x=y$, T.E. KOGDA UZHE DOSTIGNUTO 
KONECHNOE SOSTOYANIE. nO |TO TOLXKO MALAYA MODIFIKACIYA; OSNOVNAYA 
MODIFIKACIYA DOLZHNA BYTX SVYAZANA S VVEDENIEM NOVOJ FUNKCII $t$, I YA 
PREDLAGAYU VZYATX TAKUYU FUNKCIYU $t$, KOTORAYA TOLXKO OGRANICHENA SNIZU 
V SILU INVARIANTNOSTI $P$. oCHEVIDNYM PRIMEROM YAVLYAETSYA
$$ 
t=x+y 
$$
mY VYYASNYAEM, CHTO DLYA ODNOVREMENNOGO PRISVAIVAIVANIYA
$$ 
\wdec ("x, y:=y, x", x+y) =F 
$$
I PO|TOMU ODNOVREMENNOE PRISVAIVANIE OTVERGAETSYA. 

mY NAHODIM DLYA PRISVAIVANIYA $x:= x+y$
$$ 
\wdec("x:=x+y", x+y) = (y< 0) 
$$
iSTINNOSTX |TOGO VYRAZHENIYA ISKLYUCHAETSYA ISTINNOSTXYU INVARIANTNOGO 
OTNOSHENIYA $P$, A SLEDOVATELXNO, TAKOE PRISVAIVANIE (NARYADU S 
PRISVAIVANIEM $y:=y+x$)  TAKZHE OTVERGAETSYA.

oDNAKO DLYA SLEDUYUSHCHEGO PRISVAIVANIYA $x:=x-y$ MY NAHODIM 
$$ 
\wdec("x:=x-y", x+y) = (y>0) 
$$
T. E. USLOVIE, KOTOROE, LOGICHESKI SLEDUET IZ USLOVIYA $P$ ( 
USILENNOGO MNOYU RADI |TOGO). 

oKRYLENNYE NADEZHDOJ, MY IZUCHAEM 
$$ 
\wp("x:=x-y", P) = (\nod(X, Y)=\nod(x-y, y) \and x-y > 0 \and y>0) 
$$
kRAJNIE CHLENY MOZHNO OTBROSITX, POTOMU CHTO ONI SLEDUYUT IZ $P$, I U 
NAS OSTAETSYA SREDNIJ CHLEN: ITAK, MY NAHODIM
\prg 
x>y\to x:=x-y 
\grp 
I
\prg
y>H\to y:=y-x 
\grp
i NA |TOM MY MOGLI BY PREKRATITX ISSLEDOVANIE, TAK KAK, KOGDA 
ZNACHENIYA OBOIH PREDOHRANITELEJ STANOVYATSYA LOZHNYMI, VYPOLNYAETSYA 
ZHELAEMOE NAMI OTNOSHENIE $x=y$. eSLI MY PRODOLZHIM, TO NAJDEM TRETIJ 
I CHETVERTYJ VARIANTY:
\prg
 x>y-x \and y>x\to x:=y-x 
\grp
 I
\prg
 y>x-y \and x>y\to y:= x-y 
\grp
NO NE YASNO, CHTO MOZHNO VYIGRATX IH VKLYUCHENIEM.

{\bf uPRAZHNENIYA.}

1. iSSLEDUJTE PRI TOM ZHE $P$ VYBOR $t=\max(x, y)$.

2. iSSLEDUJTE PRI TOM ZHE $P$ VYBOR $t=x+2*y$.

3. dOKAZHITE, CHTO PRI $X>0$ I $Y>0$ SLEDUYUSHCHAYA PROGRAMMA, OPERIRUYUSHCHAYA 
NAD CHETYRXMYA PEREMENNYMI,
\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{PECHATATX}((x+y)/2); \var{PECHATATX}((u+v)/2)
\grp
PECHATAET NAIBOLXSHIJ OBSHCHIJ DELITELX CHISEL h I u, A SLEDOM ZA NIM IH 
NAIMENXSHEE OBSHCHEE KRATNOE. (kONEC UPRAZHNENIJ.)

nAKONEC, ESLI NASH MALENXKIJ ALGORITM ZAPUSKAETSYA PRI PARE $(X,Y)$, 
KOTORAYA NE UDOVLETVORYAET PREDPOLOZHENIYU $X>0 \and Y>0$, TO 
PROIZOJDUT NEPRIYATNOSTI: ESLI $(X,Y)=(0, 0)$, TO POLUCHITSYA 
NEPRAVILXNYJ NULEVOJ REZULXTAT, A ESLI ODIN IZ ARGUMENTOV 
OTRICATELXNYJ, TO ZAPUSK PRIVEDET K BESKONECHNOJ RABOTE. eTOGO MOZHNO 
IZBEZHATX, NAPISAV
\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{PECHATATX}(x) 
\.{fi}
\grp

vKLYUCHIV TOLXKO ODIN VARIANT V KONSTRUKCIYU VYBORA, MY YAVNO VYRAZILI 
USLOVIYA, PRI KOTORYH OZHIDAETSYA RABOTA |TOJ MALENXKOJ PROGRAMMY. v 
TAKOM VIDE |TO HOROSHO ZASHCHISHCHENNYJ I DOVOLXNO SAMOSTOYATELXNYJ 
FRAGMENT, OBLADAYUSHCHIJ TEM PRIYATNYM SVOJSTVOM, CHTO POPYTKA ZAPUSKA 
VNE EGO OBLASTI OPREDELENIYA PRIVEDET K NEMEDLENNOMU OTKAZU.
\bye