\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 in$, PREDOHRANITELX "$j0$ 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} i0)$ 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 $r0 \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 $rq2 \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 an) $$ 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 $r1)$ 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