\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