\input style

\chapter{8 formal'noe rassmotrenie neskol'kih nebol'shih primerov}
v |TOJ GLAVE YA PROVEDU FORMALXNOE POSTROENIE NESKOLXKIH NEBOLXSHIH 
PROGRAMM DLYA RESHENIYA PROSTYH ZADACH. nE SLEDUET PONIMATX |TU GLAVU 
KAK PREDLOZHENIE STROITX PROGRAMMY TOLXKO TAK I NE INACHE: TAKOE 
PREDLOZHENIE BYLO BY DOVOLXNO  SMEHOTVORNYM. ya POLAGAYU, CHTO MNOGIM 
IZ MOIH CHITATELEJ ZNAKOMO BOLXSHINSTVO PRIMEROV, A ESLI NET, ONI, 
VEROYATNO, NE ZADUMYVAYASX SMOGUT NAPISATX LYUBUYU IZ |TIH PROGRAMM. 

sLEDOVATELXNO, POSTROENIE PROGRAMM PROVODITSYA ZDESX SOVSEM PO 
DRUGIM PRICHINAM. vO-PERVYH, |TO BLIZHE POZNAKOMIT NAS S FORMALIZMOM, 
RAZVITYM V PREDYDUSHCHIH GLAVAH. vO-VTORYH, UBEDIT NAS V TOM, CHTO PO 
KRAJNEJ MERE V PRINCIPE, FORMALIZM SPOSOBEN SDELATX YASNYM I 
SOVERSHENNO STROGIM TO, CHTO CHASTO OB�YASNYAETSYA PRI POMOSHCHI |NERGICHNOJ 
ZHESTIKULYACII. v-TRETXIH, MNOGIE IZ NAS NASTOLXKO HOROSHO ZNAYUT |TI 
PROGRAMMY, CHTO UZHE ZABYLI, KAKIM OBRAZOM DAVNYM-DAVNO MY UBEDILISX 
V IH PRAVILXNOSTI: V |TOM OTNOSHENII NASTOYASHCHAYA GLAVA NAPOMINAET 
NACHALXNYE UROKI PLANIMETRII, KOTORYE PO TRADICII POSVYASHCHAYUTSYA 
DOKAZATELXSTVU OCHEVIDNOGO. v-CHETVERTYH, MY MOZHEM SLUCHAJNO 
OBNARUZHITX, K SVOEMU UDIVLENIYU, CHTO MALENXKAYA ZNAKOMAYA ZADACHKA NE 
TAKAYA UZHE ZNAKOMAYA. nAKONEC, PROCESS POSTROENIYA PROGRAMM MOZHET 
PROLITX SVET NA OSUSHCHESTVIMOSTX, TRUDNOSTI I VOZMOZHNOSTI 
AVTOMATICHESKOGO SOSTAVLENIYA PROGRAMM ILI ISPOLXZOVANIYA MASHINY V 
PROCESSE PROGRAMMIROVANIYA. eTO MOZHET OKAZATXSYA VAZHNYM, DAZHE ESLI 
AVTOMATICHESKOE SOSTAVLENIE PROGRAMM NE VYZYVAET U NAS NI MALEJSHEGO 
INTERESA, POTOMU CHTO MOZHET POMOCHX NAM LUCHSHE OCENITX TU ROLX, 
KOTORUYU MOGUT ILI DOLZHNY IGRATX NASHI IZOBRETATELXSKIE SPOSOBNOSTI.

v MOIH PRIMERAH YA BUDU FORMULIROVATX TREBOVANIYA ZADACHI V FORMe "DLYA 
FIKSIROVANNYH $x$, $y$, \dots", CHTO YAVLYAETSYA SOKRASHCHENNOJ ZAPISXYU 
FORMY "DLYA LYUBYH ZNACHENIJ $x_0$, $y_0$, ... POSTUSLOVIE VIDA 
$x=x_0 \and y=y_0 \and \ldots$ DOLZHNO VYZYVATX PREDUSLOVIE, IZ 
KOTOROGO SLEDUET, CHTO $x=x_0 \and y=y_0 \and \ldots$". eTA 
SVYAZX MEZHDU POSTUSLOVIEM I PREDUSLOVIEM BUDET GARANTIROVANA TEM, 
CHTO MY BUDEM OTNOSITXSYA K TAKIM VELICHINAM KAK K "VREMENNYM 
KONSTANTAM"; ONI NE BUDUT VSTRECHATXSYA V LEVYH CHASTYAH OPERATOROV 
PRISVAIVANIYA.

{\sl pERVYJ PRIMER}

dLYA FIKSIROVANNYH $x$ I $y$ OBESPECHITX ISTINNOSTX OTNOSHENIYA $R(m)$. 
$$ 
(m=x \or m=y) \and m\ge x \and m\ge y 
$$

dLYA LYUBYH ZNACHENIJ $x$ I $y$ OTNOSHENIE $m=x$ MOZHET STATX ISTINNYM 
TOLXKO V REZULXTATE PRISVAIVANIYA $m:=x$; SLEDOVATELXNO, ISTINNOSTX 
$(m=x \or m=y)$ OBESPECHIVAETSYA TOLXKO VYPOLNENIEM LIBO $m:=H$, LIBO 
$m:=y$. v VIDE BLOK-SHEMY:
\pict{8.1}

vSE DELO V TOM, CHTO NA VHODE NUZHNO SDELATX PRAVILXNYJ VYBOR, 
KOTORYJ OBESPECHIT ISTINNOSTX $R(m)$ POSLE ZAVERSHENIYA VYCHISLENIJ. 
dLYA |TOGO MY "PROTALKIVAEM POSTUSLOVIE CHEREZ ALXTERNATIVY":
\pict{8.2}
I MY POLUCHILI PREDOHRANITELI! tAK KAK 
$$ 
R(x) = ((x=x \or x=y) \and x\ge x \and x\ge y) = (x\ge y) 
$$ 
 I
$$ 
R(y)= ((y=x \or y=y) \and y \ge x \and y\ge y) = (y \ge x) 
$$ 
MY PRIHODIM K NASHEMU RESHENIYU: 
\prg 
\.{if} x\ge y \to m:=x \wbox y\ge x \to m:=y \.{fi}
\grp
pOSKOLXKU $(x\ge y \or y \ge x)=T$, OTKAZA NIKOGDA NE PROIZOJDET 
(POPUTNO MY POLUCHILI DOKAZATELXSTVO SUSHCHESTVOVANIYA: DLYA LYUBYH 
ZNACHENIJ $x$ I $y$ SUSHCHESTVUET $m$, UDOVLETVORYAYUSHCHEE $R(m)$). 
pOSKOLXKU $(x\ge y \and y\ge x)\not=F$, NASHA PROGRAMMA NE 
OBYAZATELXNO DETERMINIROVANA. eSLI PERVONACHALXNO $x=y$, TO 
OKAZYVAETSYA NEOPREDELENNYM, KAKOE IZ DVUH PRISVAIVANIJ BUDET 
VYBRANO DLYA ISPOLNENIYA; TAKAYA NEDETERMINIROVANNOSTX SOVERSHENNO 
KORREKTNA, TAK KAK MY POKAZALI, CHTO VYBOR NE IMEET ZNACHENIYA.

{\sl zAMECHANIE.} eSLI BY SREDI DOSTUPNYH PRIMITIVOV IMELASX FUNKCIYA 
"$\max$", MY MOGLI BY NAPISATX PROGRAMMU $m:=\max(H,y)$, POSKOLXKU 
$R(\max(x,y))=T$. {\sl(kONEC ZAMECHANIYA.)}

pOLUCHENNAYA PROGRAMMA NE PROIZVODIT OCHENX SILXNOGO VPECHATLENIYA; S 
DRUGOJ STORONY, MY VIDIM, CHTO V PROCESSE VYVODA PROGRAMMY IZ 
POSTUSLOVIYA NA DOLYU NASHEJ IZOBRETATELXNOSTI POCHTI NICHero NE 
OSTALOSX.

{\sl vTOROJ PRIMER}

dLYA FIKSIROVANNOGO ZNACHENIYA $n$ $(n>0)$ ZADANA FUNKCIYA $f(i)$ DLYA 
$0\le i< n$. oBESPECHITX ISTINNOSTX $R$:
$$
 0 \le k< n \and (\forall i:0 \le i<n:f(k)\ge f(i)) 
$$
pOSKOLXKU NASHA PROGRAMMA DOLZHNA RABOTATX PRI LYUBOM  POLOZHITELXNOM 
ZNACHENII $n$, TRUDNO SEBE PREDSTAVITX, KAK MOZHNO OBESPECHITX 
ISTINNOSTX $R$, NE PRIBEGAYA K POMOSHCHI CIKLA; PO|TOMU MY ISHCHEM 
OTNOSHENIE $P$, KOTOROE LEGKO MOZHNO SDELATX ISTINNYM  V NACHALE 
PROGRAMMY I TAKOE, CHTO V KONCE $(P \and \non BB)\Rightarrow R$.  
sLEDOVATELXNO, OTYSKIVAYA $P$, MY ISHCHEM OTNOSHENIE, BOLEE SLABOE, CHEM 
$R$; INACHE GOVORYA, MY HOTIM POLUCHITX OBOBSHCHENIE NASHEGO KONECHNOGO 
SOSTOYANIYA. sTANDARTNYJ SPOSOB OBOBSHCHENIYA OTNOSHENIYA --- |TO ZAMENA 
KONSTANTY PEREMENNOJ (VOZMOZHNO, V OGRANICHENNOM INTERVALE), I ZDESX 
MOJ OPYT PODSKAZYVAET MNE, CHTO NUZHNO  ZAMENITX  KONSTANTU $n$ NOVOJ 
PEREMENNOJ, NAPRIMER $j$, I VZYATX V KACHESTVE $r$
$$
 0\le k<j\le n \and (\forall i:0\le i<j:f(k)\ge f(i))
$$

GDE USLOVIE $j\le n$ DOBAVLENO DLYA TOGO, CHTOBY OBLASTX 
OPREDELENIYA FUNKCII $f$ BYLA KONECHNOJ. tEPERX, IMEYA TAKOE
OBOBSHCHENIE, MY LEGKO POLUCHAEM
$$
(P \and j =n) \Rightarrow R
$$

chTOBY PODTVERDITX VOZMOZHNOSTX ISPOLXZOVANIYA TAKIM
OBRAZOM VYBRANNOGO r, MY DOLZHNY RASPOLAGATX LEGKIM 
SREDSTVOM DLYA OBESPECHENIYA ISTINNOSTI r V NACHALE PROGRAMMY.
pOSKOLXKU
$$
(k=0\and j=1) \Rightarrow P
$$
MY OTVAZHIVAEMSYA PREDLOZHITX SLEDUYUSHCHUYU STRUKTURU DLYA
NASHEJ PROGRAMMY (KOMMENTARII DAYUTSYA V SKOBKAH):
\prg
k,j:=0, 1 \{P STALO ISTINNYM\};
\.{do} j\not= n \to NEKIJ SHAG K j=n PRI INVARIANTNOSTI P \.{od}
\{R STALO ISTINNYM\}
\grp

sNOVA MOJ OPYT PODSKAZYVAET MNE VYBRATX V KaCHESTVE
MONOTONNO UBYVAYUSHCHEJ FUNKCII $t$  TEKUSHCHEGO SOSTOYANIYA FUNKCIYU
$t=(n-j)$, KOTORAYA I V SAMOM DELE TAKOVA, CHTO $r\Leftarrow(t\ge 0)$.
chTOBY GARANTIROVATX MONOTONNOE UBYVANIE $t$, YA PREDLAGAYU
UVELICHIVATX $j$ NA 1, POSLE CHEGO MY MOZHEM NAPISATX
$$
\displaylines{
\wp("j:=j+1", P)=\cr
0\le k<j+1\le n \and(\forall i:0\le i<j+1:f(k)\ge f(i))=\cr
0\le k<j+1\le n \and(\forall i:0\le i<j : f(k)\ge f(i))\and f(k)\ge f(j)\cr
}
$$

pERVYE DVA CHLENA SLEDUYUT IZ $P \and j\not=n$  (POTOMU CHTO
$(j\le n \and j\not=n)\Rightarrow (j+1\le n)$, I IMENNO PO|TOMU MY RESHILI UVELICHITX 
$j$  TOLXKO NA 1). sLEDOVATELXNO,
$$
(P \and j\not=n \and f(k)\ge f(j)) \Rightarrow  \wp ("j:=j+1",P)
$$
I MY MOZHEM ISPOLXZOVATX POSLEDNEE USLOVIE V KACHESTVE
PREDOHRANITELYA. pROGRAMMA
\prg
k, j:=0,1;
\.{do} j \NE n\to \.{if} f(k)\ge f(j)\to j:=j+1 \.{fi} \.{od}
\grp
DEJSTVITELXNO DAST PRAVILXNYJ OTVET, ESLI ONA ZAVERSHITSYA
NORMALXNO. oDNAKO NORMALXNOE ZAVERSHENIE NE GARANTIROVANO,
POSKOLXKU KONSTRUKCIYA VYBORA MOZHET PRIVESTI K OTKAZU --- I
|TO DEJSTVITELXNO TAK I BUDET, ESLI $k=0$ NE UDOVLETVORYAET $R$.
eSLI NEVERNO, CHTO $f(k) \ge f(i)$, MY MOZHEM SDELATX |TO OTNOSHENIE
VERNYM PRI POMOSHCHI PRISVAIVANIYA $k:=j$ I PRODOLZHITX
NASHI ISSLEDOVANIYA:
$$
\displaylines{
\wp("k,j:=j,j+1", P)=\cr
0\le j<j+1\le n \and (\forall i: 0\le i<j+1:f(j)\ge f(i))=\cr
0\le j<j+1\le n \and (\forall i:0\le i<j:f(j)\ge f(i))\cr
}
$$
s OGROMNYM OBLEGCHENIEM MY ZAMECHAEM, CHTO
$$
(P\and j\not=n\and f(k)\le f(j))\Rightarrow \wp("k,j:=j,j+1",P)
$$

I SLEDUYUSHCHAYA PROGRAMMA BUDET RABOTATX, NE PODVERGAYASX OPASNOSTI 
OTKAZA.
\prg
k, j=0,1;
\.{do} j\NE n\to \.{if} f(k)\GE f(j)\to j:=j+1
\wbox f(k)\le f(j) \to k,j:=j,j+1 \.{fi} \.{od}
\grp

sLEDUET SDELATX NESKOLXKO PRIMECHANIJ. pERVOE: POSKOLXKU
PREDOHRANITELI KONSTRUKCII VYBORA NE OBYAZATELXNO ISKLYUCHAYUT
DRUG DRUGA, PROGRAMMA TAIT V SEBE VNUTRENNYUYU NEDETERMINIROVANNOSTX
TOGO ZHE TIPA, CHTO I V PERVOM PRIMERE. eTA 
NEDETERMIROVANNOSTX MOZHET PROYAVITXSYA I VNESHNE. fUNKCIYA
$f$ MOGLA OKAZATXSYA TAKOJ, CHTO KONECHNOE ZNACHENIE $k$ NEODNOZNACHNO;
V |TOM SLUCHAE NASHA PROGRAMMA MOZHET VYRABOTATX LYUBOE
DOPUSTIMOE ZNACHENIE!

vTOROE PRIMECHANIE: TO, CHTO MY POSTROILI PRAVILXNUYU PROGRAMMU,
NE OZNACHAET, CHTO MY SPRAVILISX S ZADACHEJ. pROGRAMMIROVANIE
V RAVNOJ STEPENI YAVLYAETSYA KAK MATEMATICHESKOJ, TAK I INZHENERNOJ
DISCIPLINOJ; MY DOLZHNY ZABOTITXSYA O PRAVILXNOSTI V TOJ
ZHE MERE, KAK SKAZHEM, I OB |FFEKTIVNOSTI. iSHODYA IZ
PREDPOLOZHENIYA, CHTO NA VYCHISLENIE ZNACHENIYA FUNKCII $f$ 
DLYA DANNOGO ARGUMENTA ZATRACHIVAETSYA OTNOSITELXNO MNOGO VREMENI,
HOROSHIJ INZHENER DOLZHEN OBRATITX VNIMANIE NA TO, CHTO V
PROGRAMME, PO VSEJ VEROYATNOSTI, BUDET MNOGOKRATNO VYCHISLYATXSYA
$f(k)$ DLYA ODNOGO I TOGO ZHE ZNACHENIYA $k$. v |TOM SLUCHAE
REKOMENDUETSYA POJTI NA SDELKU I POZHERTVOVATX NEKOTORYM
OB�EMOM PAMYATI, CHTOBY S|KONOMITX CHASTX VREMENI, ZATRACHIVAEMOGO
NA VYCHISLENIE. nO PRI |TOM NASHI USILIYA, NAPRAVLENNYE NA
POVYSHENIE |FFEKTIVNOSTI PROGRAMMY I UMENXSHENIE
ZATRAT VREMENI, NI V KOEJ MERE NE DOLZHNY SLUZHITX IZVINENIEM
ZA VNESENIE BESPORYADKA V PROGRAMMU. (eTO OCHEVIDNAYA VESHCHX, NO YA HOCHU
PODCHERKNUTX |TU MYSLX, POTOMU CHTO OCHENX CHASTO
ZAPUTANNOSTX PROGRAMMY OPRAVDYVAETSYA SSYLKOJ NA
|FFEKTIVNOSTX. oDNAKO PRI BLIZHAJSHEM RASSMOTRENII TAKOE
OPRAVDANIE VSEGDA OKAZYVAETSYA NEOBOSNOVANNYM, DOLZHNO BYTX,
POTOMU, CHTO ZAPUTANNOSTX PROGRAMMY VSEGDA NEOPRAVDANNA.)
chTOBY AKKURATNO REALIZOVATX OBMEN VREMENI VYCHISLENIJ NA
PAMYATX, MOZHNO VOSPOLXZOVATXSYA METODOM VVEDENIYA ODNOJ ILI
NESKOLXKIH DOPOLNITELXNYH PEREMENNYH, CHXE ZNACHENIE MOZHNO
ISPOLXZOVATX, TAK KAK SOHRANYAETSYA INVARIANTNYM NEKOTOROE
OTNOSHENIE. v DANNOM PRIMERE BYLO ZAMECHENO, CHTO VOZMOZHNY
CHASTYE POVTORNYE VYCHISLENIYA f(k) DLYA ODNOGO I TOGO ZHE $k$, 
A |TO NAVODIT NA MYSLX O VVEDENII DOPOLNITELXNOJ 
PEREMENNOJ, SKAZHEM $max$, I RASSHIRENII INVARIANTNOGO OTNOSHENIYA
ZA SCHET DOPOLNITELXNOGO CHLENA
$$
max=f(k)
$$

eTO OTNOSHENIE DOLZHNO STATX ISTINNYM, KOGDA k  POLUCHIT
NACHALXNOE ZNACHENIE, I DOLZHNO SOHRANYATXSYA INVARIANTNYM (PRI
POMOSHCHI YAVNOGO PRISVAIVANIYA ZNACHENIYA PEREMENNOJ $max$) 
POSLE IZMENENIYA k. mY PRIHODIM K SLEDUYUSHCHEJ PpoGpaMME:
\prg
k,j, max:=0,1,f(0);
\.{do} j \NE n\to \.{if} max \GE f(j) \to j:=j+1
\wbox max\LE f(j) \to k, j, max:=j, j+1, f(j) \.{fi} \.{od}
\grp

vEROYATNO, |TA PROGRAMMA GORAZDO BOLEE |FFEKTIVNA, CHEM
NASHA PREDYDUSHAYA VERSIYA, v TAKOM SLUCHAE HOROSHIJ INZHENER
NA |TOM NE OSTANOVITSYA, POTOMU CHTO TEPERX ON OBNARUZHIT, CHTO
MOG BY RASPORYADITXSYA POVTORNYMI VYCHISLENIYAMI $f(j)$ DLYA
ODNOGO I TOGO ZHE $j$. dLYA |TOGO MOZHNO VVESTI DOPOLNITELXNUYU
PEREMENNUYU, SKAZHEM $h$, I OBESPECHITX INVARIANTNOSTX
$$
h=f(j)
$$

oDNAKO MY Ne MOZHEM SDELATX |TO NA TOM ZHE GLOBALXNOM
UROVNE, KAK DLYA NASHEGO PREDYDUSHCHEGO CHLENA: ZNACHENIE $j=n$ NE
ISKLYUCHENO, A PRI |TOM ZNACHENIE $f(j)$ NE OBYAZATELXNO OPREDELENO.
sLEDOVATELXNO, ISTINNOSTX OTNOSHENIYA $h=f(j)$ DOLZHNA
ZANOVO OBESPECHIVATXSYA POSLE KAZHDOJ PROVERKI, POKAZYVAYUSHCHEJ,
CHTO $j\not=n$, PO ZAVERSHENII VNESHNEJ OHRANYAEMOJ KOMANDY (TAK
SKAZATX, "KAK RAZ PERED od") MY IMEEM $h=f(j-1)$, NO NAS |TO
NE DOLZHNO BESPOKOITX, I PUSTX VSE OSTAETSYA TAK, KAK ESTX.
\prg
k, j, max:= 0, 1, f(0);
\.{do} j\NE n\to h:=f(j);
         \.{if} max\GE h \to j:=j+1
\wbox max \LE h \to k, j, max:=j, j+1, h \.{fi} \.{od}
\grp

pOSLEDNEE PRIMECHANIE KASAETSYA NE STOLXKO NASHEGO RESHENIYA
ZADACHI, SKOLXKO NASHIH SOOBRAZHENIJ O PODHODE K RESHENIYU.
mY GOVORILI O MATEMATICHESKOM PODHODE, MY GOVORILI OB
INZHENERNOM PODHODE I PROVELI RAZDELENIE MEZHDU |TIMI PODHODAMI,
SOSREDOTOCHIVAYA VNIMANIE TO NA ODNOM, TO NA DRUGOM ASPEKTE.
hOTYA RAZDELENIE PODHODOV ABSOLYUTNO NEOBHODIMO,
KOGDA RECHX IDET O BOLEE SLOZHNYH ZADACHAH, YA DOLZHEN PODCHERKNUTX,
CHTO, SOSREDOTOCHIVAYA VNIMANIE NA ODNOM IZ ASPEKTOV, NE
SLEDUET POLNOSTXYU IGNORIROVATX DRUGIE ASPEKTY. rAZRABATYVAYA
MATEMATICHESKUYU CHASTX PROEKTA, MY DOLZHNY POMNITX, CHTO DAZHE
MATEMATICHESKI PRAVILXNAYA PROGRAMMA MOZHET POGIBNUTX,
ESLI ONA PLOHA S INZHENERNOJ TOCHKI ZRENIYA. aNALOGICHNO, OSUSHCHESTVLYAYA
"SDELKU" MEZHDU PAMYATXYU I VREMENEM, MY DOLZHNY DELATX
|TO AKKURATNO I SISTEMATICHESKI, CHTOBY PO NERYASHLIVOSTI
NE VNESTI OSHIBOK V PROGRAMMU; KROME TOGO, HOTYA PREDVARITELXNO
BYL PROVEDEN MATEMATICHESKIJ ANALIZ, MY DOLZHNY
K TOMU ZHE DOSTATOCHNO HOROSHO RAZBIRATXSYA V ZADACHE, CHTOBY
SUDITX O TOM, PRIVEDUT LI PREDPOLAGAEMYE IZMENENIYA K ZNACHITELXNOMU
ULUCHSHENIYU PROGRAMMY.

{\sl zAMECHANIE.} dO TOGO KAK YA NACHAL POLXZOVATXSYA |TIMI FORMALXNYMI
POSTROENIYAMI, YA VSEGDA ISPOLXZOVAL "$j<n$" V KACHESTVE 
PREDOHRANITELYA V |TOJ KONSTRUKCII POVTORENIYA, TEPERX YA
DOLZHEN OTUCHIT�SYA OT |TOJ PRIVYCHKI, TAK KAK V SLUCHAE, PODOBNOM
DANNOMU, KONECHNO, PREDPOCHTITELXNEE PREDOHRANITELX "$j\not= n$".
dLYA |TOGO IMEYUTSYA DVE PRICHINY. pREDOHRANITELX "$j\not=n$"
POZVOLYAET NAM SDELATX VYVOD, CHTO PO ZAVERSHENII PROGRAMMY 
$j=n$, NE SSYLAYASX PRI |TOM NA INVARIANTNOE OTNOSHENIE $P$;
TEM SAMYM UPROSHCHAETSYA DISKUSSIYA O TOM, CHTO DAET NAM
VSYA KONSTRUKCIYA V CELOM PO SRAVNENIYU S PREDOHRANITELEM "$j<n$".
gORAZDO VAZHNEE, ODNAKO, CHTO PREDOHRANITELX "$j\not=n$"
STAVIT ZAVERSHENIE PROGRAMMY V ZAVISIMOSTX OT (CHASTI) INVARIANTNOGO
OTNOSHENIYA, A IMENNO $j\le n$, I PO|TOMU EMU SLEDUET
OTDATX PREDPOCHTENIE, TAK KAK EGO ISPOLXZOVANIE PRIVEDET K
USILENIYU KONSTRUKCII. eSLI V REZULXTATE VYPOLNENIYA $j:=j+1$
ZNACHENIE $j$ TAK VOZRASTET, CHTO STANET SPRAVEDLIVYM OTNOSHENIE
$j>n$, PREDOHRANITELX "$j<n$" NE PODNIMET TREVOGU, TOGDA
KAK PREDOHRANITELX "$j\not=n$" PO KRAJNEJ MERE NE DOPUSTIT
NORMALXNOGO ZAVERSHENIYA. tAKOJ ARGUMENT PREDSTAVLYAETSYA VPOLNE
VESOMYM, DAZHE ESLI NE PRINIMATX VO VNIMANIE SBOJ MASHINY.
pUSTX V POSLEDOVATELXNOSTI $x_0$, $x_1$, $x_2$, \dots ZNACHENIE $x_0$ ZADAETSYA,
A ZNACHENIE $x_i$ DLYA $i>0$ OPREDELYAETSYA KAK $x_i=f(x_{i-1})$, GDE $f$ ---
NEKOTORAYA VYCHISLIMAYA FUNKCIYA. bUDEM VNIMATELXNO I TOCHNO
SLEDITX ZA TEM. CHTOBY SOHRANYALOSX INVARIANTNYM OTNOSHENIE
$X=x_i$. pREDPOLOZHIM, CHTO V PROGRAMME IMEETSYA MONOTONNO
VOZRASTAYUSHCHAYA PEREMENNAYA $n$, TAKAYA, CHTO DLYA NEKOTORYH 
ZNACHENIJ $n$ NAS INTERESUYUT $x_n$. pRI USLOVII CHTO $n\ge i$, MY VSEGDA
MOZHEM SDELATX ISTINNYM OTNOSHENIE $X=x_n$ PRI POMOSHCHI
\prg
\.{do} i\NE n \TO i, X:=i+1, f(X) \.{od}
\grp

eSLI ZHE OTNOSHENIE $n\ge i$ NE OBYAZATELXNO IMEET MESTO
(MOZHET BYTX, POSLEDUYUSHCHIE IZMENENIYA V PROGRAMME PRIVELI K
TOMU, CHTO V PROCESSE VYCHISLENIJ $n$ BUDET NE TOLXKO VOZRASTATX),
PRIVEDENNAYA VYSHE KONSTRUKCIYA (K SCHASTXYU!) NE PRIDET K ZAVERSHENIYU,
V TO VREMYA KAK KONSTRUKCIYA
\prg
\.{do} i<n\TO i, X:= i+1, f(X) \.{od}
\grp
NE OBESPECHIT ISTINNOSTI OTNOSHENIYA $X=x_n$. mORALX |TOJ
ISTORII TAKOVA, CHTO PRI PROCHIH RAVNYH USLOVIYAH MY DOLZHNY
VYBIRATX NASHI PREDOHRANITELI KAK MOZHNO BOLEE SLABYMI.
{\sl (kONEC ZAMECHANIYA.)}

tRETIJ PRIMER

dLYA FIKSIROVANNYH $a(a\ge 0)\hbox{ I }d(d>0)$ TREBUETSYA
OBESPECHITX ISTINNOSTX R:
$$
0\le r< d \and d|(a-r)
$$
(zDESX VERTIKALXNAYA CHERTA "$|$" ZAMENYAET SOBOJ SLOVA
"YAVLYAETSYA DELITELEM".) iNACHE GOVORYA, NAM TREBUETSYA VYCHISLITX
NAIMENXSHIJ NEOTRICATELXNYJ OSTATOK $r$, POLUCHENNYJ V REZULXTATE
DELENIYA $a$ NA $d$. chTOBY |TA ZADACHA DEJSTVITELXNO BYLA ZADACHEJ,
MY DOLZHNY OGRANICHITX ISPOLXZOVANIE ARIFMETICHESKIH
OPERACIJ TOLXKO OPERACIYAMI SLOZHENIYA I VYCHITANIYA. pOSKOLXKU
USLOVIE $d|(a-r)$ VYPOLNYAETSYA PRI $r=a$ I PRI |TOM, TAK KAK
$a\ge 0$, VERNO, CHTO $0\le r$, PREDLAGAETSYA VYBRATX V KACHESTVE
INVARIANTNOGO OTNOSHENIYA $P$:
$$
0 \le r \and d|(a-r)
$$

v KACHESTVE FUNKCII $t$, UBYVANIE KOTOROJ DOLZHNO 
OBESPECHITX ZAVERSHENIE RABOTY PROGRAMMY, MY VYBIRAEM SAMO $r$.
pOSKOLXKU IZMENENIE $r$ DOLZHNO BYTX TAKIM, CHTOBY NEIZMENNO
VYPOLNYALOSX USLOVIE $d|(a-r)$, $r$ MOZHNO IZMENYATX TOLXKO NA CHISLO,
KRATNOE $d$, NAPRIMER NA SAMO $d$. tAKIM OBRAZOM, NAM, KAK
OKAZALOSX, PREDLAGAETSYA VYCHISLITX
$$
\wp("r:=r-d", P) \and \wdec("r:=r-d", r)=0\le r-d \and d|(a-r+d) \and d>0
$$

pOSKOLXKU CHLEN $d>0$ MOZHNO BYLO BY DOBAVITX K INVARIANTNOMU
OTNOSHENIYU $P$, OBOSNOVANIYA TREBUET TOLXKO PERVYJ CHLEN;
MY NAHODIM SOOTVETSTVUYUSHCHIJ PREDOHRANITELX "$r\ge d$"
I PROBUEM SOSTAVITX TAKUYU PROGRAMMU:
\prg
\.{if} a \GE 0 \and d>0 \TO
  r:=a;
  \.{do} r \GE d \TO r:=r-d \.{od}
\.{fi}
\grp

pO ZAVERSHENII PROGRAMMY STALO ISTINNYM OTNOSHENIE
$P\and\non r\ge d$, IZ CHEGO SLEDUET ISTINNOSTX $R$, I, TAKIM OBRAZOM,
ZADACHA RESHENA.

pREDPOLOZHIM TEPERX, CHTO NAM, KROME TOGO, POTREBOVALOSX BY
PRISVOITX $q$  TAKOE ZNACHENIE, CHTOBY PO OKONCHANII PROGRAMMY
BYLO BY TAKZHE VERNO, CHTO
$$
a=d *q+r
$$
INACHE GOVORYA, TREBUETSYA NAJTI NE TOLXKO OSTATOK, NO I CHASTNOE.
pOPROBUEM DOBAVITX |TOT CHLEN K NASHEMU INVARIANTNOMU OTNOSHENIYU.
pOSKOLXKU
$$
(a=d* q+r)\Rightarrow (a=d*(q+1)+(r-d))
$$
MY PRIHODIM K PROGRAMME
\prg
\.{if} a \GE 0 \and d>0 \TO
 q, r:=0, a;
 \.{do} r \GE d \to q,  r:=q+1, r-d \.{od}
\.{fi}
\grp
nA VYPOLNENIE PRIVEDENNYH VYSHE PROGRAMM BUDET, KONECHNO,
ZATRACHIVATXSYA OCHENX MNOGO VREMENI, ESLI CHASTNOE VELIKO. mOZHEM
LI MY SOKRATITX |TO VREMYA? oCHEVIDNO, |TOGO MOZHNO DOBITXSYA,
ESLI UMENXSHATX $r$ NA VELICHINU, KRATNUYU I BOLXSHUYU $d$. vVODYA
DLYA |TOJ CELI NOVUYU PEREMENNUYU, SKAZHEM $dd$, MY POLUCHAEM
USLOVIE, KOTOROE DOLZHNO NEIZMENNO VYPOLNYATXSYA NA PROTYAZHENII
VSEJ Ra6oTY PROGRAMMY:
$$
d|dd \and dd \GE d
$$

mY MOZHEM USKORITX NASHU PERVUYU PROGRAMMU, ZAMENIV
"$r:=r-d$" UMENXSHENIEM, VOZMOZHNO POVTORNYM, $r$ NA $dd$,
PREDOSTAVLYAYA V TO ZHE VREMYA VOZMOZHNOSTX $dd$, PERVONACHALXNO 
RAVNOMU $d$, DOVOLXNO BYSTRO VOZRASTATX, NAPRIMER KAZHDYJ RAZ
UDVAIVAYA $dd$. tOGDA MY PRIHODIM K SLEDUYUSHCHEJ PROGRAMME:
\prg
\.{if} a \ge 0 \and d>0\to
  r:=a;
  \.{do} r\ge d \to
    dd:=d;
    \.{do} r\ge dd\to r:=r-dd; dd:=dd+dd \.{od}
  \.{od}
\.{fi}
\grp
yaSNO, CHTO OTNOSHENIE $0\le r \and d|(a-r)$ SOHRANYAETSYA
INVARIANTNYM, I PO|TOMU PROGRAMMA OBESPECHIT ISTINNOSTX $R$,
ESLI ONA ZAVERSHITSYA NORMALXNO, NO TAK LI |TO? kONECHNO, TAK,
POSKOLXKU VNUTRENNIJ CIKL, KOTORYJ ZAVERSHAETSYA PRI $dd>0$,
VOZBUZHDAETSYA TOLXKO PRI NACHALXNYH SOSTOYANIYAH, UDOVLETVORYAYUSHCHIH
USLOVIYU $r\ge dd$, I PO|TOMU UMENXSHENIE $r:=r-dd$
VYPOLNYAETSYA PO KRAJNEJ MERE ODIN RAZ DLYA KAZHDOGO POVTORENIYA
VNESHNEGO CIKLA.

nO TAKOE RASSUZHDENIE (HOTYA I DOSTATOCHNO UBEDITELXNOE!)
YAVLYAETSYA VESXMA NEFORMALXNYM, A POSKOLXKU V |TOJ GLAVE MY
GOVORIM O FORMALXNOM POSTROENII PROGRAMM, MY MOZHEM POPROBOVATX
SFORMULIROVATX I DOKAZATX TEOREMU, KOTOROJ INTUITIVNO 
VOSPOLXZOVALISX.

pUSTX IF, DO I vv PONIMAYUTSYA V OBYCHNOM SMYSLE, I
$P$ --- |TO OTNOSHENIE, SOHRANYAYUSHCHEESYA INVARIANTNYM, T.E.
$$
(P \and BB)\Rightarrow \wp (IF, P) \qquad\hbox{DLYA VSEH SOSTOYANIJ}
\eqno(1)
$$
I PUSTX $t$ --- CELOCHISLENNAYA FUNKCIYA, TAKAYA, CHTO DLYA LYUBOGO 
ZNACHENIYA $t_0$ I DLYA VSEH SOSTOYANIJ
$$
(P \and BB \and t\le t_0+1)\to \wp(IF, t\le t_0)
\eqno(2)
$$
ILI, CHTO TO ZHE,
$$
(P \and BB)\Rightarrow \wdec(IF,t) \qquad\hbox{DLYA VSEH SOSTOYANIJ}
\eqno(3)
$$

tOGDA DLYA LYUBOGO ZNACHENIYA $t_0$ I DLYA VSEH SOSTOYANIJ
$$
(P \and BB \and \wp(DO, T) \and t\le t_0+1) \Rightarrow \wp (DO,t\le t_0)
\eqno(4)
$$
ILI, CHTO TO ZHE,
$$
(P\and BB\and\wp(DO,T))\Rightarrow \wdec(DO,t)
\eqno(5)
$$
v SLOVESNOJ FORMULIROVKE: ESLI SOHRANYAEMOE INVARIANTNYM
OTNOSHENIE $P$ GARANTIRUET, CHTO KAZHDAYA VYBRANNAYA DLYA ISPOLNENIYA
OHRANYAEMAYA KOMANDA VYZYVAET DEJSTVITELXNOE UMENXSHENIE $t$,
TO KONSTRUKCIYA POVTORENIYA VYZOVET DEJSTVITELXNOE UMENXSHENIE
$t$, ESLI ONA NORMALXNO ZAVERSHITSYA POSLE PO KRAJNEJ MERE
ODNOGO VYPOLNENIYA KAKOJ-LIBO OHRANYAEMOJ KOMANDY.
tEOREMA NASTOLXKO OCHEVIDNA, CHTO BYLO BY DOSADNO, ESLI BY EE
DOKAZATELXSTVO OKAZALOSX TRUDNYM, NO, K SCHASTXYU, |TO NE TAK.
mY POKAZHEM, CHTO IZ (1) I (2) SLEDUET, CHTO DLYA LYUBOGO ZNACHENIYA
$t_0$ I DLYA VSEH SOSTOYANIJ
$$
(P \and BB and H_k(T)) \and t\le t_0+1)\Rightarrow  H_k (t \le t_0)   
\eqno (6)
$$
DLYA VSEH $k \ge 0$. eTO SPRAVEDLIVO DLYA $k=0$, POSKOLXKU 
$(BB\and H_0(T))=F$, I, ISHODYA IZ PREDPOLOZHENIYA, CHTO (6)
SPRAVEDLIVO DLYA $k=K$, MY DOLZHNY POKAZATX, CHTO (6) SPRAVEDLIVO
I DLYA $k=K+1$.
$$
\displaylines{
(P \and BB \and H_{K+1}(T) \and t \le t_0+1)\cr
\eqalign{
&\Rightarrow \wp(IF, P) \and \wp(IF, H_K (T)) \and \wp(lF, t\le t_0)\cr
&=\wp(IF, P \and H_K(T) \and t\le t_0)\cr
&\Rightarrow \wp ((IF, (P \and BB \and H_K(T) \and t\le t0+1) \or (t\le t_0  \and \non BB))\cr
&\Rightarrow \wp(IF, H_K(t\le t_0) \or H_0(t\le t_0))\cr
&=\wp(IF, H_K(t\le t_0))\cr
&\Rightarrow \wp(IF, H_K(t\le t_0)) \or H_0(t\le t_0)\cr
&=H_{K+1}(t\le t_0)\cr
}\cr
}
$$

pERVAYA IMPLIKACIYA SLEDUET IZ (1), OPREDELENIYA 
$H_{K+1}(T)$ I (2);
RAVENSTVO V TRETXEJ STROKE OCHEVIDNO; IMPLIKACIYA V CHETVERTOJ
STROKE VYVODITSYA PRI POMOSHCHI PRISOEDINENIYA
$(BB \or\non BB)$ I POSLEDUYUSHCHEGO OSLABLENIYA OBOIH CHLENOV;
IMPLIKACIYA V PYATOJ STROKE SLEDUET IZ (6) PRI $k=K$ I OPREDELENIYA
$H_0(t\le t_0)$; OSTALXNOE PONYATNO. tAKIM OBRAZOM, MY DOKAZALI
SPRAVEDLIVOSTX (6) DLYA VSEH $k>0$, A OTSYUDA NEMEDLENNO
VYTEKAYUT (4) I (5).

{\bf uPRAZHNENIE}

iZMENITE NASHU VTORUYU PROGRAMMU TAKIM OBRAZOM, CHTOBY
ONA VYCHISLYALA TAKZHE I CHASTNOE, I DAJTE FORMALXNOE DOKAZATELXSTVO
PRAVILXNOSTI VASHEJ PROGRAMMY. {\sl(kONEC UPRAZHNENIYA.)}

pREDPOLOZHIM TEPERX, CHTO IMEETSYA MALENXKOE CHISLO,
SKAZHEM 3, NA KOTOROE NAM POZVOLENO UMNOZHATX I DELITX, I CHTO
|TI OPERACII VYPOLNYAYUTSYA DOSTATOCHNO BYSTRO, TAK CHTO IMEET
SMYSL VOSPOLXZOVATXSYA IMI. bUDEM OBOZNACHATX PROIZVEDENIE
"$m*3$" (ILI "$3*m$") I CHASTNOE "$m/3$"; POSLEDNEE VYRAZHENIE
BUDET ISPOLXZOVATXSYA TOLXKO PRI USLOVII, CHTO PERVONACHALXNO
SPRAVEDLIVO $3|m$. (mY VEDX RABOTAEM S CELYMI CHISLAMI, NE
TAK LI?)

i OPYATX MY PYTAEMSYA OBESPECHITX ISTINNOSTX ZHELAEMOGO
OTNOSHENIYA $R$ PRI POMOSHCHI KONSTRUKCII POVTORENIYA, DLYA KOTOROJ
INVARIANTNOE OTNOSHENIE $P$ VYVODITSYA PUTEM ZAMENY
KONSTANTY PEREMENNOJ. zAMENYAYA KONSTANTU $d$ PEREMENNOJ $dd$, CHXI
ZNACHENIYA BUDUT PREDSTAVLYATXSYA TOLXKO V VIDE $d * (\hbox{ STEPENX }3)$,
MY PRIHODIM K INVARIANTNOMU OTNOSHENIYU $P$:
$$
0\le r < dd \and dd \ (A-r) \and (\exists i:i\ge 0:dd=d*3^i)
$$

mY OBESPECHIM ISTINNOSTX |TOGO OTNOSHENIYA I ZATEM,
ZAMENYAYA EGO INVARIANTNYM, POSTARAEMSYA DOSTICHX SOSTOYANIYA,
PRI KOTOROM $d=dd$.

chTOBY OBESPECHITX ISTINNOSTX $P$, NAM PONADOBITSYA ESHCHE ODNA
KONSTRUKCIYA POVTORENIYA: SNACHALA MY OBESPECHIM ISTINNOSTX
OTNOSHENIYA
$$
0\le r \and dd \ (a-r) \and (\exists i:i\ge 0:dd=d*3^i)
$$
A ZATEM BUDEM UVELICHIVATX $dd$, POKA EGO ZNACHENIE NE STANET 
DOSTATOCHNO BOLXSHIM I TAKIM, CHTO $r<dd$. pOLUCHIM SLEDUYUSHCHUYU
PROGRAMMU:
\prg
\.{if} a\GE 0 \and d>0 \TO
        r, dd := a, d;
\.{do} r\GE dd \TO dd:=dd*3 \.{od};
\.{do} dd \NE d\TO dd:=dd/3;
 \.{do} r\GE dd\TO r:=r-dd \.{od}
\.{od}
\.{fi}
\grp

{\bf uPRAZHNENIE}

iZMENITE PRIVEDENNUYU VYSHE PROGRAMMU TAKIM OBRAZOM,
CHTOBY ONA VYCHISLYALA TAKZHE I CHASTNOE, I DAJTE FORMALXNOE
DOKAZATELXSTVO PRAVILXNOSTI VASHEJ PROGRAMMY, eTO 
DOKAZATELXSTVO DOLZHNO NAGLYADNO POKAZYVATX, CHTO VSYAKIJ RAZ, KOGDA
VYCHISLYAETSYA $dd/3$, IMEET MESTO $3|dd$. {\sl (kONEC UPRAZHNENIYA.)}

dLYA PRIVEDENNOJ VYSHE PROGRAMMY HARAKTERNA DOVOLXNO
RASPROSTRANENNAYA OSOBENNOSTX. nA VNESHNEM UROVNE DVE KONSTRUKCII
POVTORENIYA RASPOLOZHENX PODRYAD; KOGDA DVE ILI
BOLXSHE KONSTRUKCIJ POVTORENIYA NA ODNOM I TOM ZHE UROVNE
SLEDUYUT DRUG ZA DRUGOM, OHRANYAEMYE KOMANDY BOLEE POZDNIH
KONSTRUKCIJ OKAZYVAYUTSYA, KAK PRAVILO, BOLEE SLOZHNYMI, CHEM
KOMANDY PREDYDUSHCHIH KONSTRUKCIJ. (eTO YAVLENIE IZVESTNO KAK
"ZAKON dEJKSTRY", KOTORYJ, ODNAKO, NE VSEGDA VYPOLNYAETSYA.)
pRICHINA TAKOJ TENDENCII YASNA: KAZHDAYA KONSTRUKCIYA POVTORENIYA
DOBAVLYAET SVOE "$\and \non BB$" K OTNOSHENIYU, KOTOROE ONA
SOHRANYAET INVARIANTNYM, I |TO DOPOLNITELXNOE OTNOSHENIE
SLEDUYUSHCHAYA KONSTRUKCIYA TAKZHE DOLZHNA SOHRANYATX INVARIANTNYM.
eSLI BY NE VNUTRENNIJ CIKL, VTOROJ CIKL BYL BY V TOCHNOSTI
PROTIVOPOLOZHEN PERVOMU; I FUNKCIYA DOPOLNITELXNOGO
OPERATORA
\prg
\.{do} r\GE dd\TO r:= r-dd \.{od}
\grp
IMENNO V TOM I SOSTOIT, CHTOBY VOSSTANAVLIVATX VOZMOZHNO NARUSHENNOE
OTNOSHENIE $r<dd$, DOSTIGAEMOE PRI VYPOLNENII PERVOGO CIKLA.

{\sl chETVERTYJ PRIMER}

dLYA FIKSIROVANNYH $Q1$, $Q2$, $Q3$ I $Q4$ TREBUETSYA OBESPECHITX
ISTINNOSTX $R$, PRICHEM $R$ ZADAETSYA KAK $R1 \and R2$, GDE

R1: POSLEDOVATELXNOSTX ZNACHENIJ (q1, q2, q3, q4) ESTX NEKOTORAYA
      PERESTANOVKA ZNACHENIJ (Ql, Q2, Q3, Q4)

R2: q1\LE q2 \LE q3 \LE q4

eSLI MY VOZXMEM $R1$ V KACHESTVE SOHRANYAEMOGO INVARIANTNYM
OTNOSHENIYA $P$, POLUCHIM TAKOE VOZMOZHNOE RESHENIE:
\prg
q1, q2, q3, q4:=Q1, Q2, Q3, Q4;
\.{do} q1>q2 \TO q1, q2 := q2, q1
\wbox q2>q3 \TO q2, q3 := q3, q2
\wbox q3>q4 \TO q3, q4:=q4, q3
\.{od}
\grp
oCHEVIDNO, CHTO POSLE PERVOGO PRISVAIVANIYA $P$ STANOVITSYA
ISTINNYM I NI ODNA IZ OHRANYAEMYH KOMAND NE NARUSHAET EGO
ISTINNOSTI. pO ZAVERSHENII PROGRAMMY MY IMEEM $\non BB$, A
|TO ESTX OTNOSHENIE $R2$. v TOM, CHTO PROGRAMMA DEJSTVITELXNO
PRIDET K ZAVERSHENIYU, KAZHDYJ IZ NAS UBEZHDAETSYA PO-RAZNOMU
V ZAVISIMOSTI OT SVOEJ PROFESSII: MATEMATIK MOG BY ZAMETITX,
CHTO CHISLO PERESTANOVOK UBYVAET, ISSLEDOVATELX OPERACIJ
BUDET INTERPRETIROVATX |TO KAK MAKSIMIZACIYU $q1+2*q2+3*q3+4*q4$,
A YA --- KAK FIZIK --- SRAZU "VIZHU", CHTO CENTR
TYAZHESTI SMESHCHAETSYA V ODNOM NAPRAVLENII (VPRAVO, ESLI BYTX
TOCHNYM). pROGRAMMA PRIMECHATELXNA V TOM SMYSLE, CHTO, KAKIE
BY PREDOHRANITELI MY NI VYBRALI, NIKOGDA NE VOZNIKNET
OPASNOSTI NARUSHENIYA ISTINNOSTI r: PREDOHRANITELI,
ISPOLXZUEMYE V NASHEM PRIMERE, YAVLYAYUTSYA CHISTYM SLEDSTVIEM
NEOBHODIMOSTI ZAVERSHENIYA PROGRAMMY.

{\sl zAMECHANIE.} zAMETXTE, CHTO MY MOGLI BY DOBAVITX TAKZHE I
DRUGIE VARIANTY, TAKIE, KAK
\prg
q1>q3 \to q1, q3 := q3, q1
\grp
PRICHEM IH NELXZYA ISPOLXZOVATX DLYA ZAMENY ODNOGO IZ TREH,
PERECHISLENNYH V PROGRAMME. {\sl (kONEC ZAMECHANIYA.)}

eTO HOROSHIJ PRIMER TOGO, KAKOGO RODA YASNOSTI MOZHNO
DOSTICHX PRI NASHEJ NEDETERMINIROVANNOSTI; IZLISHNE GOVORITX
ODNAKO, CHTO YA NE REKOMENDUYU SORTIROVATX BOLXSHOE 
KOLICHESTVO ZNACHENIJ ANALOGICHNYM SPOSOBOM.

{\sl pYATYJ PRIMER}

nAM TREBUETSYA SOSTAVITX PROGRAMMU APPROKSIMACII
KVADRATNOGO KORNYA; BOLEE TOCHNO: DLYA FIKSIROVANNOGO $n$ $(n>0)$
PROGRAMMA DOLZHNA OBESPECHITX ISTINNOSTX
$$
R:              a^2\le n \and (a+1)^2>n
$$

chTOBY OSLABITX |TO OTNOSHENIE, MOZHNO, NAPRIMER,
OTBROSITX ODIN IZ LOGICHESKIH SOMNOZHITELEJ, SKAZHEM POSLEDNIJ,
I SOSREDOTOCHITXSYA NA
$$
P:                 a^2\le n
$$

oCHEVIDNO, CHTO |TO OTNOSHENIE VERNO PRI $a=0$, PO|TOMU
VYBOR NACHALXNOGO ZNACHENIYA NE DOLZHEN NAS BESPOKOITX.
mY VIDIM, CHTO ESLI VTOROJ CHLEN NE YAVLYAETSYA ISTINNYM, TO |TO
VYZYVAETSYA SLISHKOM MALENXKIM ZNACHENIEM $a$, PO|TOMU MY MOGLI
BY OBRATITXSYA K OPERATORU "$a:=a+1$". fORMALXNO MY
POLUCHAEM
$$
\wp ("a := a + 1 ", P)=((a + 1)^2\le n)
$$

iSPOLXZUYA |TO USLOVIE V KACHESTVE (EDINSTVENNOGO!)
PREDOHRANITELYA, MY POLUCHAEM $(P \and \non BB) =R$ I PRIHODIM
K SLEDUYUSHCHEJ PROGRAMME:
\prg
\.{if} n\GE 0 \TO
a:=0  \{r STALO ISTINNYM\};
\.{do} (a+1)^2\LE n\to a:=a+1 \{P OSTALOSX ISTINNYM\} \.{od}
\{R STALO ISTINNYM \}
\.{fi} \{R  STALO ISTINNYM \}
\grp

pRI SOSTAVLENII PROGRAMMY MY ISHODILI IZ PREDPOLOZHENIYA,
CHTO ONa ZAVERSHITSYA, I |TO DEJSTVITELXNO TAK, POSKOLXKU
KORENX IZ NEOTRICATELXNOGO CHISLA ESTX MONOTONNO VOZRASTAYUSHCHAYA
FUNKCIYA: V KACHESTVE $t$ MY MOZHEM VZYATX FUNKCIYU $n-a^2$.

eTA PROGRAMMA DOVOLXNO OCHEVIDNA, K TOMU ZHE ONA I NE
OCHENX |FFEKTIVNA: PRI BOLXSHIH ZNACHENIYAH $n$ ONA BUDET RABOTATX
DOVOLXNO DOLGO. dRUGOJ SPOSOB OBOBSHCHENIYA R --- |TO VVEDENIE
DRUGOJ PEREMENNOJ (SKAZHEM, $b$ --- I SNOVA V OGRANICHENNOM
INTERVALE IZMENENIYA), KOTORAYA ZAMENIT CHASTX $R$, NAPRIMER,
$$
P:\quad a^2 \le n \and b^2>n \and 0\le a<b
$$
bLAGODARYA TAKOMU VYBORU $P$ OBLADAET TEM PRIYATNYM SVOJSTVOM, CHTO
$$
(P \and (a+1=b))\Rightarrow R
$$

tAKIM OBRAZOM, MY PRIHODIM K PROGRAMME, PREDSTAVLENNOJ
V TAKOJ FORME (ZDESX I DALEE KONSTRUKCIYA \.{if} n\GE 0 \TO \dots \.{fi}
OPUSKAETSYA):
\prg
a,b:=0, n+1 \{r STALO ISTINNYM\};
\.{do} a+1\NE b \TO UMENXSHITX b-a PRI INVARIANTNOSTI P \.{od}
\{R STALO ISTINNYM\}
\grp

pUSTX $d$ BUDET VELICHINOJ, NA KOTORUYU UMENXSHAETSYA RAZNOSTX $b-a$
PRI KAZHDOM VYPOLNENII OHRANYAEMOJ KOMANDY.
rAZNOSTX MOZHET UMENXSHATXSYA LIBO ZA SCHET UMENXSHENIYA $b$,
LIBO ZA SCHET UVELICHENIYA $a$, LIBO ZA SCHET I TOGO I DRUGOGO. nE
TERYAYA OBSHCHNOSTI, MY MOZHEM OGRANICHITXSYA RASSMOTRENIEM TAKIH
SHAGOV, KOGDA IZMENYAETSYA LIBO $a$, LIBO $b$, NO NE $a$ I $b$ ODNOVREMENNO:
ESLI $a$ SLISHKOM MALO I $b$ SLISHKOM VELIKO I NA ODNOM SHAGE
TOLXKO UMENXSHAETSYA $b$, TOGDA NA SLEDUYUSHCHEM SHAGE MOZHNO
UVELICHITX $a$. eTI SOOBRAZHENIYA PRIVODYAT NAS K PROGRAMME V
SLEDUYUSHCHEJ FORME:
\prg
a, b:=0, n+1 \{P STALO ISTINNYM\};
\.{do} a+1 \NE b \TO
d:=\dots \{d  IMEET SOOTVETSTVUYUSHCHEE ZNACHENIE I P PO-PREZHNEMU VYPOLNYAETSYA\};
\.{if} \dots\TO a:=a+d  \{P OSTALOSX ISTINNYM\}
\wbox\dots \TO b:=b-d \{P OSTALOSX ISTINNYM\}
\.{fi} \{P STALO ISTINNYM\}
\.{od} \{R STALO ISTINNYM\}
\grp

tEPERX
$$
\wp("a:=a+d", P)=((a+d)^2\le n \and b^2>n)
$$
pOSKOLXKU ISTINNOSTX VTOROGO CHLENA SLEDUET IZ ISTINNOSTI $P$,
MY MOZHEM ISPOLXZOVATX PERVYJ CHLEN V KACHESTVE NASHEGO
PERVOGO PREDOHRANITELYA; ANALOGICHNO VYVODITSYA VTOROJ
PREDOHRANITELX, I MY POLUCHAEM OCHEREDNUYU FORMU NASHEJ 
PROGRAMMY:
\prg
a, b:= 0, n+1;
\.{do} a+1 \NE b \TO d:=\dots;
      \.{if}(a+d)^2 \LE n\TO a:=a+d
      \wbox (b-d)^2>n\TO b:= b-d
      \.{fi} \{r OSTALOSX ISTINNYM\}
\.{od} \{R STALO ISTINNYM\}
\grp

nAM OSTAETSYA ESHCHE SOOTVETSTVUYUSHCHIM OBRAZOM VYBRATX $d$.
pOSKOLXKU MY VZYALI $b-a$ (NA SAMOM DELE, $b-A-1$) V KACHESTVE
NASHEJ FUNKCII $t$, |FFEKTIVNOE UBYVANIE DOLZHNO BYTX TAKIM,
CHTOBY d UDOVLETVORYALO USLOVIYU $d>0$. kROME TOGO, 
POSLEDUYUSHCHAYA KONSTRUKCIYA VYBORA NE DOLZHNA PRIVODITX K OTKAZU, T. E.
PO KRAJNEJ MERE ODIN IZ PREDOHRANITELEJ DOLZHEN BYTX
ISTINNYM. eTO ZNACHIT, CHTO IZ OTRICANIYA ODNOGO, $(a+d)^2>n$, DOLZHEN
SLEDOVATX DRUGOJ, $(b-d)^2>n$; |TO GARANTIRUETSYA, ESLI
$$
a+d\le b-d
$$
ILI
$$
2*d\le b-a
$$

nARYADU S NIZHNEJ GRANICEJ MY USTANOVILI TAKZHE I VERHNYUYU
GRANICU DLYA $d$. mY MOGLI BY VZYATX $d=1$, NO CHEM BOLXSHE $d$, TEM
BYSTREE RABOTAET PROGRAMMA, PO|TOMU MY PREDLAGAEM
\prg
a,b:=0,n+1;
\.{do} a+1 \NE b \TO d:=(b-a) \div 2;
             \.{if} (a+d)^2\LE n\TO a:=a+d
                \wbox (b-d)^2>n\TO b:=b-d
             \.{fi}          
\.{od}
\grp
GDE $n\div 2$ ESTX $n/2$, ESLI $2|n$ I $(n-1)/2$, ESLI $2|(n-1)$.

iSPOLXZOVANIE DEJSTVIYA $\div$ POBUZHDAET  NAS RAZOBRATSYA
V TOM, CHTO PROIZOJDET, ESLI MY NAVYAZHEM SEBE OGRANICHENIE NA $b-a$,
POLAGAYA, CHTO $b-a$ CHETNO PRI KAZHDOM VYCHISLENII $d$. vVODYA 
$c=(b-a)$ I ISKLYUCHAYA $b$, MY POLUCHAEM INVARIANTNOE OTNOSHENIE
$$
P:\qquad a^2\le n \and (a+c)^2 > n \and (\exists i: i\ge 0 : c=2^i)
$$
I PROGRAMMU (V KOTOROJ $c$ IGRAET ROLX $d$)
\prg
a,c:=0, 1; \.{do} c^2\LE n\TO c:=2*c \.{od};
\.{do} c \NE 1 \TO c := c/2;
           \.{if} (a + c)^2 \LE n \TO a:=a+c
               \wbox (a-c)^2 > n \TO \var{PROPUSTITX}
           \.{fi}
\.{od}
\grp

{\sl zAMECHANIE.} eTA PROGRAMMA OCHENX POHOZHA NA POSLEDNYUYU
PROGRAMMU DLYA TRETXEGO PRIMERA, GDE VYCHISLYALSYA OSTATOK V
PREDPOLOZHENII, CHTO MY IMEEM PRAVO UMNOZHATX I DELITX NA 3.
v PRIVEDENNOJ VYSHE PROGRAMME MOZHNO BYLO BY ZAMENITX KONSTRUKCIYU
VYBORA NA
\prg
\.{dO} (a+c)^2 \LE n \TO a:=a+c \.{od}
\grp
eSLI USLOVIE, KOTOROMU DOLZHEN UDOVLETVORYATX OSTATOK,
$0\le r < d$, ZAPISATX KAK $r<d \and (r+d)\ge d$, SHODSTVO STANET
ESHCHE BOLEE OTCHETLIVYM. {\sl (kONEC ZAMECHANIYA.)}

pONIMAYA, CHTO TAK MOZHNO OKONCHATELXNO "ZAMUCHITX" |TOT MALENXKIJ
PRIIMER, YA BY HOTEL TEM NE MENEE PREDLOZHITX POSLEDNIJ
VARIANT PREOBRAZOVANIYA PROGRAMMY. mY NAPISALI PROGRAMMU,
ISHODYA IZ PREDPOLOZHENIYA, CHTO OPERACIYA VOZVEDENIYA CHISLA V
KVADRAT VHODIT V SOSTAV IMEYUSHCHIHSYA OPERACIJ; NO PREDPOLOZHIM,
CHTO |TO NE TAK I CHTO EDINSTVENNYE OPERACII TIPA
UMNOZHENIYA, IMEYUSHCHIESYA V NASHEM RASPORYAZHENII,--- |TO UMNOZHENIE
I DELENIE NA (MALYE) STEPENI 2. tOGDA NASHA POSLEDNYAYA
PROGRAMMA OKAZYVAETSYA NE TAKOJ UZH HOROSHEJ, T. E. ONA
NEHOROSHA, ESLI MY PREDPOLAGAEM, CHTO ZNACHENIYA PEREMENNYH,
S KOTORYMI NEPOSREDSTVENNO OPERIRUET MASHINA, OTOZHDESTVLENY
SO ZNACHENIYAMI PEREMENNYH $a$ I $c$, KAK |TO BYLO BY PRI 
"ABSTRAKTNYH" VYCHISLENIYAH. dRUGIMI SLOVAMI, MY MOZHEM
RASSMATRIVATX $a$ I $c$ KAK ABSTRAKTNYE PEREMENNYE, CHXI
ZNACHENIYA PREDSTAVLYAYUTSYA (V SOOTVETSTVII S SOGLASHENIEM, 
PREDUSMATRIVAYUSHCHIM BOLEE SLOZHNYE USLOVIYA, CHEM PROSTO 
TOZHDESTVENNOSTX)
ZNACHENIYAMI DRUGIH PEREMENNYH, S KOTORYMI
V DEJSTVITELXNOSTM OPERIRUET MASHINA PRI VYPOLNENII
PROGRAMMY. mY MOZHEM POZVOLITX MASHINE RABOTATX NE
NEPOSREDSTVENNO S $a$ I $c$, A S $R$, $q$, $r$, TAKIMI, CHTO
$$
\eqalign{
p &= a * c \cr
q &=c^2\cr
r &=n-a^2\cr
}
$$

mY VIDIM, CHTO |TO --- PREOBRAZOVANIE KOORDINAT, I KAZHDOJ
TRAEKTORII V NASHEM $(a, c)$-PROSTRANSTVE SOOTVETSTVUET
TRAEKTORIYA V NASHEM $(p, q, r)$-PROSTRANSTVE. oBRATNOE NE VSEGDA
VERNO, TAK KAK ZNACHENIYA $p$, $q$ I $r$  NE NEZAVISIMY: V TERMINAH
$p$, $q$  I $r$ MY POLUCHAEM IZBYTOCHNOSTX I, SLEDOVATELXNO,
POTENCIALXNUYU VOZMOZHNOSTX, POZHERTVOVAV NEKOTORYM OB�EMOM
PAMYATI, NE  TOLXKO VYIGRATX VREMYA VYCHISLENIJ, NO
DAZHE IZBAVITXSYA OT NEOBHODIMOSTI VOZVODITX V KVADRAT!
(sOVERSHENNO YASNO, CHTO PRESLEDOVALASX IMENNO |TA CELX,
KOGDA STROILOSX PREOBRAZOVANIE, PEREVODYASHCHEE TOCHKU V
$(a,c)$-PROSTRANSTVE V TOCHKU V $(R, q, r)$-PROSTRANSTVE.) tEPERX MY
MOZHEM POPYTATXSYA PEREVESTI VSE BULEVY VYRAZHENIYA I 
PEREMESHCHENIYA V $(a, c)$-PROSTRANSTVE V SOOTVETSTVUYUSHCHIE BULEVY
VYRAZHENIYA I PEREMESHCHENIYA V $(p, q, r)$ -PROSTRANSTVE. eSLI BY NAM
UDALOSX SDELATX |TO V TERMINAH DOPUSTIMYH OPERACIJ, NASHA
ZADACHA BYLA BY USPESHNO RESHENA. pREDLAGAEMOE PREOBRAZOVANIE
I V SAMOM DELE OTVECHAET NASHIM TREBOVANIYAM, I REZULXTATOM
EGO YAVLYAETSYA SLEDUYUSHCHAYA PROGRAMMA (PEREMENNAYA $h$ BYLA
VVEDENA DLYA OCHENX LOKALXNOJ OPTIMIZACII):
\prg
p,q,r:=0,1,n; \.{do} q\LE n \TO q:=q*4 \.{od};
\.{do} q \NE 1\TO q:=q/4; h:=p+q; p:=p/2 \{h=2*p+q\}
     \.{if} r \GE h \TO p,r:=p+q,r-h
       \wbox r<h \TO \var{PROPUSTITX}
     \.{fi}
\.{od} \{ p IMEET ZNACHENIE, TREBUEMOE DLYA a \}
\grp

eTOT PYATYJ PRIMER BYL VKLYUCHEN BLAGODARYA ISTORII EGO
SOZDANIYA (PRAVDA, NESKOLXKO PRIUKRASHENNOJ). kOGDA
MLADSHEJ IZ DVUH NASHIH SOBAK BYLO VSEGO NESKOLXKO MESYACEV,
YA ODNAZHDY VECHEROM POSHEL POGULYATX S NIMI OBEIMI. nAZAVTRA
MNE PREDSTOYALO CHITATX LEKCII STUDENTAM, KOTORYE VSEGO LISHX
NESKOLXKO NEDELX NAZAD NACHALI ZNAKOMITXSYA S PROGRAMMIROVANIEM,
I MNE NUZHNA BYLA PROSTAYA ZADACHA, CHTOBY NA EE 
PRIMERE YA MOG "MASSIROVATX" RESHENIYA. v TECHENIE CHASOVOJ PROGULKI
YA PRODUMAL PERVUYU, TRETXYU I CHETVERTUYU PROGRAMMY, PRAVDA,
PRAVILXNO VVESTI $h$ V POSLEDNEJ PROGRAMME YA SMOG TOLXKO
PRI POMOSHCHI KARANDASHA I BUMAGI, KOGDA VERNULSYA DOMOJ. kO
VTOROJ PROGRAMME, TOJ, KOTORAYA OPERIRUET S $a$ I $b$ I KOTORAYA
BYLA ZDESX PREDSTAVLENA KAK PEREHODNAYA STUPENX K NASHEMU
TRETXEMU RESHENIYU, YA PRISHEL LISHX NESKOLXKO NEDELX SPUSTYA ---
I ONA BYLA TOGDA V GORAZDO MENEE |LEGANTNOJ FORME, CHEM PREDSTAVLENA
ZDESX. vTORAYA PRICHINA DLYA EE VKLYUCHENIYA V CHISLO
PREDSTAVLENNYH PROGRAMM --- |TO SOOTNOSHENIE MEZHDU TRETXEJ
PROGRAMMAMI: PO OTNOSHENIYU K CHETVERTOJ PROGRAMME TRETXYA
PREDSTAVLYAET SOBOJ NASH PERVYJ PRIMER TAK NAZYVAEMOJ
"ABSTRAKCII PREDSTAVLENIYA".

{\sl shESTOJ PRIMER}

dLYA FIKSIROVANNYH $X\ (X>1)$ I $Y\ (Y\ge 0)$ PROGRAMMA DOLZHNA
OBESPECHITX ISTINNOSTX OTNOSHENIYA
$$
R: \quad z=X^Y
$$
PRI OCHEVIDNOM PREDPOLOZHENII, CHTO OPERACIYA VOZVEDENIYA V STEPENX
NE VHODIT V NABOR DOSTUPNYH OPERACIJ. eTA ZADACHA MOZHET BYTX
RESHENA PRI POMOSHCHI "ABSTRAKTNOJ PEREMENNOJ", SKAZHEM $h$;
PRI RESHENII ZADACHI MY BUDEM POLXZOVATXSYA CIKLOM, DLYA KOTOROGO
INVARIANTNYM YAVLYAETSYA OTNOSHENIE
$$
P:\qquad h * z=X^Y
$$
I NASHA (V RAVNOJ STEPENI "ABSTRAKTNAYA") PROGRAMMA MOGLA 
BY VYGLYADETX TAK:
\prg
h,z:=h^Y,1 \{P STALO ISTINNYM\};
\.{do} h \NE 1\TO SZHIMATX $h$ PRI INVARIANTNOSTI $P$ \.{od}
\{ R STALO ISTINNYM \}
\grp

pOSLEDNEE ZAKLYUCHENIE SPRAVEDLIVO, POSKOLXKU $(P \and h=1)\Rightarrow R$.
pRIVEDENNAYA VYSHE PROGRAMMA PRIDET K ZAVERSHENIYU, ESLI
POSLE KONECHNOGO CHISLA PRIMENENIJ OPERACII "SZHIMANIYA" $h$
STANET RAVNYM 1. pROBLEMA, KONECHNO, V TOM, CHTO MY NE MOZHEM
PREDSTAVITX ZNACHENIE $h$ ZNACHENIEM KONKRETNOJ PEREMENNOJ, 
S KOTORYM NEPOSREDSTVENNO OPERIRUET MASHINA; ESLI BY MY
MOGLI TAK SDELATX, MY MOGLI BY SRAZU PRISVOITX $z$ ZNACHENIE
$X^Y$, NE ZATRUDNYAYA SEBYA VVEDENIEM $h$. fOKUS V TOM, CHTO
DLYA PREDSTAVLENIYA TEKUSHCHEGO ZNACHENIYA $h$ MY MOZHEM VVESTI DVE ---
NA |TOM UROVNE KONKRETNYE --- PEREMENNYE, SKAZHEM $x$ I $y$,
I NASHE PERVOE PRISVAIVANIE PREDLAGAET V KACHESTVE SOGLASHENIYA
OB |TOM PREDSTAVLENII
$$
h=x^y
$$

tOGDA USLOVIE "$h\not=1$" PEREHODIT V USLOVIE "$y\not=0$", I NASHA
SLEDUYUSHCHAYA ZADACHA SOSTOIT V TOM, CHTOBY PODYSKATX VYPOLNIMUYU
OPERACIYU "SZHIMANIYA". pOSKOLXKU PRI |TOJ OPERACII
PROIZVEDENIE $h*z$ DOLZHNO OSTAVATXSYA INVARIANTNYM, MY DOLZHNY
DELITX $h$ NA TU ZHE VELICHINU, NA KOTORUYU UMNOZHAETSYA $z$.
iSHODYA IZ PREDSTAVLENIYA $h$, NAIBOLEE ESTESTVENNYM KANDIDATOM NA
|TU VELICHINU MOZHNO SCHITATX TEKUSHCHEE ZNACHENIE $x$. bEZ 
DALXNEJSHIH ZATRUDNENIJ MY PRIHODIM K TAKOMU VIDU NASHEJ
ABSTRAKTNOJ PROGRAMMY:
\prg
x,y,z:=X,Y,1 \{P STALO ISTINNYM\};
\.{do} y\NE 0 \TO y,z:=y-1, z*x \{P OSTALOSX ISTINNYM\} \.{od}
\{R STALO ISTINNYM\}
\grp

gLYADYA NA |TU PROGRAMMU, MY PONIMAEM, CHTO CHISLO 
VYPOLNENIJ CIKLA RAVNO PERVONACHALXNOMU ZNACHENIYU $Y$, I MOZHEM
ZADATX SEBE VOPROS, NELXZYA LI USKORITX PROGRAMMU. yaSNO, CHTO
ZADACHEJ OHRANYAEMOJ KOMANDY YAVLYAETSYA SVEDENIE $y$ K NULYU; NE
IZMENYAYA \emph{ZNACHENIYA} $h$, MY MOZHEM PROVERITX, NELXZYA LI IZMENITX
\emph{PREDSTAVLENIE} |TOGO ZNACHENIYA V NADEZHDE UMENXSHITX ZNACHENIE
$y$. pOPYTAEMSYA VOSPOLXZOVATXSYA TEM FAKTOM, CHTO KONKRETNOE
PREDSTAVLENIE ZNACHENIYA $h$, ZADANNOE KAK $x^y$, VOVSE NE YAVLYAETSYA
ODNOZNACHNYM. eSLI $y$ CHETNO, MY MOZHEM RAZDELITX $y$ NA 2 I
VOZVESTI $x$ V KVADRAT, PRI |TOM ZNACHENIE $h$ SOVSEM NE IZMENITSYA.
 nEPOSREDSTVENNO PERED OPERACIEJ SZHIMANIYA MY VSTAVLYAEM
PREOBRAZOVANIE, PRIVODYASHCHEE K NAIBOLEE PRIVLEKATELXNOMU
PREOBRAZOVANIYU $h$ I POLUCHAEM SLEDUYUSHCHUYU PROGRAMMU:
\prg
x,y,z:=X,Y,1;
\.{do} y\NE0 \TO \.{do} 2 | y\TO x, U:= x*x, y/2 \.{od};
              y,z:=y-1,z*x
\.{od} \{R STALO ISTINNYM \}
\grp

sUSHCHESTVUET TOLXKO ODNA VELICHINA, KOTORUYU MOZHNO
BESKONECHNO DELITX POPOLAM I ONA NE STANET NECHETNOJ, |TA
VELICHINA --- NULX; INACHE GOVORYA, VNESHNIJ PREDOHRANITELX GARANTIRUET
NAM, CHTO VNUTRENNIJ CIKL PRIDET K ZAVERSHENIYU.

ya VKLYUCHIL |TOT PRIMER PO RAZNYM PRICHINAM. mENYA 
PORAZILO OTKRYTIE, CHTO ESLI PROSTO VSTAVITX V PROGRAMMU CHTO-TO,
CHTO NA ABSTRAKTNOM UROVNE DEJSTVUET KAK PUSTOJ OPERATOR,
MOZHNO TAK IZMENITX ALGORITM, CHTO CHISLO OPERACIJ, KOTOROE
RANXSHE BYLO PROPORCIONALXNO $Y$, STANET PROPORCIONALXNO
TOLXKO $\log (Y)$. eTO OTKRYTIE BYLO PRYAMYM SLEDSTVIEM TOGO,
CHTO YA ZASTAVIL SEBYA DUMATX V TERMINAH OTDELXNOJ ABSTRAKTNOJ
PEREMENNOJ. pROGRAMMA VOZVEDENIYA V STEPENX, KOTORUYU YA ZNAL,
BYLA SLEDUYUSHCHEJ:
\prg
x,y,z:=h,Y,1;
\.{do} y<>0 \TO \.{if} \non 2| y\TO y,z:=y-1,z*x
                       \wbox 2|y \TO\var{PROPUSTITX} \.{fi};
                   x,y:=x*x,y/2
\.{od}
\grp
eTA POSLEDNYAYA PROGRAMMA OCHENX HOROSHO IZVESTNA, MNOGIE IZ
NAS PRISHLI K NEJ NEZAVISIMO DRUG OT DRUGA. pOSKOLXKU POSLEDNEE
VOZVEDENIE $x$ V KVADRAT, KOGDA $y$ STAL RAVNYM NULYU, UZHE
IZLISHNE, NA |TU PROGRAMMU CHASTO SSYLALISX KAK NA PRIMER,
PODTVEZHDAYUSHCHIJ NEOBHODIMOSTX IMETX TO, CHTO MY NAZVALI BY
"PROMEZHUTOCHNNYMI VYHODAMI". pRINIMAYA VO VNIMANIE NASHU
PROGRAMMU, YA PRIHOZHU K ZAKLYUCHENIYU, CHTO |TOT DOVOD SLAB.

{\sl sEDXMOJ PRIMER }

dLYA FIKSIROVANNOGO ZNACHENIYA $n$ $(n\ge 0)$ ZADANA FUNKCIYA
$f(i)$ DLYA $0\le i<n$. pRISVOITX BULEVOJ PEREMENNOJ "\var{VSESHESTX}"
TAKOE ZNACHENIE, CHTOBY V KONECHNOM REZULXTATE STALO SPRAVEDLIVYM
$$
R:\qquad \var{VSESHESTX} =  (\forall i: 0 \le i < n : f (i) = 6)
$$
(eTOT PRIMER OBNARUZHIVAET NEKOTOROE SHODSTVO SO VTORYM
PRIMEROM DANNOJ GLAVY. zAMETIM, ODNAKO, CHTO V |TOM PRIMERE
DOPUSKAETSYA RAVENSTVO $n$ NULYU. v TAKOM SLUCHAE INTERVAL
VOZMOZHNYH ZNACHENIJ DLYA KVANTORA "$\forall$" PUST I DOLZHNO BYTX
VERNYM, CHTO  $\var{VSESHESTX}=\var{ISTINA}$.) pO ANALOGII SO VTORYM PRIMEROM
VVEDEM INVARIANTNOE OTNOSHENIE
$$
P:\qquad \var{VSESHESTX}=(\forall i: 0\le i<j :f(i)= 6)) \and 0\le j\le n
$$
POSKOLXKU |TO OTNOSHENIE LEGKO SDELATX ISTINNYM PRI $j=0$
I K TOMU ZHE $(P \and j=n) \Rightarrow R$ . eDINSTVENNOE, CHTO MY DOLZHNY
SDELATX, |TO PONYATX, KAK UVELICHIVATX $j$ PRI INVARIANTNOSTI $r$.
pO|TOMU BEREM
$$
\wp("j:=j+1", P)=
(\var{VSESHESTX}= (\forall i: 0\le i<j+1: f(i)=6)) \and 0\le j+1\le n
$$
sPRAVEDLIVOSTX POSLEDNEGO CHLENA SLEDUET IZ SPRAVEDLIVOSTI
$P \and j\not=n$; I V |TOM NET NIKAKOJ PROBLEMY, TAK KAK MY UZHE
RESHILI, CHTO USLOVIE $j\not=n$, VZYATOE V KACHESTVE PREDOHRANITELYA,
YAVLYAETSYA OSTATOCHNO SLABYM, CHTOBY DELATX VYVODY O ZNACHENII

\bye
