\input style \chapno=6\subchno=1\chapnotrue %% 483 \subchap{ОНХЯЙ ОНЯПЕДЯРБНЛ ЯПЮБМЕМХЪ ЙКЧВЕИ} %% 6.2 Б щрнл оюпюцпюте лш пюяялнрпхл лерндш онхяйю, нямнбюммше мю кхмеимнл сонпъднвемхх йкчвеи (мюопхлеп, онпъднй лнфер ашрэ вхякнбшл хкх юктюбхрмшл). Оняке япюбмемхъ дюммнцн юпцслемрю~$K$ я йкчвнл~$K_i$ хг рюакхжш онхяй опнднкфюеряъ ндмхл хг рпеу яонянанб б гюбхяхлнярх нр рнцн, йюйне хг яннрмньемхи бепмн: $KK_i$. Опх онякеднбюрекэмнл онхяйе лш, б ясымнярх, днкфмш бшахпюрэ ндмн хг дбсу опнднкфемхи ($K=K_i$ хкх~$K\ne K_i$), мн еякх лш нябнандхляъ нр нцпюмхвемхъ хлерэ кхьэ онякеднбюрекэмши днярсо й рюакхже, рн онксвхл бнглнфмнярэ щттейрхбмн хяонкэгнбюрэ нрмньемхе онпъдйю. \subsubchap{ Онхяй б сонпъднвеммни рюакхже} % 6.2.1 Врн бш ярюмере декюрэ, еякх бюл бпсвюр анкэьсч рекетнммсч ймхцс х онопняър мюирх хлъ векнбейю, мнлеп рекетнмю йнрнпнцн 795-68-41? Гю мехлемхел ксвьецн опхдеряъ бняонкэгнбюрэяъ лерндюлх онякеднбюрекэмнцн онхяйю, хгкнфеммшлх б \S~6.1. (Опюбдю, кнбйхи вюярмши дерейрхб лнц аш оношрюрэяъ мюапюрэ мнлеп х яопняхрэ, йрн цнбнпхр; ме хяйкчвемн рюйфе, врн с мецн еярэ дпсгэъ мю рекетнммни ярюмжхх, хлечыхе днярсо й яопюбнвмхйюл, цде рекетнмш пюяонкнфемш б онпъдйе бнгпюярюмхъ мнлепнб.) Декн б рнл, врн цнпюгдн кецве мюирх гюохяэ он тюлхкхх юанмемрю, ю ме он мнлепс, унръ рекетнммюъ ймхцю яндепфхр бяч хмтнплюжхч, мсфмсч б нанху яксвюъу. Еякх менаундхлн мюирх гюохяэ б анкэьнл тюике, н онякеднбюрекэмнл онхяйе онврх ме лнфер ашрэ певх, мн хяонкэгнбюмхе нрмньемхъ онпъдйю б нцпнлмни яреоемх накецвюер пюанрс. Б мюьел пюяонпъфемхх еярэ лмнцн лернднб янпрхпнбйх (цк.~5), онщрнлс дкъ мюя ме янярюбхр рпсдю сонпъднвхрэ тюик, врнаш гюрел ашярпее опнхгбеярх онхяй. Пюгслееряъ, еякх мсфем кхьэ ндмнйпюрмши опнялнрп, рн ашярпее опнхгбеярх ецн онякеднбюрекэмн, аег опедбюпхрекэмни янпрхпнбйх. Мн еякх б ндмни х рни фе рюакхже опхундхряъ вюярн опнхгбндхрэ онхяй, рн щттейрхбмее сонпъднвхрэ ее. Б щрнл осмйре лш хгсвхл лерндш онхяйю б рюакхжюу ян яксвюимшл днярсонл х сонпъднвеммшлх йкчвюлх $$ K_1K_i \rem{[$R_1$, $R_2$,~\dots, $R_i$ хяйкчвючряъ хг пюяялнрпемхъ].}\cr } $$ Слекн деиярбсъ б йюфднл хг щрху яксвюеб, лш ящйнмнлхл лмнцн бпелемх он япюбмемхч я онякеднбюрекэмшл онхяйнл, еякх рнкэйн $i$ ме якхьйнл акхгйн й йнмжюл рюакхжш. Рюйхл напюгнл, сонпъднвемхе бедер й щттейрхбмшл юкцнпхрлюл. \section Ахмюпмши онхяй. Онфюкси, оепбшл опхундхр б цнкнбс якедсчыхи нвебхдмши лернд: ямювюкю япюбмхрэ~$K$ ян япедмхл йкчвнл б рюакхже. Пегскэрюр япюбмемхъ онгбнкхр нопедекхрэ, б йюйни онкнбхме тюикю опнднкфхрэ онхяй, опхлемъъ й меи рс фе опнжедспс, х р. д. Оняке ме анкее вел опхлепмн $\log_2 N$ япюбмемхи кхан йкчв асдер мюидем, кхан асдер сярюмнбкемн ецн нрясрярбхе. Рюйюъ опнжедспю хмнцдю мюгшбюеряъ "кнцюпхтлхвеяйхл онхяйнл" хкх "лернднл декемхъ ононкюл", мн мюханкее сонрпеахрекэмши реплхм---\dfn{ахмюпмши онхяй.} Нямнбмюъ хдеъ ахмюпмнцн онхяйю днбнкэмн опнярю, дерюкх фе мерпхбхюкэмш, х дкъ лмнцху унпньху опнцпюллхярнб ме ндмю оношрйю мюохяюрэ опюбхкэмсч опнцпюллс гюйнмвхкюяэ месдювеи. Ндмю хг мюханкее оноскъпмшу пеюкхгюжхх лерндю хяонкэгсер дбю сйюгюрекъ---$l$ х~$u$, яннрберярбсчыхе бепумеи х мхфмеи цпюмхжюл онхяйю, х янярнхр б якедсчыел. \alg Б.(Ахмюпмши онхяй.) Я онлныэч дюммнцн юкцнпхрлю пюгшяйхбюеряъ юпцслемр~$K$ б рюакхже гюохяеи $R_1$, $R_2$,~\dots, $R_N$, йкчвх йнрнпшу пюяонкнфемш б бнгпюярючыел онпъдйе: $K_1K_i$, рн оепеирх мю~\stp{5}; еякх $K=K_i$, юкцнпхрл гюйюмвхбюеряъ сдювмн. \st[Йнппейрхпнбйю~$u$]. Сярюмнбхрэ $u\asg i-1$ х бепмсрэяъ й ьюцс~\stp{2}. \st[Йнппейрхпнбйю~$l$.] Сярюмнбхрэ $l\asg i+1$ х бепмсрэяъ й ьюцс~\stp{2}. \algend %%485 \picture{Пхя. 3. Ахмюпмши онхяй.} Пхясмнй~4 хккчярпхпсер онбедемхе юкцнпхрлю Б б дбсу яксвюъу: йнцдю пюгшяйхбюеряъ юпцслемр, пюбмши хлечыелсяъ б рюакхже вхякс~653, х йнцдю пюгшяйхбюеряъ нрясрярбсчыхи юпцслемр~400. Яйнайх яннрберярбсчр сйюгюрекъл $l$ х~$u$, ондвепймсрши йкчв опедярюбкъер~$K_i$. Б нанху яксвюъу онхяй йнмвюеряъ оняке вершпеу япюбмемхи. \prog B.(Ахмюпмши онхяй.) Йюй х б опнцпюллюу \S~6.1, опедонкюцюеряъ, врн $K_i$ гюмхлюер онкмне якнбн он юдпеяс $|KEY|+i$. Опхбндхлюъ мхфе опнцпюллю хяонкэгсер $|rI1|\equiv l$, $|rI2|\equiv u$, $|rI3|\equiv i$. {\catcode`\!=\active\def!#1.{\underline{#1}} \catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}} \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}} $$ \displaylines{ \matrix{ \vbox{\halign{$\phantom{[}#\phantom{]}$\bskip&&$\phantom{[}#\phantom{]}$\bskip\cr \noalign{\hbox{a)~Онхяй вхякю 653:}} [061 & 087 & 154 & 170 & 275 & 426 & 503 &!509.& 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 & 612 & 653 &!677.& 703 & 765 & 897 & 908]\cr 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 &!612.& 653] & 677 & 703 & 765 & 897 & 908 \cr 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 &[!653.]& 677 & 703 & 765 & 897 & 908 \cr }}\hfill\cr \vbox{\halign{$#$\bskip&&$#$\bskip\cr \noalign{\hbox{b)~Онхяй вхякю 400:}} [061 & 087 & 154 & 170 & 275 & 426 & 503 &!509.& 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr [061 & 087 & 154 &!170.& 275 & 426 & 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr 061 & 087 & 154 & 170 & [275 &!426.& 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr 061 & 087 & 154 & 170 &[!275.]& 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr 061 & 087 & 154 & 170 & 275] &[426 & 503 & 509 & 512 & 612 & 658 & 677 & 703 & 765 & 897 & 908 \cr }}\hfill\cr }\cr \hbox{Пхя. 4. Опхлепш ахмюпмнцн онхяйю.}\cr } $$ } %%486 \code START & ENT1 & 1 & 1 & Bl. Мювюкэмюъ сярюмнбйю. $l\asg 1$. & ENT2 & N & 1 & $u\asg N$. & JMP & 2F & 1 & Мю B2. 5H & JE & SUCCESS & C1 & Оепеунд, еякх $K=K_i$. & ENT1 & 1,3 & C1-S& B5. Йнппейрхпнбйю $l$. $l\asg l+1$. 2H & ENTA & 0,1 &C+1-S& B2. Мюунфдемхе яепедхмш. & INCA & 0,2 &C+1-S& $|rA|\asg l+u$. & SRB & 1 &C+1-S& $|rA|\asg\floor{|rA|/2}$. (Лемъеряъ х~|rX|.) & STA & TEMP &C+1-S& & CMP1 & TEMP &C+1-S& & JG & FAILURE &C+1-S& Оепеунд, еякх $uK_8$, хяонкэгсеряъ опюбне онддепебн. Месдювмши онхяй бедер б ндхм хг "бмеьмху" йбюдпюрмшу сгкнб, гюмслепнбюммшу нр~\leaf{0} дн~\leaf{$N$}; мюопхлеп, лш днярхцмел сгкю~\leaf{6} рнцдю х рнкэйн рнцдю, йнцдю $K_6K_8$, $KK_i$, рн оепеирх мю~\stp{4}; опх $K=K_i$ юкцнпхрл нйюмвхбюеряъ сдювмн. \st[Слемэьемхе $i$.] (Лш нопедекхкх онкнфемхе хмрепбюкю, цде мсфмн опнднкфюрэ онхяй. Нм яндепфхр $m$ хкх $m-1$~гюохяеи; $i$ сйюгшбюер мю оепбши щкелемр яопюбю нр хмрепбюкю.) Еякх $m=0$, рн юкцнпхрл нйюмвхбюеряъ месдювмн. Б опнрхбмнл яксвюе сярюмнбхрэ $i\asg i-\ceil{m/2}$; $m\asg\floor{m/2}$ х бепмсрэяъ мю~\stp{2}. \st[Сбекхвемхе $i$.] (Яхрсюжхъ рю фе, врн х б ьюце~\stp{3}, рнкэйн $i$~сйюгшбюер мю оепбши щкелемр \emph{якебю} нр хмрепбюкю.) Еякх $m=0$, рн юкцнпхрл нйюмвхбюеряъ месдювмн. Б опнрхбмнл яксвюе сярюмнбхрэ $i\asg i+\ceil{m/2}$; $m\asg\floor{m/2}$ х бепмсрэяъ мю~\stp{2}. \algend Мю пхя.~6 опедярюбкемн ахмюпмне депебн, яннрберярбсчыее онхяйс опх $N=10$. Опх месдювмнл онхяйе йюй пюг оепед нйнмвюмхел %%490 пюанрш юкцнпхрлю лнфер опнхгбндхрэяъ кхьмее япюбмемхе; сгкш, нрбевючыхе щрхл япюбмемхъл, гюьрпхунбюмш. Дюммши опнжеяя онхяйю лнфмн мюгбюрэ \emph{ндмнпндмшл}, рюй йюй пюгмнярэ лефдс вхякнл б сгке спнбмъ~$\ell$ х вхякнл б сгке-опедьеярбеммхйе спнбмъ~$\ell-1$ еярэ онярнъммюъ бекхвхмю~$\delta$ дкъ бяеу сгкнб спнбмъ~$\ell$. Нанямнбюрэ опюбхкэмнярэ юкцнпхрлю~U лнфмн якедсчыхл напюгнл. Опедонкнфхл, врн онхяй мсфмн опнхгбеярх б хмрепбюке \picture{Пхя. 6. Ахмюпмне депебн дкъ "ндмнпндмнцн" ахмюпмнцн онхяйю ($N=10$).} дкхмш~$n-1$; япюбмемхе ян япедмхл щкелемрнл (еякх $n$ вермн) хкх я ндмхл хг дбсу япедмху (еякх $n$ мевермн) бшдекъер дбю хмрепбюкю дкхмш~$\floor{n/2}-1$ х~$\ceil{n/2}-1$. Оняке онбрнпемхъ щрни опнжедспш $k$~пюг лш онксвхл $2^k$~хмрепбюкнб я лхмхлюкэмни дкхмни~$\floor{n/2^k}-1$ х люйяхлюкэмни дкхмни~$\ceil{n/2^k}-1$. Якеднбюрекэмн, мю йюфднл щрюое дкхмш дбсу хмрепбюкнб пюгкхвючряъ яюлне анкэьее мю~1, врн декюер бнглнфмшл бшанп ондундъыецн "япедмецн" щкелемрю аег гюонлхмюмхъ онякеднбюрекэмнярх рнвмшу гмювемхи дкхм. Бюфмне опехлсыеярбн юкцнпхрлю~U янярнхр б рнл, врн мюл янбяел ме мсфмн янупюмърэ гмювемхе~$m$; мсфмн кхьэ яяшкюрэяъ мю йнпнремэйсч рюакхжс гмювемхи~$\delta$ дкъ йюфднцн спнбмъ. Рюйхл напюгнл, юкцнпхрл ябндхряъ й якедсчыеи опнжедспе, ндхмюйнбн унпньеи х дкъ дбнхвмшу, х дкъ деяърхвмшу ЩБЛ. \alg C.(Ндмнпндмши ахмюпмши онхяй.) Юкцнпхрл юмюкнцхвем юкцнпхрлс~U, мн блеярн бшвхякемхи, нрмняъыхуяъ й~$m$, хяонкэгсер бяонлнцюрекэмсч рюакхжс бекхвхм $$ |DELTA|[j]=\floor{{N+2^{j-1}\over 2^j}}=\left({N\over 2^j}\right) \hbox{ нйпсцкеммне}; \qquad 1\le j \le \floor{\log_2 N}+2. \eqno(6) $$ \st[Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ $i\asg|DELTA| [1]$, $j\asg2$. %%491 \st[Япюбмемхе:] Еякх $KK_i$, рн оепеирх мю~\stp{4}. Опх $K=K_i$ юкцнпхрл нйюмвхбюеряъ сдювмн. \st[Слемэьемхе $i$.] Еякх $|DELTA|[j]=0$, рн юкцнпхрл нйюмвхбюеряъ месдювмн. Б опнрхбмнл яксвюе сярюмнбхрэ $i\asg i-|DELTA|[j]$, $j\asg j+1$ х бепмсрэяъ мю~\stp{2}. \st[Сбекхвемхе~$i$.] Еякх $|DELTA|[j]=0$, юкцнпхрл нйюмвхбюеряъ месдювмн. Б опнрхбмнл яксвюе сярюмнбхрэ $i\asg i+|DELTA|[j]$, $j\asg j+1$ х бепмсрэяъ мю~\stp{2}. \algend Б соп.~8 асдер онйюгюмн, врн юкцнпхрл яяшкюеряъ мю бяонлнцюрекэмши йкчв~$K_0=-\infty$ кхьэ опх вермшу~$N$. \prog C.(Ндмнпндмши ахмюпмши онхяй.) Щрю опнцпюллю мю аюге юкцнпхрлю~C опндекшбюер рс фе пюанрс, врн х опнцпюллю~B. Хяонкэгсчряъ $|rA|\equiv K$, $|rI1|\equiv i$, $|rI2|\equiv j$, $|rI3|\equiv |DELTA| [j]$. \code START & ENT1 & N+1/2 & 1 & C1. Мювюкэмюъ сярюмнбйю. & ENT2 & 2 & 1 & $j\asg 2$. & LDA & Й & 1 & & JMP & 2F & 1 & 3H & JE & SUCCESS& C1 & Оепеунд, еякх $K=K_i$. & J3Z & FAILURE& C1-S & Оепеунд, еякх $|DELTA|[j]=0$. & DEC1 & 0,3 & C1-S-A& C3. Слемэьемхе~$i$. 5H & INC2 & 1 & C-1 & $j\asg j+1$. 2H & LD3 & DELTA,2& C & C2. Япюбмемхе. & ЯЛПЮ & KEY.1 & C & & JLE & 3B & C & Оепеунд, еякх $K\le K_i$. & INC1 & 0,3 & C2 & C4. Сбекхвемхе $i$. & J3NZ & 5B & C2 & Оепеунд, еякх $|DELTA|[j]\ne0$. FAILURE& EQU & * & 1-S & Бшунд, еякх мер б рюакхже. \endcode \progend Опх сдювмнл онхяйе щрнр юкцнпхрл яннрберярбсер ахмюпмнлс депебс я рни фе дкхмни бмсрпеммецн осрх, врн х юкцнпхрл~Б, онщрнлс япедмее вхякн япюбмемхи~$C_N$ дюеряъ тнплскни~(4). Опх месдювмнл онхяйе юкцнпхрл~C бяецдю янбепьюер пнбмн $\floor{\log_2N}+1$~япюбмемхи. Онкмне бпелъ пюанрш опнцпюллш~C ме бонкме яхллерпхвмн он нрмньемхч й кебшл х опюбшл бербъл, рюй йюй $C1$ хлеер бея, анкэьхи вел $C2$, мн б соп.~9 асдер онйюгюмн, врн яксвюи $K>K_i$ бярпевюеряъ опхлепмн рюй фе вюярн, йюй х~$KK_i$ х~$N>2^k$ сярюмюбкхбюел $i=i'=N+1-2^\ell$, цде $\ell=\floor{\log_2(N-2^k)}+1$, х, декюъ бхд, врн оепбшл япюбмемхел ашкн $K>K_{i'}$, хяонкэгсел ндмнпндмши онхяй я $\delta=2^{\ell-1}$, $2^{\ell-2}$,~\dots, $1$, $0$. Пхясмнй~7 хккчярпхпсер лернд Ьепю опх $N=10$. Б лернде Ьепю мхйнцдю ме рпеасеряъ анкее $\floor{\log_2 N}+1$~япюбмемхи; якеднбюрекэмн, нм дюер ндмн хг ксвьху япедмху вхяек япюбмемхъ, меялнрпъ мю рн врн хмнцдю опнундхр вепег меяйнкэйн онякеднбюрекэмшу хгашрнвмшу ьюцнб (яп. я соп.~12). Еые ндмю лндхтхйюжхъ ахмюпмнцн онхяйю, сксвьючыюъ бяе пюяялнрпеммше лерндш опх нвемэ анкэьху $N$, наясфдюеряъ б соп.~23. Б соп.~24 хгкнфем еые анкее ашярпши лернд! \section Тханмюввхеб онхяй. Опх пюяялнрпемхх лмнцнтюгмнцн якхъмхъ (о.~5.4.2) лш бхдекх, врн вхякю Тханмюввх лнцср хцпюрэ пнкэ, юмюкнцхвмсч яреоемъл~$2$. Онунфее ъбкемхе хлеер леярн х б яксвюе онхяйю, йнцдю я онлныэч вхяек Тханмюввх янгдючряъ лерндш, яонянамше яноепмхвюрэ я ахмюпмшл онхяйнл. Опедкюцюелши лернд дкъ мейнрнпшу ЩБЛ опедонврхрекэмее ахмюпмнцн, рюй йюй нм бйкчвюер кхьэ якнфемхе х бшвхрюмхе; мер менаундхлнярх б декемхх мю~$2$. Якедсер нркхвюрэ опнжедспс, йнрнпсч лш янах- %%493 пюеляъ наясфдюрэ, нр хгбеярмни вхякеммни опнжедспш "тханмюввхебю онхяйю", йнрнпюъ хяонкэгсеряъ дкъ мюунфдемхъ люйяхлслю ндмнбепьхммни тсмйжхх [яп.~я~Fibonacci Quarterly, 4 (1966), 265--269]; яунфеярэ мюгбюмхи бедер й мейнрнпни осрюмхже. Мю оепбши бгцкъд тханмюввхеб онхяй йюферяъ беяэлю рюхмярбеммшл; еякх опнярн бгърэ опнцпюллс х оношрюрэяъ на╝ъямхрэ ее пюанрс, рн янгдюяряъ боевюркемхе, врн нмю пюанрюер я онлныэч люцхх. Мн рслюм рюхмярбеммнярх пюяяееряъ, йюй рнкэйн лш онярпнхл \picture{Пхя. 8. Депебн Тханмюввх онпъдйю 6.} яннрберярбсчыее депебн онхяйю. Онщрнлс хгсвемхе пюяялюрпхбюелнцн лерндю мювмел я пюяяйюгю н "тханмюввхебшу депебэъу". Мю пхя.~8 хгнапюфемн депебн Тханмюввх онпъдйю~$6$. Гюлерэре, врн нмн меяйнкэйн анкэье мюонлхмюер пеюкэмши йсяр, вел пюяялюрпхбюбьхеяъ пюмее депебэъ, бнглнфмн, онрнлс, врн лмнцхе опхпндмше опнжеяяш сднбкербнпъчр гюйнмс Тханмюввх. Бннаые тханмюввхебн депебн онпъдйю~$k$ хлеер $F_{k+1}-1$~бмсрпеммху (йпсцкшу) сгкнб х~$F_{k+1}$~бмеьмху (йбюдпюрмшу) сгкнб; нмн ярпнхряъ якедсчыхл напюгнл: {\medskip\narrower \item{Еякх}~$k=0$ хкх~$k=1$, депебн ябндхряъ опнярн й~\leaf{0}. \item{Еякх}~$k\ge2$, йнпмел ъбкъеряъ~\node{F_k}; кебне онддепебн еярэ депебн Тханмюввх онпъдйю~$k-1$; опюбне онддепебн еярэ депебн Тханмюввх онпъдйю~$k-2$ я вхякюлх б сгкюу, сбекхвеммшлх мю~$F_k$. \medskip} \noindent Гюлерхл, врн, гю хяйкчвемхел бмеьмху сгкнб, вхякю, яннрберярбсчыхе опеелмхйюл йюфднцн бмсрпеммецн сгкю, нркхвючряъ нр вхякю б щрнл сгке мю ндмс х рс фе бекхвхмс, ю хлеммн мю вхякн Тханмюввх. Рюй, $5=8-F_4$, $11=8+F_4$ (пхя.~8). Еякх пюгмнярэ ашкю пюбмю~$F_j$, рн мю якедсчыел спнбме яннрберярбсчыюъ %%494 пюгмнярэ янярюбхр дкъ кебни бербх $F_{j-1}$, ю дкъ опюбни~$F_{j-2}$. Рюй, мюопхлеп, $3=5-F_3$, a~$10=11-F_2$. Щрх мюакчдемхъ б янбнйсомнярх я ондундъыхл леуюмхглнл пюяонгмюбюмхъ бмеьмху сгкнб дючр \alg F.(Тханмюввхеб онхяй.) Юкцнпхрл опедмюгмювюеряъ дкъ онхяйю юпцслемрю~$K$ б рюакхже гюохяеи $R_1$, $R_2$,~\dots, $R_N$, пюяонкнфеммшу б онпъдйе бнгпюярюмхъ йкчвеи $K_1K_i$, рн оепеирх мю~\stp{4}; еякх $K=K_i$, юкцнпхрл гюйюмвхбюеряъ сдювмн. \st[Слемэьемхе~$i$.] Еякх~$q=0$, юкцнпхрл гюйюмвхбюеряъ месдювмн. Еякх~$q\ne 0$, рн сярюмнбхрэ $i\asg i-q$, гюлемхрэ $(p, q)$ мю~$(q, p-q)$ х бепмсрэяъ мю~\stp{2}. \st[Сбекхвемхе~$i$.] Еякх~$p=1$, юкцнпхрл гюйюмвхбюеряъ месдювмн. Еякх~$p\ne1$, сярюмнбхрэ $i\asg i+q$, $p\asg p-q$, $q\asg q-p$ х бепмсрэяъ мю~\stp{2}. \algend Б опхбндхлни мхфе пеюкхгюжхх юкцнпхрлю~F дкъ люьхмш \MIX\ яйнпнярэ сбекхвхбюеряъ гю явер дсакхпнбюмхъ бмсрпеммецн жхйкю, б ндмнл хг щйгелокъпнб йнрнпнцн $p$~упюмхряъ б~|rI2|, ю~$q$---б~|rI3|, б дпсцнл фе пецхярпш лемъчряъ пнкълх; щрн сопныюер ьюц~F3. Мю яюлнл деке опнцпюллю упюмхр б пецхярпюу $p-1$ х~$q-1$, врн сопныюер опнбепйс "$p=1$?" б ьюце~F4. \prog F.(Тханмюввхеб онхяй.) Гмювемхъ пецхярпнб: $|rA|\equiv K$, $|rI1|\equiv i$, $(|rI2|, |rI3|)\equiv p-l$, $(|rI3|, |rI2|)\equiv q-l$. \code START & LDA & K & 1 & F1. Мювюкэмюъ сярюмнбйю. & ENT1& $F_k$ & 1 & $i\asg F_k$. & ENT2& $F_{k-1}-1$& 1 & $p\asg F_{k-1}$. & ENT3& $F_{k-2}-1$& 1 & $q\asg F_{k-2}$. & JMP & F2A & 1 & Мю F2. \twocols F4A & INC1 &1,3 & F4B &INC1 &1,2 & C2-S-A & F4. Сбекхвемхе $i$. $i\asg i+q$. & DEC2 &1,3 & &DEC3 &1,2 & G2-S-A & $p\asg p-q$. & DEC3 &1,2 & &DEC2 &1,3 & G2-S-A & $q\asg q-p$. F2A & CMPA &KEY, 1 & F2Б &CMPA &KEY,1 & G & F2. Япюбмемхе. & JL &F3A & &JL &F3B & G & Мю FГ, еякх $K0$. & JMP &FAILURE& &JMP &FAILURE& 1-S-A & Бшунд, еякх мер б рюакхже. \endtwocols \endcode \progend Б соп.~18 юмюкхгхпсеряъ бпелъ пюанрш щрни опнцпюллш. Пхясмнй~8 онйюгшбюер, ю юмюкхг днйюгшбюер, врн бкебн лш хдел меяйнкэйн вюые, вел бопюбн. Вепег $C$, $C1$ х~$C2-S$ нангмювхл вхякн бшонкмемхи ьюцнб F2, F3 х~F4 яннрберярбеммн. Хлеел $$ \eqalign{ C&=(\ave \phi k/sqrt{5}+O(1), \max k-1), \cr C1&=(\ave k/\sqrt{5}+O(1), \max k-1),\cr C2-S&=(\ave \phi^{-1} k/\sqrt{5}+O(1), \max \floor{k/2}).\cr } \eqno(8) $$ Гмювхр, кебюъ бербэ бшахпюеряъ опхлепмн б $\phi=1.618$~пюгю вюые опюбни (щрн лнфмн ашкн опедбхдерэ, рюй йюй йюфдюъ опнаю декхр пюяялюрпхбюелши хмрепбюк мю дбе вюярх, опхвел кебюъ вюярэ опхлепмн б $\phi$~пюг дкхммее опюбни). Япедмее бпелъ пюанрш опнцпюллш F янярюбкъер опхлепмн $$ \eqalign{ (6\phi k/\sqrt{5}-(2+22\phi)/5)u &\approx (6.252\log_2 N-4.6)u \rem {дкъ сдювмнцн онхяйю;}\cr (6\phi k/\sqrt{5}+(58/(27\phi))/5)u&\approx (6.252\log_2 N+5.8)u \rem{дкъ месдювмнцн онхяйю.}\cr } \eqno(9) $$ Щрн меяйнкэйн ксвье, вел~(7), унръ б мюхусдьел яксвюе опнцпюллю~F пюанрюер опхлепмн $(8.6\log_2 N)u$, р.е. всрэ-всрэ ледкеммее опнцпюллш~Я. \section Хмрепонкъжхнммши онхяй. Гюасдел мю лхмсрс н бшвхякхрекэмшу люьхмюу х опнюмюкхгхпсел, йюй опнхгбндхр онхяй векнбей. Хмнцдю онбяедмебмюъ фхгмэ ондяйюгшбюер осрэ й янгдюмхч унпньху юкцнпхрлнб. Опедярюбэре, врн бш хыере якнбн б якнбюпе. Люкнбепнърмн, врн бш ямювюкю гюцкъмере б яепедхмс якнбюпъ, гюрел нрярсохре нр мювюкю мю~$1/4$ хкх~$3/4$ х~р.~д., йюй б ахмюпмнл онхяйе, х сф янбяел мебепнърмн, врн бш бняонкэгсереяэ тханмюввхебшл онхяйнл! Еякх мсфмне якнбн мювхмюеряъ я асйбш~A, бш, он-бхдхлнлс, мювмере онхяй цде-рн б мювюке якнбюпъ. Бн лмнцху якнбюпъу %%496 хлечряъ "онасйбеммше бшяевйх" дкъ анкэьнцн оюкэжю, йнрнпше онйюгшбючр ярпюмхжс, цде мювхмючряъ якнбю мю дюммсч асйбс. Рюйсч оюкэжебсч реумхйс кецйн опхяонянахрэ й ЩБЛ, врн сяйнпхр онхяй; яннрберярбсчыхе юкцнпхрлш хяякедсчряъ б \S~6.3. Йнцдю мюидемю нропюбмюъ рнвйю дкъ онхяйю, бюьх дюкэмеиьхе деиярбхъ люкн онунфх мю пюяялнрпеммше лерндш. Еякх бш гюлерхре, врн мсфмне якнбн днкфмн мюундхрэяъ цнпюгдн дюкэье нрйпшрни ярпюмхжш, бш опносярхре онпъднвмне ху йнкхвеярбн, опефде вел ядекюрэ якедсчысч оношрйс. Щрн б йнпме нркхвюеряъ нр опедшдсыху юкцнпхрлнб, йнрнпше ме декючр пюгкхвхъ лефдс "лмнцн анкэье" х "всрэ анкэье". Лш опхундхл й рюйнлс юкцнпхрлс, мюгшбюелнлс "хмрепонкъжхнммшл онхяйнл": еякх хгбеярмн, врн $K$ кефхр лефдс~$K_l$ х~$K_u$, рн якедсчысч опнас декюел опхлепмн мю пюяярнъмхх $(u-l)(K-K_l)/(K_u-K_l)$ нр~$l$, опедонкюцюъ, врн йкчвх ъбкъчряъ вхякюлх, бнгпюярючыхлх опхакхгхрекэмн йюй юпхтлерхвеяйюъ опнцпеяяхъ. Хмрепонкъжхнммши онхяй юяхлорнрхвеяйх опедонврхрекэмее ахмюпмнцн; он ясыеярбс, ндхм ьюц ахмюпмнцн онхяйю слемэьюер йнкхвеярбн "онднгпебюелшу" гюохяеи я~$n$ дн~${1\over2}n$, ю ндхм ьюц хмрепонкъжхнммнцн (еякх йкчвх б рюакхже пюяопедекемш яксвюимшл напюгнл)---я~$n$ дн~$\sqrt{n}$. Лнфмн онйюгюрэ, врн хмрепонкъжхнммши онхяй рпеасер б япедмел нйнкн $\log_2 \log_2 N$~ьюцнб (соп.~22). Й янфюкемхч, щйяоепхлемрш мю ЩБЛ онйюгюкх, врн хмрепонкъжхнммши онхяй слемэьюер вхякн япюбмемхи ме мюярнкэйн, врнаш йнлоемяхпнбюрэ бнгмхйючыхи днонкмхрекэмши пюяунд бпелемх, йнцдю рюакхжю, б йнрнпни опнхгбндхряъ онхяй, упюмхряъ бн бмсрпеммеи ("ашярпни") оюлърх. Пюгмнярэ лефдс $\log_2 \log_2 N$ х~$\log_2 N$ ярюмнбхряъ ясыеярбеммни кхьэ дкъ беяэлю анкэьху~$N$, ю рхохвмше тюикш меднярюрнвмн яксвюимш. Хмрепонкъжхъ сяоеьмю дн мейнрнпни яреоемх кхьэ б опхлемемхх й онхяйс мю \emph{бмеьмху} гюонлхмючыху сярпниярбюу. (Гюлерхл, врн псвмни опнялнрп якнбюпъ еярэ, б ясымнярх, ме бмсрпеммхи, ю бмеьмхи онхяй; щрн ъбкъеряъ релни онякедсчыху пюяялнрпемхи.) \section Хярнпхъ х ахакхнцпютхъ. Оепбшл хгбеярмшл опхлепнл дкхммнцн оепевмъ щкелемрнб, сонпъднвеммшу дкъ накецвемхъ онхяйю, ъбкъеряъ гмюлемхрюъ бюбхкнмяйюъ рюакхжю напюрмшу бекхвхм Inakibit-Anu, дюрхпселюъ опхлепмн 200~ц. дн~м.щ. Щрю цкхмъмюъ окюярхмйю, нвебхдмн, нрйпшбюкю яепхч хг рпеу рюакхвей, яндепфюыху анкее 500 лмнцнгмювмшу ьеярхдеяърепхвмшу вхяек х напюрмшу хл бекхвхм, нрянпрхпнбюммшу б кейяхйнцпютхвеяйнл онпъдйе. Мюопхлеп, бярпевюеряъ рюйюъ онякеднбюрекэмнярэ: %%497 \ctable{ \bskip$#$\bskip&&\bskip$#$\bskip\cr 01&13&09&34&29&08&08&53&20&\qquad&49&12&27\cr 01&13&14&31&52&30& & & & &49&09&07&12\cr 01&13&43&40&48& & & & & &48&49&41&15\cr 01&13&48&40&30& & & & & & 48&46&22&59&25&25&55&33&20\cr 01&14&04&26&40& & & & & &48&36\cr } Янпрхпнбйю 500 онднамшу вхяек япедярбюлх реу бпелем йюферяъ темнлемюкэмни. [Ял. рюйфе D.~Е.~Knuth, {\sl CACM\/}, {\bf 15} (1972), 671--677, цде яндепфхряъ лмнцн днонкмхрекэмшу ябедемхи.] Днбнкэмн еяреярбеммн пюяонкюцюрэ он онпъдйс вхякю, мн нрмньемхе онпъдйю лефдс асйбюлх хкх якнбюлх ме опедярюбкъеряъ яюлн янани нвебхдмшл. Ндмюйн онякеднбюрекэмнярх дкъ япюбмхбюмхъ асйб опхясрярбнбюкх сфе б мюханкее дпебмху юктюбхрюу. Мюопхлеп, лмнцхе ахакеияйхе ояюклш яндепфюр ярхух, якедсчыхе дпсц гю дпсцнл б ярпнцн юктюбхрмнл онпъдйе: оепбши ярху мювхмюеряъ я~юкетю, брнпни я~аерю х~р.~д.; щрн накецвюкн гюонлхмюмхе. Хмнцдю ярюмдюпрмюъ онякеднбюрекэмнярэ асйб хяонкэгнбюкюяэ яелхрюлх х цпейюлх дкъ нангмювемхъ вхяек; мюопхлеп, $\alpha$, $\beta$, $\gamma$ нангмювюкх 1, 2, 3 яннрберярбеммн. Ндмюйн хяонкэгнбюмхе юктюбхрмнцн онпъдйю дкъ якнб жекхйнл ашкн, бепнърмн, цнпюгдн анкее онгдмхл хгнаперемхел; беых, нвебхдмше яеивюя дюфе дкъ пеаемйю, йнцдю-рн рпеанбюкняэ на╝ъямърэ бгпнякшл! Мейнрнпше днйслемрш, дюрхпселше опхлепмн 300~ц. дн~м.щ., мюидеммше мю нярпнбюу Щцеияйнцн лнпъ, яндепфюр яохяйх вкемнб меяйнкэйху пекхцхнгмшу наыхм; нмх сонпъднвемш, мн рнкэйн он оепбни асйбе, р.~е. опедярюбкъчр янани пегскэрюр кхьэ оепбнцн опнундю якебю мюопюбн онпюгпъдмни янпрхпнбйх. Цпевеяйхе оюохпсяш 134--135~ц. м.~щ. яндепфюр тпюцлемрш явернб, б йнрнпшу тюлхкхх мюкнцнокюрекэыхйнб сонпъднвемш он оепбшл дбсл асйбюл. Юонккнмхи Янтхяр% \note{1}{Ндхм хг цпюллюрхйнб дпебмнярх, пнднл хг Юкейяюмдпхх.---{\sl Опхл. оепеб.\/}} хяонкэгнбюк юктюбхрмне сонпъднвемхе он оепбшл дбсл, ю вюярн х он онякедсчыхл асйбюл б ябнел "Якнбюпе цнлепнбяйху якнб" (I~бей м.~щ.). Хгбеярмн меяйнкэйн опхлепнб анкее янбепьеммнцн юктюбхрмнцн сонпъднвемхъ, яйюфел бшдючыхеяъ "Йнллемрюпхх й Цхоонйпюрс" Цюкемю% \note{2}{Пхляйхи бпюв х еяреярбнхяошрюрекэ, йкюяяхй юмрхвмни ледхжхмш.---{\sl Опхл. оепеб.\/}} (нйнкн 200~ц.), мн щрн ашкн нвемэ педйхл ъбкемхел. Рюй, б упнмхйе Яб.~Хяхднпю% \note{3}{Хяхднп Яебхкэяйхи---хяоюмяйхи еохяйно, бшдючыхияъ свемши х охяюрекэ.---{\sl Опхл. оепеб.\/}} "Etymologiarum" (нйнкн 630~ц., ймхцю~X) якнбю сонпъднвемш кхьэ он оепбни асйбе, ю б мюханкее пюммел хг хгбеярмшу дбсъгшвмшу якнбюпеи "Corpus Glossary" (нйнкн 725~ц.) --- рнкэйн он дбсл оепбшл. Дбе онякедмхе пюанрш ашкх, бепнърмн, йпсомеиьхлх мевхякнбшлх тюикюлх дюммшу, яйнлохкхпнбюммшлх б япедмхе бейю. %% 498 Рнкэйн б ймхце Дфнбюммх Цемсщгяйнцн "Catholicon" (1286~ц.) лш мюундхл ондпнамне нохяюмхе опюбхкэмнцн юктюбхрмнцн онпъдйю. Б опедхякнбхх Дфнбюммх на╝ъямъер, врн \ctable{ \hfill\it # \bskip & опедьеярбсер \it #\hfill\cr amo & bibo \cr abeo & adeo \cr amatus & amor \cr imprudens & impudens\cr iusticia & iustus\cr polisintheton & polissenus \cr } (р.~е. опхбндхр опхлепш яхрсюжхи, йнцдю онпъднй нопедекъеряъ он $1$, $2$,~\dots, $6\hbox{-и}$~асйбюл) "х дюкее юмюкнцхвмн". Нм гюлевюер, .врн нрйпшрхе щрнцн опюбхкю онрпеанбюкн гмювхрекэмшу.сяхкхи. "Ъ опньс Бюя, сбюфюелши вхрюрекэ, ме опегхпюрэ щрс лнч анкэьсч пюанрс х щрнр онпъднй йюй меврн мхвецн ме ярнъыее". Пюгбхрхе юктюбхрмнцн онпъдйю дн лнлемрю хгнаперемхъ ймхцноевюрюмхъ ондпнамн хгсвхк К.~С.~Деикх ({\sl Collection Latomus,\/} {\bf 90} (1967), 100~pp.). Нм намюпсфхк меяйнкэйн хмрепеямшу ярюпхммшу псйнохяеи, йнрнпше, меянлмеммн, хяонкэгнбюкхяэ йюй вепмнбхйх опх янпрхпнбйе якнб он оепбни асйбе (ял. ярп.~87--90 ецн лнмнцпютхх). Оепбши якнбюпэ юмцкхияйнцн ъгшйю Пнаепрю Йндпх "Table Alphabeticall" (London, 1604) яндепфхр якедсчыхе хмярпсйжхх: {\narrower Еякх якнбн, йнрнпне реае мсфмн мюирх, мювхмюеряъ я~(a), ялнрпх б мювюкн щрни ймхцх, ю еякх я~(v)---рн б йнмеж. Ноърэ еякх якнбн мювхмюеряъ я~(ca), ялнрпх б мювюкн асйбш~(c), ю еякх я~(cu) рн б йнмеж. Х рюй дн йнмжю якнбю. } \noindent Хмрепеямн гюлерхрэ, врн Йндпх бн бпелъ ондцнрнбйх якнбюпъ, бепнърмн, яюл свхкяъ пюяярюбкърэ якнбю б юктюбхрмнл онпъдйе; мю меяйнкэйху оепбшу ярпюмхжюу бярпевюеряъ лмнцн меопюбхкэмн ярнъыху якнб, гюрн дюкэье вхякн ньханй ясыеярбеммн слемэьюеряъ. Ахмюпмши онхяй боепбше сонлъмср Дфнмнл Лнвкх б дхяйсяяхх, йнрнпюъ ашкю, онфюкси, оепбшл носакхйнбюммшл наясфдемхел лернднб мевхякеммнцн опнцпюллхпнбюмхъ [ял. Theory and techniques for the design of electronic digital computers, ed. by G.~W.~Patterson, 3 (1946); 22.8--22.9]. Б ревемхе 50-у~цнднб лернд ярюмнбхряъ "унпньн хгбеярмшл", мн, йюферяъ, мхйрн ме пюгпюаюршбюк дерюкх юкцнпхрлю дкъ~$N\ne 2^n-1$. [Ял. A.~D.~Booth, {\sl Nature,\/} {\bf 176} (1955), 565; A.~I.~Dumey, {\sl Computers and Automation, \/} {\bf 5} (December, 1956), 7, цде ахмюпмши онхяй хлеер мюгбюмхе "Дбюджюрэ бнопнянб"; D.~D.~McCracken, Digital Computer Programming (Wiley, 1957), 201--203; M.~Halpern, {\sl CACM\/} {\bf 1, 2} (February, 1958), 1--3.] %%499 Он-бхдхлнлс, юкцнпхрл ахмюпмнцн онхяйю, опхцндмши дкъ бяеу~$N$, боепбше носакхйнбюм Анрремапсйнл [{\sl JACM,\/} {\bf 9} (1962), 214]. Нм опедярюбхк хмрепеямсч лндхтхйюжхч юкцнпхрлю~B, йнцдю опнбепйх мю пюбемярбн нрндбхцючряъ б йнмеж юкцнпхрлю. Хяонкэгсъ б ьюце~B2 $i\asg\ceil{(l+u)/2}$ блеярн~$\floor{(l+u)/2}$, нм сярюмюбкхбюер $l\asg i$ опх~$K\ge K_i$; рнцдю $u-l$ слемэьюеряъ оняке йюфднцн ьюцю. Б йнмже, йнцдю $l=u$, хлеел $K_l\le K1$, опх йнрнпшу юкцнпхрлш~Б х~Я юаянкчрмн щйбхбюкемрмш б рнл ялшяке, врн нмх янбепьючр ндхмюйнбше, онякеднбюрекэмнярх япюбмемхи опх бяеу юпцслемрюу онхяйю? \ex[21] На╝ъямхре, йюй мюохяюрэ \MIX-опнцпюллс дкъ юкцнпхрлю~C, яндепфюысч опхлепмн $7\log_2 N$~йнлюмд, бпелъ пюанрш йнрнпни янярюбхр опхакхгхрекэмн $4.5\log_2 N$~едхмхж? \ex[20] Мюпхясире депебн ахмюпмнцн онхяйю, яннрберярбсчыее лерндс Ьепю опх~$N=12$. \ex[Л24] Гюрюаскхпсире япедмхе вхякю япюбмемхи б лернде Ьепю дкъ $1\le N<16$, пюяялюрпхбюъ йюй сдювмше, рюй х месдювмше онхяйх. \ex[21] На╝ъямхре, йюй опхяонянахрэ юкцнпхрл~F дкъ пюанрш я кчашл~$N\ge 1$. \ex[21] Мю пхя.~9 хгнапюфемю дхюцпюллю пюглмнфемхъ йпнкхйнб б хяундмни гюдюве Тханмюввх (яп.~я~о.~1.2.8). Ясыеярбсер кх опнярюъ ябъгэ лефдс щрни дхюцпюллни х тханмюввхебшл депебнл пеьемхи? \ex[Л19] Опх йюйху гмювемхъу~$k$ тханмюввхебн депебн онпъдйю~$k$ нопедекъер норхлюкэмсч опнжедспс онхяйю, р.~е. рюйсч, опх йнрнпни япедмее вхякн япюбмемхи лхмхлюкэмн? \ex[Л21] Хг соп.~1.2.8-34 (хкх соп.~5.4.2-10) лш гмюел, врн кчане мюрспюкэмне вхякн~$n$ едхмярбеммшл напюгнл опедярюбкъеряъ б бхде ясллс вхяек Тханмюввх: $n=F_{a_1}+F_{a_2}+\cdots+F_{a_r}$, цде $r\ge 1$, $a_j\ge a_{j+1}+2$ опх~$1\le j1$.} $$ Щрн опнхяундхр онрнлс, врн оняке оепбнцн япюбмемхъ онхяй опхлепмн я бепнърмнярэч~$p$ ябндхряъ й онхяйс япедх $pN$~щкелемрнб х я бепнърмнярэч $q$---й онхяйс япедх $qN$~щкелемрнб. Опх анкэьху~$N$ лнфмн опемеапевэ щттейрнл мхгьецн онпъдйю, ябъгюммшл я рел, врн вхякю~$pN$ х~$qN$ ме жекше. \medskip \item{a)} Онйюфхре, врн $C(N)=\log_b N$ рнвмн сднбкербнпъер сйюгюммшл яннрмньемхъл опх мейнрнпнл~$b$. Дкъ ахмюпмнцн х тханмюввхебю онхяйнб бекхвхмю~$b$ онксвюеряъ хг бшбедеммшу пюмее тнплск. \item{b)} Мейрн пюяясфдюк рюй: "Я бепнърмнярэч~$p$ дкхмю пюяялюрпхбюелнцн хмрепбюкю декхряъ мю~$1/p$, я бепнърмнярэч~$q$---мю~$1/q$. Якеднбюрекэмн хмрепбюк декхряъ б япедмел мю~$p(1/p)+q (1/q)=2$, рюй врн юкцнпхрл б рнвмнярх рюй фе унпнь, йюй х ахмюпмши онхяй, мегюбхяхлн нр~$p$ х~$q$". Еярэ кх ньхайю б щрху пюяясфдемхъу? \medskip \ex[20] Мюпхясире ахмюпмне депебн, яннрберярбсчыее хмрепонкъжхнммнлс онхяйс опх~$N=10$. \ex[Л43] (Щ.~Й.~Ън х~Т.~Т.~Ън.) Онйюфхре,, врн днкфмшл напюгнл нтнплкеммши хмрепонкъжхнммши онхяй б япедмел рпеасер (юяхлорнрхвеяйх) $\log_2\log_2 N$~япюбмемхи, еякх $N$~нрянпрхпнбюммшу йкчвеи хлечр мегюбхяхлше пюбмнлепмше пюяопедекемхъ. Анкее рнцн, бяе юкцнпхрлш онхяйю он рюйхл рюакхжюл днкфмш янбепьюрэ б япедмел $\log_2 \log_2 N$~япюбмемхи (нжемйю юяхлорнрхвеяйюъ). \rex[25] Юкцнпхрл ахмюпмнцн онхяйю Ц.~Анрремапсйю, сонлъмсрши б йнмже осмйрю, "нрйкюдшбюер" опнбепйх мю пюбемярбн дн яюлнцн йнмжю онхяйю. (Бн %%502 бпелъ пюанрш юкцнпхрлю лш гмюел, врн $K_l\le K2^{36}$ йнлоемяхпсеряъ менаундхлнярэ днонкмхрекэмни хрепюжхх!) Онйюфхре, врн \emph{кчани} юкцнпхрл онхяйю, яннрберярбсчыхи ахмюпмнлс депебс х пюгбербкъчыхияъ он рпел мюопюбкемхъл ($<$, $=$, хкх~$>$), лнфмн оепедекюрэ б юкцнпхрл, пюгбербкъчыхияъ бн бмсрпеммху сгкюу кхьэ он дбсл мюопюбкемхъл ($<$ хкх~$\ge$). Б вюярмнярх, лндхтхжхпсире рюйхл яонянанл юкцнпхрл~C. \rex[23] Онкмне ахмюпмне депебн ъбкъеряъ сднамшл яонянанл опедярюбкемхъ б онякеднбюрекэмшу ъвеийюу депебю я лхмхлюкэмни дкхмни осрх. (Яп. я о.~2.3.4.5.) Опхдслюире щттейрхбмши лернд онхяйю, нямнбюммши мю рюйнл опедярюбкемхх. [\emph{Сйюгюмхе:} лнфмн кх б ахмюпмнл онхяйе хяонкэгнбюрэ слмнфемхе мю~$2$ блеярн декемхъ мю~$2$?] \rex[Л25] Опедонкнфхл, врн с ахмюпмнцн депебю хлееряъ $a_k$~бмсрпеммху х $b_k$~бмеьмху сгкнб мю спнбме~$k$, $k=0$, $1$,~\dots. (Йнпемэ мюундхряъ мю мскебнл спнбме.) Рюй, дкъ пхя.~8 хлеел $(a_0, a_1,~\ldots, a_6)=(1, 2, 4, 4, 1, 0)$ х $(b_0, b_1,~\ldots, b_6)=(0, 0, 0, 4, 7, 2)$. (a)~Онйюфхре, врн ясыеярбсер опнярне юкцеапюхвеяйне яннрмньемхе, ябъгшбючыее опнхгбндъыхе тсмйжхх $A(z)=\sum_{k}a_kz^k$ х~$B(z)=\sum_k b_kz^k$. (b)~Пюяопедекемхе бепнърмняреи опх сдювмнл онхяйе он ахмюпмнлс депебс хлеер опнхгбндъысч тсмйжхч $g(z)=zA(z)/N$, ю опх месдювмнл онхяйе опнхгбндъыюъ тсмйжхъ еярэ $h(z)=B(z)/(N+1)$. (Б нангмювемхъу о.~6.2.1 $C_N=\mean(g)$, $C'_N=\mean(h)$, ю яннрмньемхе~(2) ябъгшбюер щрх бекхвхмш.) Мюидхре гюбхяхлнярэ лефдс $\var(g)$ х~$\var(h)$. \ex[22] Онйюфхре, врн депебн Тханмюввх ябъгюмн я янпрхпнбйни лмнцнтюгмшл якхъмхел мю рпеу кемрюу. \ex[M30] (X.~Я.~Ярнсм х Дф.~Кхмх.) Пюяялнрпхл опнжеяя онхяйю, нямнбюммши рнкэйн мю япюбмемхъу йкчвеи х хяонкэгсчыхи ндмнбпелеммн $k$~опнжеяянпнб. Опх йюфднл ьюце онхяйю нопедекъчряъ $k$~хмдейянб $i_1$, $i_2$,~\dots, $i_k$ х лш янбепьюел $k$~ндмнбпелеммшу япюбмемхи: еякх~$K=K_j$ дкъ мейнрнпнцн~$j$, онхяй йнмвюеряъ сдювмн, б опнрхбмнл яксвюе оепеундхл й якедсчыелс ьюцс онхяйю, нямнбшбюъяэ мю $2^k$~бнглнфмшу хяундюу~$KK_{i_j}$, $1\le j\le k$. Онйюфхре, врн рюйни опнжеяя опх~$N\to\infty$ днкфем янбепьюрэ б япедмел он йпюимеи лепе $\log_{k+1}N$~ьюцнб. (Опедонкюцюеряъ, врн бяе йкчвх б рюакхже, рюйфе йюй х юпцслемр онхяйю, пюбмнбепнърмш.) (Гмювхр, он япюбмемхч я ндмнопнжеяянпмшл ахмюпмшл онхяйнл лш бшхцпшбюел б яйнпнярх ме б $k$~пюг, йюй лнфмн ашкн аш нфхдюрэ, ю кхьэ б $\log_2(k+1)$~пюг. Б щрнл ялшяке бшцндмее йюфдши опнжеяянп хяонкэгнбюрэ дкъ нрдекэмнцн онхяйю, ю ме на╝едхмърэ ху.) \subsubchap{Онхяй он ахмюпмнлс депебс} %% 6.2.2 Б опедшдсыел осмйре лш бхдекх, врн хяонкэгнбюмхе меъбмни ярпсйрспш ахмюпмнцн депебю накецвюер онмхлюмхе ахмюпмнцн х тханмюввхебю онхяйнб. Пюяялнрпемхе яннрберярбсчыху депебэеб онгбнкхкн гюйкчвхрэ, врн опх дюммнл~$N$ япедх бяеу лернднб онхяйю осрел япюбмемхъ йкчвеи ахмюпмши онхяй янбепьюер лхмхлюкэмне вхякн япюбмемхи. Мн лерндш опедшдсыецн осмйрю опедмюгмювемш цкюбмшл напюгнл дкъ рюакхж тхйяхпнбюммнцн пюглепю, рюй йюй онякеднбюрекэмне пюяонкнфемхе гюохяеи декюер бярюбйх х сдюкемхъ днбнкэмн рпсднелйхлх. Еякх рюакхжю %%503 дхмюлхвеяйх хглемъеряъ, рн щйнмнлхъ нр хяонкэгнбюмхъ ахмюпмнцн онхяйю ме онйпнер гюрпюр мю онддепфюмхе сонпъднвеммнцн пюяонкнфемхъ йкчвеи. \emph{Ъбмне} хяонкэгнбюмхе ярпсйрспш ахмюпмнцн депебю онгбнкъер ашярпн бярюбкърэ х сдюкърэ гюохях х опнхгбндхрэ щттейрхбмши онхяй он рюакхже. Б пегскэрюре лш онксвюел лернд, онкегмши йюй дкъ онхяйю, рюй х дкъ янпрхпнбйх. Рюйюъ цхайнярэ днярхцюеряъ \picture{Пхя. 10. Ахмюпмне депебн онхяйю.} осрел днаюбкемхъ б йюфдсч гюохяэ дбсу онкеи дкъ упюмемхъ яяшкнй. Лерндш онхяйю он пюярсыхл рюакхжюл, вюярн мюгшбючр \emph{юкцнпхрлюлх рюакхж яхлбнкнб}, рюй йюй юяяелакепш, йнлохкърнпш х дпсцхе яхярелмше опнцпюллш нашвмн хяонкэгсчр ху дкъ упюмемхъ нопедекъелшу онкэгнбюрекел яхлбнкнб. Мюопхлеп, йкчвнл гюохях б йнлохкърнпе лнфер яксфхрэ яхлбнкхвеяйхи хдемрхтхйюрнп, нангмювючыхи оепелеммсч б мейнрнпни опнцпюлле мю Тнпрпюме хкх Юкцнке, ю нярюкэмше онкъ гюохях лнцср яндепфюрэ хмтнплюжхч н рхое оепелеммни х ее пюяонкнфемхх б оюлърх. Хкх фе йкчвнл лнфер ашрэ яхлбнк опнцпюллш дкъ \MIX, ю нярюбьюъяъ вюярэ гюохях лнфер яндепфюрэ щйбхбюкемр щрнцн яхлбнкю. Опнцпюллш онхяйю я бярюбйни он депебс, йнрнпше асдср нохяюмш б щрнл осмйре, нркхвмн ондундър дкъ хяонкэгнбюмхъ б йювеярбе юкцнпхрлнб рюакхж яхлбнкнб, нянаеммн еякх фекюрекэмн пюяоевюршбюрэ яхлбнкш б юктюбхрмнл онпъдйе. Дпсцхе юкцнпхрлш, рюакхж яхлбнкнб нохяюмш б \S~6.3 х~6.4. %%504 Мю пхя.~10 хгнапюфемн ахмюпмне депебн онхяйю, яндепфюыее мюгбюмхъ ндхммюджюрх гмюйнб гндхюйю% \note{1}{Гмюйх гндхюйю, сонпъднвеммше он леяъжюл: Йнгепнц, Бнднкеи, Пшаш, Нбем, Рекеж, Акхгмежш, Пюй, Кеб, Дебю, Беяш, Яйнпохнм, Ярпекеж,---{\sl Опхл. оепеб.\/}}. Еякх реоепэ, нропюбкъъяэ нр йнпмъ депебю, лш асдел хяйюрэ дбемюджюрне мюгбюмхе, |SAGITTARIUS|, рн сбхдхл, врн нмн анкэье, вел |CAPRICORN|, онщрнлс мсфмн хдрх бопюбн; нмн анкэье, вел |PISCES|,---ямнбю хдел бопюбн; нмн лемэье, вел |TAURUS|,---хдел бкебн; нмн лемэье, вел |SCORPIO|,--- х лш оноюдюел бн бмеьмхи сгек~\leaf{8}. Онхяй ашк месдювмшл; реоепэ он нйнмвюмхх онхяйю лш лнфел \emph{бярюбхрэ} |SAGITTARIUS|, "ондбъгшбюъ" ецн й депебс блеярн бмеьмецн сгкю~\leaf{8}. Рюйхл напюгнл, рюакхжю лнфер пюярх аег оепелеыемхъ ясыеярбсчыху гюохяеи. Пхясмнй~10 онксвем онякеднбюрекэмни бярюбйни, мювхмюъ я осярнцн депебю, йкчвеи |CAPRICORN|, |AQUARIUS|, |PISCES|, |ARIES|, |TAURUS|, |GEMINI|, |CANCER|, |LEO|, |VIRGO|, |LIBRA|, |SCORPIO| б сйюгюммнл онпъдйе. Мю пхя.~10 бяе йкчвх кебнцн онддепебю йнпмъ опедьеярбсчр он юктюбхрс якнбс |CAPRICORN|, ю б опюбнл онддепебе ярнър оняке мецн. Юмюкнцхвмне србепфдемхе яопюбедкхбн дкъ кебнцн х опюбнцн онддепебэеб кчанцн сгкю. Нрячдю якедсер, врн опх наунде депебю б \emph{яхллерпхвмнл онпъдйе} йкчвх пюяонкюцючряъ ярпнцн б юктюбхрмнл онпъдйе: $$ \displaylines{ |AQUARIUS|, |ARIES|, |CANCER|, |CAPRICORN|, |GEMINI|, \cr |LEO|, \ldots, |VIRGO|,\cr } $$ рюй йюй яхллерпхвмши онпъднй нямнбюм мю опнунфдемхх ямювюкю кебнцн онддепебю йюфднцн сгкю, гюрел яюлнцн сгкю, ю гюрел ецн опюбнцн онддепебю (яп. я о.~2.3.1). Мхфе дюеряъ ондпнамне нохяюмхе опнжеяяю онхяйю я бярюбйни. \alg Р.(Онхяй я бярюбйни он депебс.) Дюмю рюакхжю гюохяеи, напюгсчыху ахмюпмне депебн. Опнхгбндхряъ онхяй гюдюммнцн юпцслемрю~$K$. Еякх ецн мер б рюакхже, рн б ондундъыел леяре б депебн бярюбкъеряъ мнбши сгек, яндепфюыхи~$K$. Опедонкюцюеряъ, врн сгкш депебю яндепфюр он йпюимеи лепе якедсчыхе онкъ: $$ \eqalign{ |KEY|(|P|)&=\hbox{йкчв, упюмъыхияъ б сгке $|NODE|(|P|)$};\cr |LLINK|(|P|)&=\hbox{сйюгюрекэ мю кебне онддепебн сгкю~$|NODE|(|P|)$};\cr |RLINK|(|P|)&=\hbox{сйюгюрекэ мю опюбне онддепебн сгкю~$|NODE|(|P|)$}.\cr } $$ Осярше онддепебэъ (бмеьмхе сгкш мю пхя.~10) опедярюбкъчряъ осяршлх сйюгюрекълх~$\NULL$. Оепелеммюъ~|ROOT| сйюгшбюер мю йнпемэ депебю. Дкъ сднаярбю опедонкюцюеряъ, врн депебн ме осярн %%505 ($|ROOT|\ne\NULL$), рюй йюй опх~$|ROOT|=\NULL$ ноепюжхх ярюмнбъряъ рпхбхюкэмшлх. \st[Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ $|P|\asg |ROOT|$. (Сйюгюрекэ~|P| асдер опндбхцюрэяъ бмхг он депебс.) \st[Япюбмемхе.] Еякх~$K<|KEY|(|P|)$, рн оепеирх мю~\stp{3}; еякх $K>|KEY|(|P|)$, рн оепеирх мю~\stp{4}; еякх $K=|KEY|(|P|)$, онхяй гюбепьем сдювмн. \st[Ьюц бкебн.] Еякх~$|LLINK|(|P|)\ne\NULL$, сярюмнбхрэ $|P|\asg|LLINK|(|P|)$ х бепмсрэяъ мю~\stp{2}. Б опнрхбмнл яксвюе оепеирх мю~\stp{5}. \st[Ьюц бопюбн.] Еякх~$|RLINK|(|P|)\ne\NULL$, сярюмнбхрэ $|P|\asg|RLINK|(|P|)$ х бепмсрэяъ мю~\stp{2}. \st[Бярюбйю б депебн.] (Онхяй месдювем; реоепэ лш онлеярхл $K$ б депебн.) Бшонкмхрэ $|Q|\Asg|AVAIL|$; |Q| реоепэ сйюгшбюер мю мнбши сгек. Сярюмнбхрэ $|KEY|(|Q|)\asg K$, $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. (Мю яюлнл деке мсфмн опнхгбеярх мювюкэмсч сярюмнбйс х дпсцху онкеи мнбнцн сгкю.) Еякх $K$ ашкн лемэье $|KEY|(|P|)$, сярюмнбхрэ $|LLINK|(|P|)\asg|Q|$; б опнрхбмнл яксвюе сярюмнбхрэ $|RLINK|(|P|)\asg|Q|$. (Б щрнр лнлемр лш лнцкх аш опхябнхрэ $|P|\asg|Q|$ х сдювмн гюбепьхрэ пюанрс юкцнпхрлю.) \algend Юкцнпхрл яюл ондяйюгшбюер пеюкхгюжхч мю ъгшйе~\MIXAL. Опедонкнфхл, мюопхлеп, врн сгкш депебю хлечр якедсчысч ярпсйрспс: \picture{Пхя. ярп. 505} Бнглнфмн, дюкее пюяонкнфемш днонкмхрекэмше якнбю |INFO|. Йюй х б цк.~2, |AVAIL| еярэ яохянй ябнандмни оюлърх. Хрюй, онксвюеряъ якедсчыюъ опнцпюллю дкъ \MIX. \prog Р.(Онхяй я бярюбйни он депебс.) $|rA|\equiv K$, $|rI1|\equiv|P|$, $|rI2|\equiv Q$. \code LLINK & EQU &2:3 RLINK & EQU &4:5 START & LDA &Й & 1 & Р1. Мювюкэмюъ сярюмнбйю. & LD1 &ROOT & 1 & $|P|\asg|ROOT|$. & JMP &2F & 1 4H & LD2 &0,1(RLINK) & C2 & T4. Ьюц бопюбн. $|Q|\asg|RLlNK|(|P|)$. & J2Z &5F & C2 & Мю T5, еякх $|Q|=\NULL$. 1H & ENT1 &0,2 & C-l & $|P|\asg|Q|$. 2H & CMPA &1,1 & C & T2. Япюбмемхе. & JG & 4Б & C & Мю T4, еякх $K>|KEY|(|P|)$. & JE &SUCCESS & C1 & Бшунд, еякх $K=|KEY|(|P|)$. & LD2 &0,1 (LLINK) & C1-S & TГ. Ьюц бкебн. $|Q|\asg|LLINK|(|P|)$. %%506 & J2NZ & 1B & C1-S & Мю T2, еякх $|Q|\ne\NULL$. 5М & LD2 & AVAIL & 1-S & T5 Бярюбйх б депебн. & J2Z & OVERFLOW & 1-S & LDX & 0,2(RLINK) & 1-S & STX & AVAIL & 1-S & $|Q|\Asg|AVAIL|$. & STA & 1,2 & 1-S & $|KEY|(|Q|)\asg|K|$. & STZ & 0,2 & 1-S & $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. & JL & 1F & 1-S & $K$ ашк лемэье $|KEY|(|P|)$? & ST2 & 0,1(RLINK) & A & $|RLINK|(|P|)\asg|Q|$. & JMP & *+2 & A 1H & ST2 & 0,1(LLINK) & 1-S-A & $|LLINK|(|P|)\asg|Q|$. DONE & EQU & * & 1-S & Бшунд оняке бярюбйх. \endcode \progend Оепбше 13~ярпнй опнцпюллш нясыеярбкъчр онхяй, онякедмхе 11~ярпнй---бярюбйс. Бпелъ пюанрш онхяйнбни тюгш пюбмн $(7C+C1-3S+4)u$, цде $$ \eqalign{ C &=\hbox{вхякн опнхгбедеммшу япюбмемхи};\cr Cl& =\hbox{вхякн яксвюеб, йнцдю $K\le|KEY|(|P|)$};\cr S& =\hbox{ 1 опх сдювмнл онхяйе х 0 б опнрхбмнл яксвюе}.\cr } $$ Б япедмел хлеел $C1={1\over2}(C+S)$; деиярбхрекэмн, $C1+C2=C$ х $C1-S\approx C2$. Онщрнлс бпелъ онхяйю опхлепмн пюбмн $(7.5C-2.5S+4)u$. \picture{Пхя 11. Онхяй я бярюбйни он депебс.} Опнцпюллш ахмюпмнцн онхяйю, хяонкэгсчыхе меъбмше депебэъ, пюанрючр днкэье! (Яп. я опнцпюллни~6.2.1Я.) Опндсакхпнбюб йнлюмдш, йюй. х б опнцпюлле~6.2.1F, лнфмн хгаюбхрэяъ нр ярпнйх~08 б опнцпюлле~Р, слемэьхб рел яюлшл бпелъ онхяйю дн~$(6.5C-2.5S+5)u$. Еякх онхяй месдювем, тюгю бярюбйх гюилер еые бпелъ $14u$ хкх~$15u$. Юкцнпхрл~Р кецйн опхяонянахрэ й пюанре я йкчвюлх х гюохяълх \emph{оепелеммни дкхмш}. Мюопхлеп, еякх лш пюяопедекъел %%507 хлечыееяъ б мюкхвхх опнярпюмярбн онякеднбюрекэмн, яонянанл "онякедмхл бйкчвюеряъ---оепбшл хяйкчвюеряъ" (LIFO), рн кецйн ялнфел янгдюбюрэ сгкш пюгкхвмнцн пюглепю; оепбне якнбн депебю~(1) лнфер сйюгшбюрэ дкхмс. Рюйне щттейрхбмне хяонкэгнбюмхе оюлърх декюер юкцнпхрлш рюакхж яхлбнкнб, нямнбюммше мю дпебнбхдмни ярпсйрспе, нянаеммн опхбкейюрекэмшлх дкъ пюгпюанрвхйнб йнлохкърнпнб, юяяелакепнб х гюцпсгвхйнб. \qsection Ю йюй мюявер мюхусдьецн яксвюъ? Лмнцхе опнцпюллхярш ямювюкю яйеорхвеяйх бняопхмхлючр юкцнпхрл~T. Еякх аш йкчвх пхя.~10 онярсоюкх б юктюбхрмнл онпъдйе |AQUARIUS|,~\dots, |VIRGO|, a ме б йюкемдюпмнл |CAPRICORN|,~\dots, |SCORPIO|, рн юкцнпхрл бшярпнхк аш бшпнфдеммне депебн, йнрнпне, б ясымнярх, нопедекъер \emph{онякеднбюрекэмши} онхяй. (Бяе онкъ |LLINK| пюбмъкхяэ аш ~$\NULL$.) Юмюкнцхвмн, еякх йкчвх онярсоючр б менашвмнл онпъдйе: $$ \displaylines{ |AQUARIUS|, |VIRGO|, |ARIES|, |TAURUS|, |CANCER|, |SCORPIO|,\cr |CAPRICORN|, |PISCES|, |GEMINI|, |LIBRA|, |LEO|,\cr } $$ лш онксвхл гхцгюцннапюгмне депебн, врн мхвсрэ ме ксвье. (Онярпнире щрн депебн!) Я дпсцни ярнпнмш, дкъ сдювмнцн онхяйю он депебс пхя.~10 рпеасеряъ б япедмел бяецн кхьэ $3{2\over11}$~япюбмемхи, врн мелмнцхл анкэье норхлюкэмнцн япедмецн вхякю япюбмемхи~3, йнрнпне днярхцюеряъ опх онхяйе он мюхксвьелс хг бнглнфмшу ахмюпмшу депебэеб. Дкъ днярюрнвмн унпньн яаюкюмяхпнбюммнцн депебю бпелъ онхяйю опхлепмн, опнонпжхнмюкэмн~$\log_2N$, ю дкъ бшпнфдеммнцн депебю---$N$. Б соп.~2.3.4.5-5 днйюгшбюеряъ, врн, еякх явхрюрэ бяе ахмюпмше депебэъ хг $N$~сгкнб пюбмнбепнърмшлх, япедмее бпелъ онхяйю опхакхгхрекэмн опнонпжхнмюкэмн~$\sqrt{N}$. Вецн фе мюл нфхдюрэ нр юкцнпхрлю~T? Й явюярэч, лнфмн днйюгюрэ, врн онхяй он депебс рпеасер кхьэ нйнкн $2\ln N \approx 1.386\log_2 N$ япюбмемхи, еякх йкчвх днаюбкъчряъ й депебс б яксвюимнл онпъдйе; унпньн яаюкюмяхпнбюммше депебэъ---опюбхкн, ю бшпнфдеммше---хяйкчвемхе. Днйюгюрэ щрнр тюйр сдхбхрекэмн опнярн. Опедонкнфхл, врн йюфдюъ хг $N!$~оепеярюмнбнй $N$~йкчвеи я пюбмни бепнърмнярэч хяонкэгсеряъ дкъ онярпнемхъ депебю осрел бярюбнй. Вхякн япюбмемхи, мсфмшу дкъ мюунфдемхъ йкчвю, пнбмн мю едхмхжс анкэье вхякю япюбмемхи, онрпеанбюбьхуяъ опх бярюбйе ецн б депебн. Якеднбюрекэмн, еякх вепег $C_N$ нангмювхрэ япедмее вхякн япюбмемхи опх сдювмнл онхяйе, ю вепег $C'_N$---опх месдювмнл, лш онксвхл $$ C_N=1+{C'_0+C'_1+\cdots+C'_{N-1}\over N}. \eqno(2) $$ %%508 Мн янцкюямн яннрмньемхч лефдс дкхмюлх бмсрпеммецн х бмеьмецн осреи (6.2.1-2) $$ C_N=\left(1+{1\over N}\right)C'_N-1. \eqno(3) $$ Ондярюбкъъ $C_N$ хг~(3) б~(2), хлеел $$ (N+1)C'_N=2N+C'_0+C'_1+\cdots+C'_{N-1}. \eqno(4) $$ Хг щрнцн пейсппемрмнцн яннрмньемхъ $C'_N$ мюундхряъ кецйн. Бшвхрюмхе пюбемярбю $$ NC'_{N-1}=2(N-1)+C'_0+C'_1+\cdots+C'_{N-2} $$ дюер $$ \eqalign{ (N+1)C'_N-NC'_{N-1}&=2+C'_{N-1},\cr C'_N&=C'_{N-1}+2/(N+1).\cr } $$ Рюй йюй $C'_0=0$, рн $$ C'_N=2H_{N+1}-2. \eqno(5) $$ Опхлемхб~(3), оняке сопныемхи онксвюел $$ C_N=2\left(1+{1\over N}\right) H_N-3. \eqno(3) $$ Сопюфмемхъ 6--8 дючр анкее дерюкэмсч хмтнплюжхч: лнфмн мюирх ме рнкэйн япедмхе гмювемхъ~$C_N$ х~$C'_N$, мн х ху бепнърмнярмше пюяопедекемхъ. \section Янпрхпнбйю бярюбйни б депебн. Юкцнпхрл~T опедмюгмювюкяъ дкъ онхяйю, мн ецн лнфмн опхмърэ гю нямнбс юкцнпхрлю бмсрпеммеи \emph{янпрхпнбйх}, рюй йюй нм ъбкъеряъ еяреярбеммшл нанаыемхел юкцнпхрлю бярюбнй б яохянй~5.2.1L. Слекн гюопнцпюллхпнбюммши, нм асдер пюанрюрэ кхьэ мелмнцн ледкеммее ксвьху юкцнпхрлнб, наясфдюбьхуяъ б цк.~5. Йнцдю онярпнемхе депебю гюбепьемн, нярюеряъ яхллерпхвмн нанирх ецн (юкцнпхрл~2.3.1T)---лш "оняерхл" гюохях б нрянпрхпнбюммнл онпъдйе. Ндмюйн менаундхлн ашрэ нярнпнфмшл. Ъямн, врн б ьюце~T2 опх $K=|KEY|(|P|)$ мюдн деиярбнбюрэ он-дпсцнлс, рюй йюй лш янпрхпсел, ю ме хыел. Лнфмн, мюопхлеп, пеюцхпнбюрэ мю $K=|KEY|(|P|)$ рюй фе, йюй х мю $K>|KEY|(|P|)$; щрн дюяр опюбхкэмши лернд янпрхпнбйх. (Гюлерхл, бопнвел, врн пюбмше йкчвх ме наъгюрекэмн днкфмш мюундхрэяъ б ялефмшу сгкюу, кхьэ аш нмх опнундхкхяэ онякеднбюрекэмн опх яхллерпхвмнл наунде.) Опх анкэьнл йнкхвеярбе онбрнпъчыхуяъ йкчвеи щрнр лернд опхбедер й беяэлю меяаюкюмяхпнбюммнлс депебс, х янпрхпнбйю гюледкхряъ. Дпсцхл лернднл ъбкъеряъ упюмемхе б йюфднл сгке яохяйю гюохяеи я ндмхл х рел фе йкчвнл; онрпеасеряъ днонкмхрекэмне онке дкъ яяшкйх, мн щрн сяйнпхр янпрхпнбйс б яксвюе, йнцдю бярпевюеряъ лмнцн ндхмюйнбшу йкчвеи. %%509 Рюйхл напюгнл, юкцнпхрл~T, опхлемъелши рнкэйн дкъ янпрхпнбйх, меокну, мн еярэ х ксвьхе. Еякх фе мсфмн янверюрэ онхяй х янпрхпнбйс, хяонкэгнбюмхе дпебнбхдмни ярпсйрспш якедсер мюярнърекэмн пейнлемднбюрэ. Хмрепеямн нрлерхрэ реямсч ябъгэ лефдс юмюкхгнл янпрхпнбйх бярюбйни б депебн х юмюкхгнл налеммни янпрхпнбйх я пюгдекемхел ("ашярпни янпрхпнбйх"), унръ мю оепбши бгцкъд щрх лерндш янбепьеммн пюгкхвмш. Опх бярюбйе б оепбнмювюкэмн осярне депебн $N$~йкчвеи б япедмел янбепьюеряъ рн фе вхякн япюбмемхи, врн х б юкцнпхрле~5.2.2Q (гю меанкэьхлх хяйкчвемхълх). Мюопхлеп, опх бярюбйе б депебн йюфдши йкчв япюбмхбюеряъ я $K_1$, ю йюфдши йкчв, лемэьхи $K_1$, япюбмхбюеряъ я оепбшл йкчвнл, лемэьхл $K_1$, х р. д.; опх ашярпни янпрхпнбйе йюфдши йкчв япюбмхбюеряъ я оепбшл пюгдекъчыхл щкелемрнл~$K$, ю гюрел йюфдши йкчв, лемэьхи $K$, япюбмхбюеряъ я нопедекеммшл, лемэьхл $K$ щкелемрнл х р.~д. Япедмее вхякн япюбмемхи б нанху яксвюъу пюбмн $NC_N$. (Опюбдю, мю яюлнл деке, врнаш сяйнпхрэ бмсрпеммхи жхйк, юкцнпхрл~5.2.2Q янбепьюер меяйнкэйн анкэье япюбмемхи.) \section Сдюкемхъ. Хмнцдю ашбюер мсфмн гюярюбхрэ ЩБЛ гюашрэ ндхм хг щкелемрнб рюакхжш. Кецйн сдюкхрэ "кхяр" (сгек, наю онддепебю йнрнпнцн осярш) хкх сгек, б йнрнпнл $|LLINK|=\NULL$ хкх~$|RLINK|=\NULL$. Мн еякх нае яяшкйх ме осярш, мюдн деиярбнбюрэ нянашл напюгнл---бедэ мекэгъ б ндмнл леяре упюмхрэ дбю сйюгюрекъ. Б йювеярбе опхлепю ямнбю пюяялнрпхл пхя.~10. Йюй сдюкхрэ |CAPRICORN|? Бнр ндмн хг пеьемхи: сдюкхрэ \emph{якедсчыхи} акхфюиьхи сгек, кебюъ яяшкйю йнрнпнцн осярю, х гюрел бепмсрэ ецн мю леярн сгкю, йнрнпши деиярбхрекэмн рпеасеряъ сдюкхрэ. Мюопхлеп, мю пхя.~10 ямювюкю сдюкъеряъ |GEMINI|, гюрел |CAPRICORN| гюлемъеряъ мю |GEMINI|. Рюйюъ ноепюжхъ янупюмъер онпъднй щкелемрнб рюакхжш. Юкцнпхрл~D пеюкхгсер щрс хдеч. \alg D.(Сдюкемхе хг депебю.) Вепег |Q| нангмювхл оепелеммсч, сйюгшбючысч мю сгек ахмюпмнцн депебю онхяйю, йнрнпне опедярюбкемн йюй б юкцнпхрле~T. Дюммши юкцнпхрл сдюкъер щрнр сгек, нярюбкъъ ахмюпмне депебн онхяйю. (Мю яюлнл деке лш хлеел хкх $|Q|\equiv|ROOT|$, хкх $|Q|\equiv|LLINK|(|P|)$, хкх $|Q|\equiv|RLINK|(|P|)$ дкъ мейнрнпнцн сгкю~|P|. Юкцнпхрл хглемъер б оюлърх гмювемхе~|Q| б яннрберярбхх я нясыеярбк╦ммшл сдюкемхел.) \st[Яяшкйю |RLINK| осярю?] Сярюмнбхрэ $|T|\asg |Q|$. Еякх $|RLINK|(|T|)=\NULL$, сярюмнбхрэ $|Q|\asg|LLINK|(|T|)$ х оепеирх мю~\stp{4}. \st [Мюирх опеелмхйю.] Сярюмнбхрэ $|R|\asg|RLINK|(|T|)$. Еякх $|LLINK|(|R|)=\NULL$, сярюмнбхрэ $|LLINK|(|R|)\asg|LLINK|(|T|)$, $|Q|\asg|R|$ х оепеирх мю~\stp{4}. %%510 \st[Мюирх осярсч яяшкйс |LLINK|.] Сярюмнбхрэ $|S|\asg|LLINK|(|R|)$. Еякх $|LLINK|(|S|)\ne\NULL$, сярюмнбхрэ $|R|\asg|S|$ х онбрнпърэ ьюц дн реу онп, онйю ме онксвхл $|LLINK|(|S|)=\NULL$. (Реоепэ |S| сйюгшбюер мю якедсчыхи оняке |Q| щкелемр опх яхллерпхвмнл наунде.) Мюйнмеж, сярюмнбхрэ $|LLINK|(|S|)\asg|LLINK|(|T|)$, $|LLINK|(|R|)\asg|RLINK|(|S|)$, $|RLINK|(|S|)\asg|RLINK|(|T|)$, $|Q|\asg|S|$. \st[Нябнандхрэ сгек.] Бшонкмхрэ $|AVAIL|\Asg|T|$ (р.~е. бепмсрэ сгек б оск ябнандмни оюлърх). \algend Вхрюрекэ лнфер хяошрюрэ щрнр юкцнпхрл, сдюкъъ сгкш |AQUARIUS|, |CANCER| х~|CAPRICORN| депебю пхя.~10; йюфдши яксвюи хлеер ябнх нянаеммнярх. Бмхлюрекэмши вхрюрекэ, бепнърмн, гюлерхк, врн нрдекэмн ме бшдекем яксвюи $|RLINK|(|T|)\ne\NULL$, $|LLINK|(|T|)=\NULL$; лш наясдхл щрн меяйнкэйн онгфе, рюй йюй юкцнпхрл б рнл бхде, б йнрнпнл нм опедярюбкем гдеяэ, накюдюер беяэлю хмрепеямшлх ябниярбюлх. Оняйнкэйс б юкцнпхрле~D мер мхйюйни яхллерпхх лефдс опюбшл х кебшл, рн йюферяъ, врн дкхммюъ онякеднбюрекэмнярэ яксвюимшу сдюкемхи х бярюбнй пюгаюкюмяхпсер депебн, х бшбедеммше нжемйх щттейрхбмнярх онрепъчр яхкс. Мн б деиярбхрекэмнярх бшпнфдемхъ бнбяе ме опнхгнидер! \proclaim {Ренпелю М (Р.~М.~Ухааюпд, 1962)}. Оняке сдюкемхъ оняпедярбнл юкцнпхрлю~D яксвюимнцн сгкю яксвюимнцн депебю бмнбэ онксвюеряъ яксвюимне депебн. [Ме кчаъыхе люрелюрхйс, опносярхре, онфюксиярю, бокнрэ дн (10)!] Рюйюъ тнплскхпнбйю ренпелш, пюгслееряъ, беяэлю рслюммю. Нохьел яхрсюжхч анкее рнвмн. Осярэ $\cJ$---депебн хг $n$~щкелемрнб, ю $P(\cJ)$---бепнърмнярэ онъбкемхъ~$\cJ$, еякх ецн йкчвх бярюбкъчряъ яксвюимшл напюгнл я онлныэч юкцнпхрлю~T. Мейнрнпше депебэъ онъбкъчряъ я анкэьеи бепнърмнярэч, вел дпсцхе. Вепег $Q(\cJ)$ нангмювхл бепнърмнярэ онксвемхъ~$\cJ$ оняке бярюбйх б яксвюимнл онпъдйе $n+1$~йкчвеи (оняпедярбнл юкцнпхрлю~T) х онякедсчыецн сдюкемхъ я онлныэч юкцнпхрлю~D ндмнцн хг щрху щкелемрнб, бшапюммнцн яксвюимн. Опх бшвхякемхх~$P(\cJ)$ опедонкюцюеряъ, врн бяе $n~$~оепеярюмнбнй йкчвеи пюбмнбепнърмш; опх мюунфдемхх $Q(\cJ)$ лш явхрюел, врн $(n+1)(n+1)!$~оепеярюмнбнй йкчвеи х бшанпнб йкчвю дкъ сдюкемхъ пюбмнбепнърмш. Ренпелю србепфдюер, врн $P(\cJ)=Q(\cJ)$ дкъ бяеу~$\cJ$. \proof Он сякнбхч пюбмнбепнърмш ме депебэъ, ю оепеярюмнбйх, онщрнлс асдел днйюгшбюрэ ренпелс, пюяялюрпхбюъ б йювеярбе яксвюимшу на╝ейрнб \emph{оепеярюмнбйх}. Нопедекхл ямювюкю сдюкемхе хг оепеярюмнбйх х гюрел днйюфел, врн "оняке сдюкемхъ хг яксвюимни оепеярюмнбйх яксвюимнцн щкелемрю нярюеряъ яксвюимюъ оепеярюмнбйю". %%511 Осярэ $a_1$ $a_2$~\dots $a_{n+1}$---оепеярюмнбйю лмнфеярбю $\{\,1, 2,~\ldots, n+1\,\}$; лш унрхл нопедекхрэ ноепюжхч сдюкемхъ щкелемрю~$a_i$, онксвхб б пегскэрюре оепеярюмнбйс $b_1$ $b_2$~\dots $b_n$ лмнфеярбю $\{\,1, 2,~\ldots, n\,\}$. Щрю ноепюжхъ днкфмю ашрэ янцкюянбюмю я юкцнпхрлюлх~Р х~D, р.~е. еякх нропюбхрэяъ нр депебю, онярпнеммнцн онякеднбюрекэмшлх бярюбйюлх $a_1$, $a_2$,~\dots, $a_{n+1}$, х сдюкхрэ~$a_i$ я оепемслепюжхеи йкчвеи вхякюлх нр~1 дн~$n$, рн онксвхряъ депебн, йнрнпне лнцкн ашрэ онярпнемн онякеднбюрекэмшлх бярюбйюлх $b_1$ $b_2$~\dots $b_n$. Й явюярэч, нопедекхрэ рюйсч ноепюжхч мерпсдмн. Бнглнфмш дбю яксвюъ: \medskip{ \narrower \noindent{\sl Яксвюи 1:\/} $a_i=n+1$ хкх~$a_i+1=a_j$ дкъ мейнрнпнцн $ji$. Гюлемъел $a_i$ мю~$a_j$, сдюкъел $a_j$ я оепбнмювюкэмни онгхжхх х бшвхрюел, едхмхжс хг бяеу щкелемрнб, анкэьху~$a_i$. }\medskip Мюопхлеп, пюяялнрпхл оепеярюмнбйс 4~6~1~3~5~2. Еякх онлерхрэ щкелемр, йнрнпши мсфмн сдюкхрэ, гюйкчвхб ецн б йпсфнй, рн онксвхряъ {\def\r#1{\roundit{$#1$}} $$ \matrix{ \r4 & 6 & 1 & 3 & 5 & 2 & = & 4 & 5 & 1 & 3 & 2 \cr 4&\r6&1 & 3 & 5 & 2 & = & 4 & 1 & 3 & 5 & 2 \cr 4& 6 &\r1&3 & 5 & 2 & = & 3 & 5 & 1 & 2 & 4 \cr } \qquad \matrix{ 4 & 6 & 1 &\r3& 5 & 2 & = & 3 & 5 & 1 & 4 & 2 \cr 4 & 6 & 1 & 3 &\r5& 2 & = & 4 & 5 & 1 & 3 & 2 \cr 4 & 6 & 1 &3 & 5 &\r2 & = & 3 & 5 & 1 & 2 & 4 \cr } $$ } Оняйнкэйс бяецн лнфмн ядекюрэ $(n+1)(n+1)!$ пюгкхвмшу сдюкемхи, ренпелю асдер сярюмнбкемю, еякх лш онйюфел, врн йюфдсч оепеярюмнбйс лмнфеярбю $\{\, 1, 2,~\dots, n\,\}$ лнфмн онксвхрэ йюй пегскэрюр опхлемемхъ пнбмн $(n+1)^2$~сдюкемхи. Пюяялнрпхл оепеярюмнбйс $b_1$ $b_2$~\dots $b_n$ лмнфеярбю $\{\, 1, 2,~\dots, n\,\}$. Нопедекхл $(n+1)^2$~сдюкемхи, мн ндмнлс дкъ йюфдни оюпш $i, j$ ($1\le i,j\le n+1$). Еякх $ij$, хяйнлшл сдюкемхел асдер $$ b'_1\ldots b'_{i-1} \roundit{b_j} b'_i \ldots b'_n, \eqno(8) $$ врн яннрберярбсер {\sl яксвюч~1.\/} %% 512 Мюйнмеж, опх $i=j$ хлеел дпсцхе сдюкемхъ: \picture{Пхя. ярп. 512} йнрнпше рнфе нохяшбючряъ {\sl яксвюел~1.\/} Онкнфхб $n=4$, пюяялнрпхл б йювеярбе опхлепю 25~сдюкемхи, опхбндъыху й оепеярюмнбйе 3~1~4~2: {\def\r#1{\node{#1}} \ctable{\hfill$#$\hfill\bskip\bskip&&\hfill$#$\hfill\bskip\bskip\cr & i=1 & i=2 & i=3 & i=4 & i=5\cr j=1&\r5~3~1~4~2 &4~\r3~1~5~2 &4~1~\r3~5~2 &4~1~5~\r3~2 &4~1~5~2~\r3\cr j=2&\r3~4~1~5~2 &3~\r5~1~4~2 &4~2~\r1~5~3 &4~2~5~\r1~3 &4~2~5~3~\r1\cr j=3&\r3~1~4~5~2 &4~\r1~2~5~3 &3~1~\r5~4~2 &3~1~5~\r4~2 &3~1~5~2~\r4\cr j=4&\r3~1~5~4~2 &4~\r1~5~2~3 &3~1~\r4~5~2 &3~1~4~\r5~2 &4~1~5~3~\r2\cr j=5&\r3~1~5~2~4 &4~\r1~5~3~2 &3~1~\r4~2~5 &4~1~5~\r2~3 &3~1~4~2~\r5\cr }} Онлевеммши щкелемр бяецдю ярнхр б $i\hbox{-и}$ онгхжхх, х дкъ тхйяхпнбюммнцн~$i$ лш онярпнхкх $(n+1)$ пюгкхвмшу сдюкемхи, он ндмнлс дкъ йюфднцн~$j$; якеднбюрекэмн, дкъ йюфдни оепеярюмнбйх $b_1$ $b_2$~\dots $b_n$ онярпнемн $(n+1)^2$ пюгкхвмшу сдюкемхи. Дкъ гюбепьемхъ днйюгюрекэярбю гюлерхл, врн бяецн хлееряъ $(n+1)^2!$~сдюкемхи. \proofend Днйюгюрекэярбн ренпелш~H ме рнкэйн нохяшбюер яхрсюжхч оняке сдюкемхи, мн х онлнцюер опх юмюкхге япедмецн бпелемх сдюкемхъ. Сопюфмемхе~12 онйюгшбюер, врн опх сдюкемхх яксвюимнцн щкелемрю хг яксвюимни рюакхжш ьюц~D2 бшонкмъеряъ б япедмел всрэ пефе, вел б онкнбхме яксвюеб. Пюяялнрпхл реоепэ, яйнкэйн пюг опнундхряъ жхйк б ьюце~D3. Опедонкнфхл, врн сдюкъеряъ сгек, пюяонкнфеммши мю спнбме~$l$, ю \emph{бмеьмхи} сгек, меоняпедярбеммн якедсчыхи гю мхл опх яхллерпхвмнл наунде, мюундхряъ мю спнбме~$k$. Мюопхлеп, опх сдюкемхх сгкю |CAPRICORN| (пхя.~10) хлеел $l=0$ х~$k=3$, рюй йюй сгек~\leaf{4} пюяонкнфем мю спнбме~3. Еякх $k=l+1$, рн $|RLINK|(|T|)=\NULL$ б ьюце~D1; еякх $k>l+1$, лш асдел опхябюхбюрэ $|S|\asg |LLINK|(|R|)$ (ьюц~D3) пнбмн $k-l-2$~пюг. Япедмее гмювемхе~$l$ пюбмн $$ (\hbox{дкхмю бмсрпеммецн осрх})/N; $$ япедмее гмювемхе~$k$ пюбмн $$ (\hbox{дкхмю бмеьмецн осрх})/N -(\hbox{пюяярнъмхе дн яюлнцн кебнцн бмеьмецн сгкю})/N. $$ Пюяярнъмхе дн яюлнцн кебнцн бмеьмецн сгкю пюбмн йнкхвеярбс рюйху~$a_i$ хг бярюбкъелни онякеднбюрекэмнярх, врн $a_i0$ бгбеьеммюъ дкхмю бмеьмецн осрх ме лемэье $$ Q+\sum_{0\le i l_1>\ldots>l_m$ х деиярбхрекэмше онярнъммше$0=x_0