\input style \chapter{8 ТНПЛЮКЭМНЕ ПЮЯЯЛНРПЕМХЕ МЕЯЙНКЭЙХУ МЕАНКЭЬХУ ОПХЛЕПНБ} Б щрни цкюбе ъ опнбедс тнплюкэмне онярпнемхе меяйнкэйху меанкэьху опнцпюлл дкъ пеьемхъ опняршу гюдюв. Ме якедсер онмхлюрэ щрс цкюбс йюй опедкнфемхе ярпнхрэ опнцпюллш рнкэйн рюй х ме хмюве: рюйне опедкнфемхе ашкн аш днбнкэмн ялеунрбнпмшл. Ъ онкюцюч, врн лмнцхл хг лнху вхрюрекеи гмюйнлн анкэьхмярбн опхлепнб, ю еякх мер, нмх, бепнърмн, ме гюдслшбюъяэ ялнцср мюохяюрэ кчасч хг щрху опнцпюлл. Якеднбюрекэмн, онярпнемхе опнцпюлл опнбндхряъ гдеяэ янбяел он дпсцхл опхвхмюл. Бн-оепбшу, щрн акхфе онгмюйнлхр мюя я тнплюкхглнл, пюгбхршл б опедшдсыху цкюбюу. Бн-брнпшу, саедхр мюя б рнл, врн он йпюимеи лепе б опхмжхое, тнплюкхгл яонянаем ядекюрэ ъямшл х янбепьеммн ярпнцхл рн, врн вюярн на╝ъямъеряъ опх онлных щмепцхвмни феярхйскъжхх. Б-рперэху, лмнцхе хг мюя мюярнкэйн унпньн гмючр щрх опнцпюллш, врн сфе гюашкх, йюйхл напюгнл дюбмшл-дюбмн лш саедхкхяэ б ху опюбхкэмнярх: б щрнл нрмньемхх мюярнъыюъ цкюбю мюонлхмюер мювюкэмше спнйх окюмхлерпхх, йнрнпше он рпюдхжхх онябъыючряъ днйюгюрекэярбс нвебхдмнцн. Б-вербепршу, лш лнфел яксвюимн намюпсфхрэ, й ябнелс сдхбкемхч, врн люкемэйюъ гмюйнлюъ гюдювйю ме рюйюъ сфе гмюйнлюъ. Мюйнмеж, опнжеяя онярпнемхъ опнцпюлл лнфер опнкхрэ ябер мю нясыеярбхлнярэ, рпсдмнярх х бнглнфмнярх юбрнлюрхвеяйнцн янярюбкемхъ опнцпюлл хкх хяонкэгнбюмхъ люьхмш б опнжеяяе опнцпюллхпнбюмхъ. Щрн лнфер нйюгюрэяъ бюфмшл, дюфе еякх юбрнлюрхвеяйне янярюбкемхе опнцпюлл ме бшгшбюер с мюя мх люкеиьецн хмрепеяю, онрнлс врн лнфер онлнвэ мюл ксвье нжемхрэ рс пнкэ, йнрнпсч лнцср хкх днкфмш хцпюрэ мюьх хгнаперюрекэяйхе яонянамнярх. Б лнху опхлепюу ъ асдс тнплскхпнбюрэ рпеанбюмхъ гюдювх б тнплe "дкъ тхйяхпнбюммшу $x$, $y$, \dots", врн ъбкъеряъ янйпюыеммни гюохяэч тнплш "дкъ кчашу гмювемхи $x_0$, $y_0$, ... онярсякнбхе бхдю $x=x_0 \and y=y_0 \and \ldots$ днкфмн бшгшбюрэ опедсякнбхе, хг йнрнпнцн якедсер, врн $x=x_0 \and y=y_0 \and \ldots$". Щрю ябъгэ лефдс онярсякнбхел х опедсякнбхел асдер цюпюмрхпнбюмю рел, врн лш асдел нрмняхрэяъ й рюйхл бекхвхмюл йюй й "бпелеммшл йнмярюмрюл"; нмх ме асдср бярпевюрэяъ б кебшу вюяръу ноепюрнпнб опхябюхбюмхъ. {\sl Оепбши опхлеп} Дкъ тхйяхпнбюммшу $x$ х $y$ наеяоевхрэ хярхммнярэ нрмньемхъ $R(m)$. $$ (m=x \or m=y) \and m\ge x \and m\ge y $$ Дкъ кчашу гмювемхи $x$ х $y$ нрмньемхе $m=x$ лнфер ярюрэ хярхммшл рнкэйн б пегскэрюре опхябюхбюмхъ $m:=x$; якеднбюрекэмн, хярхммнярэ $(m=x \or m=y)$ наеяоевхбюеряъ рнкэйн бшонкмемхел кхан $m:=у$, кхан $m:=y$. Б бхде акнй-яуелш: \pict{8.1} Бяе декн б рнл, врн мю бунде мсфмн ядекюрэ опюбхкэмши бшанп, йнрнпши наеяоевхр хярхммнярэ $R(m)$ оняке гюбепьемхъ бшвхякемхи. Дкъ щрнцн лш "опнрюкйхбюел онярсякнбхе вепег юкэрепмюрхбш": \pict{8.2} х лш онксвхкх опеднупюмхрекх! Рюй йюй $$ R(x) = ((x=x \or x=y) \and x\ge x \and x\ge y) = (x\ge y) $$ х $$ R(y)= ((y=x \or y=y) \and y \ge x \and y\ge y) = (y \ge x) $$ лш опхундхл й мюьелс пеьемхч: \prg \.{if} x\ge y \to m:=x \wbox y\ge x \to m:=y \.{fi} \grp Оняйнкэйс $(x\ge y \or y \ge x)=T$, нрйюгю мхйнцдю ме опнхгнидер (оносрмн лш онксвхкх днйюгюрекэярбн ясыеярбнбюмхъ: дкъ кчашу гмювемхи $x$ х $y$ ясыеярбсер $m$, сднбкербнпъчыее $R(m)$). Оняйнкэйс $(x\ge y \and y\ge x)\not=F$, мюью опнцпюллю ме наъгюрекэмн дереплхмхпнбюмю. Еякх оепбнмювюкэмн $x=y$, рн нйюгшбюеряъ менопедекеммшл, йюйне хг дбсу опхябюхбюмхи асдер бшапюмн дкъ хяонкмемхъ; рюйюъ медереплхмхпнбюммнярэ янбепьеммн йнппейрмю, рюй йюй лш онйюгюкх, врн бшанп ме хлеер гмювемхъ. {\sl Гюлевюмхе.} Еякх аш япедх днярсомшу опхлхрхбнб хлекюяэ тсмйжхъ "$\max$", лш лнцкх аш мюохяюрэ опнцпюллс $m:=\max(у,y)$, оняйнкэйс $R(\max(x,y))=T$. {\sl(Йнмеж гюлевюмхъ.)} Онксвеммюъ опнцпюллю ме опнхгбндхр нвемэ яхкэмнцн боевюркемхъ; я дпсцни ярнпнмш, лш бхдхл, врн б опнжеяяе бшбндю опнцпюллш хг онярсякнбхъ мю днкч мюьеи хгнаперюрекэмнярх онврх мхвero ме нярюкняэ. {\sl Брнпни опхлеп} Дкъ тхйяхпнбюммнцн гмювемхъ $n$ $(n>0)$ гюдюмю тсмйжхъ $f(i)$ дкъ $0\le i< n$. Наеяоевхрэ хярхммнярэ $R$: $$ 0 \le k< n \and (\forall i:0 \le in$, опеднупюмхрекэ "$j0$ нопедекъеряъ йюй $x_i=f(x_{i-1})$, цде $f$ --- мейнрнпюъ бшвхякхлюъ тсмйжхъ. Асдел бмхлюрекэмн х рнвмн якедхрэ гю рел. врнаш янупюмъкняэ хмбюпхюмрмшл нрмньемхе $X=x_i$. Опедонкнфхл, врн б опнцпюлле хлееряъ лнмнрнммн бнгпюярючыюъ оепелеммюъ $n$, рюйюъ, врн дкъ мейнрнпшу гмювемхи $n$ мюя хмрепеясчр $x_n$. Опх сякнбхх врн $n\ge i$, лш бяецдю лнфел ядекюрэ хярхммшл нрмньемхе $X=x_n$ опх онлных \prg \.{do} i\NE n \TO i, X:=i+1, f(X) \.{od} \grp Еякх фе нрмньемхе $n\ge i$ ме наъгюрекэмн хлеер леярн (лнфер ашрэ, онякедсчыхе хглемемхъ б опнцпюлле опхбекх й рнлс, врн б опнжеяяе бшвхякемхи $n$ асдер ме рнкэйн бнгпюярюрэ), опхбедеммюъ бшье йнмярпсйжхъ (й явюярэч!) ме опхдер й гюбепьемхч, б рн бпелъ йюй йнмярпсйжхъ \prg \.{do} i0)$ рпеасеряъ наеяоевхрэ хярхммнярэ R: $$ 0\le r< d \and d|(a-r) $$ (Гдеяэ бепрхйюкэмюъ вепрю "$|$" гюлемъер янани якнбю "ъбкъеряъ декхрекел".) Хмюве цнбнпъ, мюл рпеасеряъ бшвхякхрэ мюхлемэьхи менрпхжюрекэмши нярюрнй $r$, онксвеммши б пегскэрюре декемхъ $a$ мю $d$. Врнаш щрю гюдювю деиярбхрекэмн ашкю гюдювеи, лш днкфмш нцпюмхвхрэ хяонкэгнбюмхе юпхтлерхвеяйху ноепюжхи рнкэйн ноепюжхълх якнфемхъ х бшвхрюмхъ. Оняйнкэйс сякнбхе $d|(a-r)$ бшонкмъеряъ опх $r=a$ х опх щрнл, рюй йюй $a\ge 0$, бепмн, врн $0\le r$, опедкюцюеряъ бшапюрэ б йювеярбе хмбюпхюмрмнцн нрмньемхъ $P$: $$ 0 \le r \and d|(a-r) $$ Б йювеярбе тсмйжхх $t$, сашбюмхе йнрнпни днкфмн наеяоевхрэ гюбепьемхе пюанрш опнцпюллш, лш бшахпюел яюлн $r$. Оняйнкэйс хглемемхе $r$ днкфмн ашрэ рюйхл, врнаш мехглеммн бшонкмъкняэ сякнбхе $d|(a-r)$, $r$ лнфмн хглемърэ рнкэйн мю вхякн, йпюрмне $d$, мюопхлеп мю яюлн $d$. Рюйхл напюгнл, мюл, йюй нйюгюкняэ, опедкюцюеряъ бшвхякхрэ $$ \wp("r:=r-d", P) \and \wdec("r:=r-d", r)=0\le r-d \and d|(a-r+d) \and d>0 $$ Оняйнкэйс вкем $d>0$ лнфмн ашкн аш днаюбхрэ й хмбюпхюмрмнлс нрмньемхч $P$, нанямнбюмхъ рпеасер рнкэйн оепбши вкем; лш мюундхл яннрберярбсчыхи опеднупюмхрекэ "$r\ge d$" х опнасел янярюбхрэ рюйсч опнцпюллс: \prg \.{if} a \GE 0 \and d>0 \TO r:=a; \.{do} r \GE d \TO r:=r-d \.{od} \.{fi} \grp Он гюбепьемхх опнцпюллш ярюкн хярхммшл нрмньемхе $P\and\non r\ge d$, хг вецн якедсер хярхммнярэ $R$, х, рюйхл напюгнл, гюдювю пеьемю. Опедонкнфхл реоепэ, врн мюл, йпнле рнцн, онрпеанбюкняэ аш опхябнхрэ $q$ рюйне гмювемхе, врнаш он нйнмвюмхх опнцпюллш ашкн аш рюйфе бепмн, врн $$ a=d *q+r $$ хмюве цнбнпъ, рпеасеряъ мюирх ме рнкэйн нярюрнй, мн х вюярмне. Онопнасел днаюбхрэ щрнр вкем й мюьелс хмбюпхюмрмнлс нрмньемхч. Оняйнкэйс $$ (a=d* q+r)\Rightarrow (a=d*(q+1)+(r-d)) $$ лш опхундхл й опнцпюлле \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 Мю бшонкмемхе опхбедеммшу бшье опнцпюлл асдер, йнмевмн, гюрпювхбюрэяъ нвемэ лмнцн бпелемх, еякх вюярмне бекхйн. Лнфел кх лш янйпюрхрэ щрн бпелъ? Нвебхдмн, щрнцн лнфмн днахрэяъ, еякх слемэьюрэ $r$ мю бекхвхмс, йпюрмсч х анкэьсч $d$. Ббндъ дкъ щрни жекх мнбсч оепелеммсч, яйюфел $dd$, лш онксвюел сякнбхе, йнрнпне днкфмн мехглеммн бшонкмърэяъ мю опнръфемхх бяеи пa6oрш опнцпюллш: $$ d|dd \and dd \GE d $$ Лш лнфел сяйнпхрэ мюьс оепбсч опнцпюллс, гюлемхб "$r:=r-d$" слемэьемхел, бнглнфмн онбрнпмшл, $r$ мю $dd$, опеднярюбкъъ б рн фе бпелъ бнглнфмнярэ $dd$, оепбнмювюкэмн пюбмнлс $d$, днбнкэмн ашярпн бнгпюярюрэ, мюопхлеп йюфдши пюг сдбюхбюъ $dd$. Рнцдю лш опхундхл й якедсчыеи опнцпюлле: \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 Ъямн, врн нрмньемхе $0\le r \and d|(a-r)$ янупюмъеряъ хмбюпхюмрмшл, х онщрнлс опнцпюллю наеяоевхр хярхммнярэ $R$, еякх нмю гюбепьхряъ мнплюкэмн, мн рюй кх щрн? Йнмевмн, рюй, оняйнкэйс бмсрпеммхи жхйк, йнрнпши гюбепьюеряъ опх $dd>0$, бнгасфдюеряъ рнкэйн опх мювюкэмшу янярнъмхъу, сднбкербнпъчыху сякнбхч $r\ge dd$, х онщрнлс слемэьемхе $r:=r-dd$ бшонкмъеряъ он йпюимеи лепе ндхм пюг дкъ йюфднцн онбрнпемхъ бмеьмецн жхйкю. Мн рюйне пюяясфдемхе (унръ х днярюрнвмн саедхрекэмне!) ъбкъеряъ беяэлю метнплюкэмшл, ю оняйнкэйс б щрни цкюбе лш цнбнпхл н тнплюкэмнл онярпнемхх опнцпюлл, лш лнфел онопнанбюрэ ятнплскхпнбюрэ х днйюгюрэ ренпелс, йнрнпни хмрсхрхбмн бняонкэгнбюкхяэ. Осярэ IF, DO х ББ онмхлючряъ б нашвмнл ялшяке, х $P$ --- щрн нрмньемхе, янупюмъчыееяъ хмбюпхюмрмшл, р.е. $$ (P \and BB)\Rightarrow \wp (IF, P) \qquad\hbox{дкъ бяеу янярнъмхи} \eqno(1) $$ х осярэ $t$ --- жекнвхякеммюъ тсмйжхъ, рюйюъ, врн дкъ кчанцн гмювемхъ $t_0$ х дкъ бяеу янярнъмхи $$ (P \and BB \and t\le t_0+1)\to \wp(IF, t\le t_0) \eqno(2) $$ хкх, врн рн фе, $$ (P \and BB)\Rightarrow \wdec(IF,t) \qquad\hbox{дкъ бяеу янярнъмхи} \eqno(3) $$ Рнцдю дкъ кчанцн гмювемхъ $t_0$ х дкъ бяеу янярнъмхи $$ (P \and BB \and \wp(DO, T) \and t\le t_0+1) \Rightarrow \wp (DO,t\le t_0) \eqno(4) $$ хкх, врн рн фе, $$ (P\and BB\and\wp(DO,T))\Rightarrow \wdec(DO,t) \eqno(5) $$ Б якнбеямни тнплскхпнбйе: еякх янупюмъелне хмбюпхюмрмшл нрмньемхе $P$ цюпюмрхпсер, врн йюфдюъ бшапюммюъ дкъ хяонкмемхъ нупюмъелюъ йнлюмдю бшгшбюер деиярбхрекэмне слемэьемхе $t$, рн йнмярпсйжхъ онбрнпемхъ бшгнбер деиярбхрекэмне слемэьемхе $t$, еякх нмю мнплюкэмн гюбепьхряъ оняке он йпюимеи лепе ндмнцн бшонкмемхъ йюйни-кхан нупюмъелни йнлюмдш. Ренпелю мюярнкэйн нвебхдмю, врн ашкн аш дняюдмн, еякх аш ее днйюгюрекэярбн нйюгюкняэ рпсдмшл, мн, й явюярэч, щрн ме рюй. Лш онйюфел, врн хг (1) х (2) якедсер, врн дкъ кчанцн гмювемхъ $t_0$ х дкъ бяеу янярнъмхи $$ (P \and BB and H_k(T)) \and t\le t_0+1)\Rightarrow H_k (t \le t_0) \eqno (6) $$ дкъ бяеу $k \ge 0$. Щрн яопюбедкхбн дкъ $k=0$, оняйнкэйс $(BB\and H_0(T))=F$, х, хяундъ хг опедонкнфемхъ, врн (6) яопюбедкхбн дкъ $k=K$, лш днкфмш онйюгюрэ, врн (6) яопюбедкхбн х дкъ $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 } $$ Оепбюъ хлокхйюжхъ якедсер хг (1), нопедекемхъ $H_{K+1}(T)$ х (2); пюбемярбн б рперэеи ярпнйе нвебхдмн; хлокхйюжхъ б вербепрни ярпнйе бшбндхряъ опх онлных опхянедхмемхъ $(BB \or\non BB)$ х онякедсчыецн някюакемхъ нанху вкемнб; хлокхйюжхъ б оърни ярпнйе якедсер хг (6) опх $k=K$ х нопедекемхъ $H_0(t\le t_0)$; нярюкэмне онмърмн. Рюйхл напюгнл, лш днйюгюкх яопюбедкхбнярэ (6) дкъ бяеу $k>0$, ю нрячдю меледкеммн бшрейючр (4) х (5). {\bf Сопюфмемхе} Хглемхре мюьс брнпсч опнцпюллс рюйхл напюгнл, врнаш нмю бшвхякъкю рюйфе х вюярмне, х дюире тнплюкэмне днйюгюрекэярбн опюбхкэмнярх бюьеи опнцпюллш. {\sl(Йнмеж сопюфмемхъ.)} Опедонкнфхл реоепэ, врн хлееряъ люкемэйне вхякн, яйюфел 3, мю йнрнпне мюл онгбнкемн слмнфюрэ х декхрэ, х врн щрх ноепюжхх бшонкмъчряъ днярюрнвмн ашярпн, рюй врн хлеер ялшяк бняонкэгнбюрэяъ хлх. Асдел нангмювюрэ опнхгбедемхе "$m*3$" (хкх "$3*m$") х вюярмне "$m/3$"; онякедмее бшпюфемхе асдер хяонкэгнбюрэяъ рнкэйн опх сякнбхх, врн оепбнмювюкэмн яопюбедкхбн $3|m$. (Лш бедэ пюанрюел я жекшлх вхякюлх, ме рюй кх?) Х ноърэ лш ошрюеляъ наеяоевхрэ хярхммнярэ фекюелнцн нрмньемхъ $R$ опх онлных йнмярпсйжхх онбрнпемхъ, дкъ йнрнпни хмбюпхюмрмне нрмньемхе $P$ бшбндхряъ осрел гюлемш йнмярюмрш оепелеммни. Гюлемъъ йнмярюмрс $d$ оепелеммни $dd$, вэх гмювемхъ асдср опедярюбкърэяъ рнкэйн б бхде $d * (\hbox{ яреоемэ }3)$, лш опхундхл й хмбюпхюмрмнлс нрмньемхч $P$: $$ 0\le r < dd \and dd \ (ю-r) \and (\exists i:i\ge 0:dd=d*3^i) $$ Лш наеяоевхл хярхммнярэ щрнцн нрмньемхъ х гюрел, гюлемъъ ецн хмбюпхюмрмшл, онярюпюеляъ днярхвэ янярнъмхъ, опх йнрнпнл $d=dd$. Врнаш наеяоевхрэ хярхммнярэ $P$, мюл онмюднахряъ еые ндмю йнмярпсйжхъ онбрнпемхъ: ямювюкю лш наеяоевхл хярхммнярэ нрмньемхъ $$ 0\le r \and dd \ (a-r) \and (\exists i:i\ge 0:dd=d*3^i) $$ ю гюрел асдел сбекхвхбюрэ $dd$, онйю ецн гмювемхе ме ярюмер днярюрнвмн анкэьхл х рюйхл, врн $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 Сопюфмемхе} Хглемхре опхбедеммсч бшье опнцпюллс рюйхл напюгнл, врнаш нмю бшвхякъкю рюйфе х вюярмне, х дюире тнплюкэмне днйюгюрекэярбн опюбхкэмнярх бюьеи опнцпюллш, Щрн днйюгюрекэярбн днкфмн мюцкъдмн онйюгшбюрэ, врн бяъйхи пюг, йнцдю бшвхякъеряъ $dd/3$, хлеер леярн $3|dd$. {\sl (Йнмеж сопюфмемхъ.)} Дкъ опхбедеммни бшье опнцпюллш уюпюйрепмю днбнкэмн пюяопнярпюмеммюъ нянаеммнярэ. Мю бмеьмел спнбме дбе йнмярпсйжхх онбрнпемхъ пюяонкнфемэ ондпъд; йнцдю дбе хкх анкэье йнмярпсйжхи онбрнпемхъ мю ндмнл х рнл фе спнбме якедсчр дпсц гю дпсцнл, нупюмъелше йнлюмдш анкее онгдмху йнмярпсйжхи нйюгшбючряъ, йюй опюбхкн, анкее якнфмшлх, вел йнлюмдш опедшдсыху йнмярпсйжхи. (Щрн ъбкемхе хгбеярмн йюй "гюйнм Деийярпш", йнрнпши, ндмюйн, ме бяецдю бшонкмъеряъ.) Опхвхмю рюйни ремдемжхх ъямю: йюфдюъ йнмярпсйжхъ онбрнпемхъ днаюбкъер ябне "$\and \non BB$" й нрмньемхч, йнрнпне нмю янупюмъер хмбюпхюмрмшл, х щрн днонкмхрекэмне нрмньемхе якедсчыюъ йнмярпсйжхъ рюйфе днкфмю янупюмърэ хмбюпхюмрмшл. Еякх аш ме бмсрпеммхи жхйк, брнпни жхйк ашк аш б рнвмнярх опнрхбнонкнфем оепбнлс; х тсмйжхъ днонкмхрекэмнцн ноепюрнпю \prg \.{do} r\GE dd\TO r:= r-dd \.{od} \grp хлеммн б рнл х янярнхр, врнаш бняярюмюбкхбюрэ бнглнфмн мюпсьеммне нрмньемхе $rq2 \TO q1, q2 := q2, q1 \wbox q2>q3 \TO q2, q3 := q3, q2 \wbox q3>q4 \TO q3, q4:=q4, q3 \.{od} \grp Нвебхдмн, врн оняке оепбнцн опхябюхбюмхъ $P$ ярюмнбхряъ хярхммшл х мх ндмю хг нупюмъелшу йнлюмд ме мюпсьюер ецн хярхммнярх. Он гюбепьемхх опнцпюллш лш хлеел $\non BB$, ю щрн еярэ нрмньемхе $R2$. Б рнл, врн опнцпюллю деиярбхрекэмн опхдер й гюбепьемхч, йюфдши хг мюя саефдюеряъ он-пюгмнлс б гюбхяхлнярх нр ябнеи опнтеяяхх: люрелюрхй лнц аш гюлерхрэ, врн вхякн оепеярюмнбнй сашбюер, хяякеднбюрекэ ноепюжхи асдер хмрепоперхпнбюрэ щрн йюй люйяхлхгюжхч $q1+2*q2+3*q3+4*q4$, ю ъ --- йюй тхгхй --- япюгс "бхфс", врн жемрп ръфеярх ялеыюеряъ б ндмнл мюопюбкемхх (бопюбн, еякх ашрэ рнвмшл). Опнцпюллю опхлевюрекэмю б рнл ялшяке, врн, йюйхе аш опеднупюмхрекх лш мх бшапюкх, мхйнцдю ме бнгмхймер ноюямнярх мюпсьемхъ хярхммнярх П: опеднупюмхрекх, хяонкэгселше б мюьел опхлепе, ъбкъчряъ вхяршл якедярбхел менаундхлнярх гюбепьемхъ опнцпюллш. {\sl Гюлевюмхе.} Гюлерэре, врн лш лнцкх аш днаюбхрэ рюйфе х дпсцхе бюпхюмрш, рюйхе, йюй \prg q1>q3 \to q1, q3 := q3, q1 \grp опхвел ху мекэгъ хяонкэгнбюрэ дкъ гюлемш ндмнцн хг рпеу, оепевхякеммшу б опнцпюлле. {\sl (Йнмеж гюлевюмхъ.)} Щрн унпньхи опхлеп рнцн, йюйнцн пндю ъямнярх лнфмн днярхвэ опх мюьеи медереплхмхпнбюммнярх; хгкхьме цнбнпхрэ ндмюйн, врн ъ ме пейнлемдсч янпрхпнбюрэ анкэьне йнкхвеярбн гмювемхи юмюкнцхвмшл яонянанл. {\sl Оърши опхлеп} Мюл рпеасеряъ янярюбхрэ опнцпюллс юоопнйяхлюжхх йбюдпюрмнцн йнпмъ; анкее рнвмн: дкъ тхйяхпнбюммнцн $n$ $(n>0)$ опнцпюллю днкфмю наеяоевхрэ хярхммнярэ $$ R: a^2\le n \and (a+1)^2>n $$ Врнаш някюахрэ щрн нрмньемхе, лнфмн, мюопхлеп, нрапняхрэ ндхм хг кнцхвеяйху янлмнфхрекеи, яйюфел онякедмхи, х яняпеднрнвхрэяъ мю $$ P: a^2\le n $$ Нвебхдмн, врн щрн нрмньемхе бепмн опх $a=0$, онщрнлс бшанп мювюкэмнцн гмювемхъ ме днкфем мюя аеяонйнхрэ. Лш бхдхл, врн еякх брнпни вкем ме ъбкъеряъ хярхммшл, рн щрн бшгшбюеряъ якхьйнл люкемэйхл гмювемхел $a$, онщрнлс лш лнцкх аш напюрхрэяъ й ноепюрнпс "$a:=a+1$". Тнплюкэмн лш онксвюел $$ \wp ("a := a + 1 ", P)=((a + 1)^2\le n) $$ Хяонкэгсъ щрн сякнбхе б йювеярбе (едхмярбеммнцн!) опеднупюмхрекъ, лш онксвюел $(P \and \non BB) =R$ х опхундхл й якедсчыеи опнцпюлле: \prg \.{if} n\GE 0 \TO a:=0 \{П ярюкн хярхммшл\}; \.{do} (a+1)^2\LE n\to a:=a+1 \{P нярюкняэ хярхммшл\} \.{od} \{R ярюкн хярхммшл \} \.{fi} \{R ярюкн хярхммшл \} \grp Опх янярюбкемхх опнцпюллш лш хяундхкх хг опедонкнфемхъ, врн нмa гюбепьхряъ, х щрн деиярбхрекэмн рюй, оняйнкэйс йнпемэ хг менрпхжюрекэмнцн вхякю еярэ лнмнрнммн бнгпюярючыюъ тсмйжхъ: б йювеярбе $t$ лш лнфел бгърэ тсмйжхч $n-a^2$. Щрю опнцпюллю днбнкэмн нвебхдмю, й рнлс фе нмю х ме нвемэ щттейрхбмю: опх анкэьху гмювемхъу $n$ нмю асдер пюанрюрэ днбнкэмн днкцн. Дпсцни яоняна нанаыемхъ R --- щрн ббедемхе дпсцни оепелеммни (яйюфел, $b$ --- х ямнбю б нцпюмхвеммнл хмрепбюке хглемемхъ), йнрнпюъ гюлемхр вюярэ $R$, мюопхлеп, $$ P:\quad a^2 \le n \and b^2>n \and 0\le an) $$ Оняйнкэйс хярхммнярэ брнпнцн вкемю якедсер хг хярхммнярх $P$, лш лнфел хяонкэгнбюрэ оепбши вкем б йювеярбе мюьецн оепбнцн опеднупюмхрекъ; юмюкнцхвмн бшбндхряъ брнпни опеднупюмхрекэ, х лш онксвюел нвепедмсч тнплс мюьеи опнцпюллш: \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} \{П нярюкняэ хярхммшл\} \.{od} \{R ярюкн хярхммшл\} \grp Мюл нярюеряъ еые яннрберярбсчыхл напюгнл бшапюрэ $d$. Оняйнкэйс лш бгъкх $b-a$ (мю яюлнл деке, $b-ю-1$) б йювеярбе мюьеи тсмйжхх $t$, щттейрхбмне сашбюмхе днкфмн ашрэ рюйхл, врнаш d сднбкербнпъкн сякнбхч $d>0$. Йпнле рнцн, онякедсчыюъ йнмярпсйжхъ бшанпю ме днкфмю опхбндхрэ й нрйюгс, р. е. он йпюимеи лепе ндхм хг опеднупюмхрекеи днкфем ашрэ хярхммшл. Щрн гмювхр, врн хг нрпхжюмхъ ндмнцн, $(a+d)^2>n$, днкфем якеднбюрэ дпсцни, $(b-d)^2>n$; щрн цюпюмрхпсеряъ, еякх $$ a+d\le b-d $$ хкх $$ 2*d\le b-a $$ Мюпъдс я мхфмеи цпюмхжеи лш сярюмнбхкх рюйфе х бепумчч цпюмхжс дкъ $d$. Лш лнцкх аш бгърэ $d=1$, мн вел анкэье $d$, рел ашярпее пюанрюер опнцпюллю, онщрнлс лш опедкюцюел \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 цде $n\div 2$ еярэ $n/2$, еякх $2|n$ х $(n-1)/2$, еякх $2|(n-1)$. Хяонкэгнбюмхе деиярбхъ $\div$ онасфдюер мюя пюгнапюряъ б рнл, врн опнхгнидер, еякх лш мюбъфел яеае нцпюмхвемхе мю $b-a$, онкюцюъ, врн $b-a$ вермн опх йюфднл бшвхякемхх $d$. Ббндъ $c=(b-a)$ х хяйкчвюъ $b$, лш онксвюел хмбюпхюмрмне нрмньемхе $$ P:\qquad a^2\le n \and (a+c)^2 > n \and (\exists i: i\ge 0 : c=2^i) $$ х опнцпюллс (б йнрнпни $c$ хцпюер пнкэ $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{опносярхрэ} \.{fi} \.{od} \grp {\sl Гюлевюмхе.} Щрю опнцпюллю нвемэ онунфю мю онякедмчч опнцпюллс дкъ рперэецн опхлепю, цде бшвхякъкяъ нярюрнй б опедонкнфемхх, врн лш хлеел опюбн слмнфюрэ х декхрэ мю 3. Б опхбедеммни бшье опнцпюлле лнфмн ашкн аш гюлемхрэ йнмярпсйжхч бшанпю мю \prg \.{dн} (a+c)^2 \LE n \TO a:=a+c \.{od} \grp Еякх сякнбхе, йнрнпнлс днкфем сднбкербнпърэ нярюрнй, $0\le r < d$, гюохяюрэ йюй $r1)$ х $Y\ (Y\ge 0)$ опнцпюллю днкфмю наеяоевхрэ хярхммнярэ нрмньемхъ $$ R: \quad z=X^Y $$ опх нвебхдмнл опедонкнфемхх, врн ноепюжхъ бнгбедемхъ б яреоемэ ме бундхр б мюанп днярсомшу ноепюжхи. Щрю гюдювю лнфер ашрэ пеьемю опх онлных "юаярпюйрмни оепелеммни", яйюфел $h$; опх пеьемхх гюдювх лш асдел онкэгнбюрэяъ жхйкнл, дкъ йнрнпнцн хмбюпхюмрмшл ъбкъеряъ нрмньемхе $$ P:\qquad h * z=X^Y $$ х мюью (б пюбмни яреоемх "юаярпюйрмюъ") опнцпюллю лнцкю аш бшцкъдерэ рюй: \prg h,z:=У^Y,1 \{P ярюкн хярхммшл\}; \.{do} h \NE 1\TO яфхлюрэ $h$ опх хмбюпхюмрмнярх $P$ \.{od} \{ R ярюкн хярхммшл \} \grp Онякедмее гюйкчвемхе яопюбедкхбн, оняйнкэйс $(P \and h=1)\Rightarrow R$. Опхбедеммюъ бшье опнцпюллю опхдер й гюбепьемхч, еякх оняке йнмевмнцн вхякю опхлемемхи ноепюжхх "яфхлюмхъ" $h$ ярюмер пюбмшл 1. Опнакелю, йнмевмн, б рнл, врн лш ме лнфел опедярюбхрэ гмювемхе $h$ гмювемхел йнмйпермни оепелеммни, я йнрнпшл меоняпедярбеммн ноепхпсер люьхмю; еякх аш лш лнцкх рюй ядекюрэ, лш лнцкх аш япюгс опхябнхрэ $z$ гмювемхе $X^Y$, ме гюрпсдмъъ яеаъ ббедемхел $h$. Тнйся б рнл, врн дкъ опедярюбкемхъ рейсыецн гмювемхъ $h$ лш лнфел ббеярх дбе --- мю щрнл спнбме йнмйпермше --- оепелеммше, яйюфел $x$ х $y$, х мюье оепбне опхябюхбюмхе опедкюцюер б йювеярбе янцкюьемхъ на щрнл опедярюбкемхх $$ h=x^y $$ Рнцдю сякнбхе "$h\not=1$" оепеундхр б сякнбхе "$y\not=0$", х мюью якедсчыюъ гюдювю янярнхр б рнл, врнаш ондшяйюрэ бшонкмхлсч ноепюжхч "яфхлюмхъ". Оняйнкэйс опх щрни ноепюжхх опнхгбедемхе $h*z$ днкфмн нярюбюрэяъ хмбюпхюмрмшл, лш днкфмш декхрэ $h$ мю рс фе бекхвхмс, мю йнрнпсч слмнфюеряъ $z$. Хяундъ хг опедярюбкемхъ $h$, мюханкее еяреярбеммшл йюмдхдюрнл мю щрс бекхвхмс лнфмн явхрюрэ рейсыее гмювемхе $x$. Аег дюкэмеиьху гюрпсдмемхи лш опхундхл й рюйнлс бхдс мюьеи юаярпюйрмни опнцпюллш: \prg x,y,z:=X,Y,1 \{P ярюкн хярхммшл\}; \.{do} y\NE 0 \TO y,z:=y-1, z*x \{P нярюкняэ хярхммшл\} \.{od} \{R ярюкн хярхммшл\} \grp Цкъдъ мю щрс опнцпюллс, лш онмхлюел, врн вхякн бшонкмемхи жхйкю пюбмн оепбнмювюкэмнлс гмювемхч $Y$, х лнфел гюдюрэ яеае бнопня, мекэгъ кх сяйнпхрэ опнцпюллс. Ъямн, врн гюдювеи нупюмъелни йнлюмдш ъбкъеряъ ябедемхе $y$ й мскч; ме хглемъъ \emph{гмювемхъ} $h$, лш лнфел опнбепхрэ, мекэгъ кх хглемхрэ \emph{опедярюбкемхе} щрнцн гмювемхъ б мюдефде слемэьхрэ гмювемхе $y$. Оношрюеляъ бняонкэгнбюрэяъ рел тюйрнл, врн йнмйпермне опедярюбкемхе гмювемхъ $h$, гюдюммне йюй $x^y$, бнбяе ме ъбкъеряъ ндмнгмювмшл. Еякх $y$ вермн, лш лнфел пюгдекхрэ $y$ мю 2 х бнгбеярх $x$ б йбюдпюр, опх щрнл гмювемхе $h$ янбяел ме хглемхряъ. Меоняпедярбеммн оепед ноепюжхеи яфхлюмхъ лш бярюбкъел опенапюгнбюмхе, опхбндъыее й мюханкее опхбкейюрекэмнлс опенапюгнбюмхч $h$ х онксвюел якедсчысч опнцпюллс: \prg x,y,z:=X,Y,1; \.{do} y\NE0 \TO \.{do} 2 | y\TO x, с:= x*x, y/2 \.{od}; y,z:=y-1,z*x \.{od} \{R ярюкн хярхммшл \} \grp Ясыеярбсер рнкэйн ндмю бекхвхмю, йнрнпсч лнфмн аеяйнмевмн декхрэ ононкюл х нмю ме ярюмер мевермни, щрю бекхвхмю --- мскэ; хмюве цнбнпъ, бмеьмхи опеднупюмхрекэ цюпюмрхпсер мюл, врн бмсрпеммхи жхйк опхдер й гюбепьемхч. Ъ бйкчвхк щрнр опхлеп он пюгмшл опхвхмюл. Лемъ онпюгхкн нрйпшрхе, врн еякх опнярн бярюбхрэ б опнцпюллс врн-рн, врн мю юаярпюйрмнл спнбме деиярбсер йюй осярни ноепюрнп, лнфмн рюй хглемхрэ юкцнпхрл, врн вхякн ноепюжхи, йнрнпне пюмэье ашкн опнонпжхнмюкэмн $Y$, ярюмер опнонпжхнмюкэмн рнкэйн $\log (Y)$. Щрн нрйпшрхе ашкн опълшл якедярбхел рнцн, врн ъ гюярюбхк яеаъ дслюрэ б реплхмюу нрдекэмни юаярпюйрмни оепелеммни. Опнцпюллю бнгбедемхъ б яреоемэ, йнрнпсч ъ гмюк, ашкю якедсчыеи: \prg x,y,z:=У,Y,1; \.{do} y<>0 \TO \.{if} \non 2| y\TO y,z:=y-1,z*x \wbox 2|y \TO\var{опносярхрэ} \.{fi}; x,y:=x*x,y/2 \.{od} \grp Щрю онякедмъъ опнцпюллю нвемэ унпньн хгбеярмю, лмнцхе хг мюя опхькх й меи мегюбхяхлн дпсц нр дпсцю. Оняйнкэйс онякедмее бнгбедемхе $x$ б йбюдпюр, йнцдю $y$ ярюк пюбмшл мскч, сфе хгкхьме, мю щрс опнцпюллс вюярн яяшкюкхяэ йюй мю опхлеп, ондрбефдючыхи менаундхлнярэ хлерэ рн, врн лш мюгбюкх аш "опнлефсрнвммшлх бшундюлх". Опхмхлюъ бн бмхлюмхе мюьс опнцпюллс, ъ опхунфс й гюйкчвемхч, врн щрнр днбнд якюа. {\sl Яедэлни опхлеп } Дкъ тхйяхпнбюммнцн гмювемхъ $n$ $(n\ge 0)$ гюдюмю тсмйжхъ $f(i)$ дкъ $0\le i