\input style \chapno=6\subchno=1\chapnotrue %% 483 \subchap{poisk posredstvom sravneniya klyuchej} %% 6.2 v |TOM PARAGRAFE MY RASSMOTRIM METODY POISKA, OSNOVANNYE NA LINEJNOM UPORYADOCHENII KLYUCHEJ (NAPRIMER, PORYADOK MOZHET BYTX CHISLOVYM ILI ALFAVITNYM). pOSLE SRAVNENIYA DANNOGO ARGUMENTA~$K$ S KLYUCHOM~$K_i$ IZ TABLICY POISK PRODOLZHAETSYA ODNIM IZ TREH SPOSOBOV V ZAVISIMOSTI OT TOGO, KAKOE IZ SOOTNOSHENIJ VERNO: $KK_i$. pRI POSLEDOVATELXNOM POISKE MY, V SUSHCHNOSTI, DOLZHNY VYBIRATX ODNO IZ DVUH PRODOLZHENIJ ($K=K_i$ ILI~$K\ne K_i$), NO ESLI MY OSVOBODIMSYA OT OGRANICHENIYA IMETX LISHX POSLEDOVATELXNYJ DOSTUP K TABLICE, TO POLUCHIM VOZMOZHNOSTX |FFEKTIVNO ISPOLXZOVATX OTNOSHENIE PORYADKA. \subsubchap{ pOISK V UPORYADOCHENNOJ TABLICE} % 6.2.1 chTO VY STANETE DELATX, ESLI VAM VRUCHAT BOLXSHUYU TELEFONNUYU KNIGU I POPROSYAT NAJTI IMYA CHELOVEKA, NOMER TELEFONA KOTOROGO 795-68-41? zA NEIMENIEM LUCHSHEGO PRIDETSYA VOSPOLXZOVATXSYA METODAMI POSLEDOVATELXNOGO POISKA, IZLOZHENNYMI V \S~6.1. (pRAVDA, LOVKIJ CHASTNYJ DETEKTIV MOG BY POPYTATXSYA NABRATX NOMER I SPROSITX, KTO GOVORIT; NE ISKLYUCHENO TAKZHE, CHTO U NEGO ESTX DRUZXYA NA TELEFONNOJ STANCII, IMEYUSHCHIE DOSTUP K SPRAVOCHNIKAM, GDE TELEFONY RASPOLOZHENY V PORYADKE VOZRASTANIYA NOMEROV.) dELO V TOM, CHTO GORAZDO LEGCHE NAJTI ZAPISX PO FAMILII ABONENTA, A NE PO NOMERU, HOTYA TELEFONNAYA KNIGA SODERZHIT VSYU INFORMACIYU, NUZHNUYU V OBOIH SLUCHAYAH. eSLI NEOBHODIMO NAJTI ZAPISX V BOLXSHOM FAJLE, O POSLEDOVATELXNOM POISKE POCHTI NE MOZHET BYTX RECHI, NO ISPOLXZOVANIE OTNOSHENIYA PORYADKA V OGROMNOJ STEPENI OBLEGCHAET RABOTU. v NASHEM RASPORYAZHENII ESTX MNOGO METODOV SORTIROVKI (GL.~5), PO|TOMU DLYA NAS NE SOSTAVIT TRUDA UPORYADOCHITX FAJL, CHTOBY ZATEM BYSTREE PROIZVESTI POISK. rAZUMEETSYA, ESLI NUZHEN LISHX ODNOKRATNYJ PROSMOTR, TO BYSTREE PROIZVESTI EGO POSLEDOVATELXNO, BEZ PREDVARITELXNOJ SORTIROVKI. nO ESLI V ODNOJ I TOJ ZHE TABLICE PRIHODITSYA CHASTO PROIZVODITX POISK, TO |FFEKTIVNEE UPORYADOCHITX EE. v |TOM PUNKTE MY IZUCHIM METODY POISKA V TABLICAH SO SLUCHAJNYM DOSTUPOM I UPORYADOCHENNYMI KLYUCHAMI $$ K_1K_i \rem{[$R_1$, $R_2$,~\dots, $R_i$ ISKLYUCHAYUTSYA IZ RASSMOTRENIYA].}\cr } $$ uMELO DEJSTVUYA V KAZHDOM IZ |TIH SLUCHAEV, MY S|KONOMIM MNOGO VREMENI PO SRAVNENIYU S POSLEDOVATELXNYM POISKOM, ESLI TOLXKO $i$ NE SLISHKOM BLIZKO K KONCAM TABLICY. tAKIM OBRAZOM, UPORYADOCHENIE VEDET K |FFEKTIVNYM ALGORITMAM. \section bINARNYJ POISK. pOZHALUJ, PERVYM PRIHODIT V GOLOVU SLEDUYUSHCHIJ OCHEVIDNYJ METOD: SNACHALA SRAVNITX~$K$ SO SREDNIM KLYUCHOM V TABLICE. rEZULXTAT SRAVNENIYA POZVOLIT OPREDELITX, V KAKOJ POLOVINE FAJLA PRODOLZHITX POISK, PRIMENYAYA K NEJ TU ZHE PROCEDURU, I T. D. pOSLE NE BOLEE CHEM PRIMERNO $\log_2 N$ SRAVNENIJ LIBO KLYUCH BUDET NAJDEN, LIBO BUDET USTANOVLENO EGO OTSUTSTVIE. tAKAYA PROCEDURA INOGDA NAZYVAETSYA "LOGARIFMICHESKIM POISKOM" ILI "METODOM DELENIYA POPOLAM", NO NAIBOLEE UPOTREBITELXNYJ TERMIN---\dfn{BINARNYJ POISK.} oSNOVNAYA IDEYA BINARNOGO POISKA DOVOLXNO PROSTA, DETALI ZHE NETRIVIALXNY, I DLYA MNOGIH HOROSHIH PROGRAMMISTOV NE ODNA POPYTKA NAPISATX PRAVILXNUYU PROGRAMMU ZAKONCHILASX NEUDACHEJ. oDNA IZ NAIBOLEE POPULYARNYH REALIZACII METODA ISPOLXZUET DVA UKAZATELYA---$l$ I~$u$, SOOTVETSTVUYUSHCHIE VERHNEJ I NIZHNEJ GRANICAM POISKA, I SOSTOIT V SLEDUYUSHCHEM. \alg v.(bINARNYJ POISK.) s POMOSHCHXYU DANNOGO ALGORITMA RAZYSKIVAETSYA ARGUMENT~$K$ V TABLICE ZAPISEJ $R_1$, $R_2$,~\dots, $R_N$, KLYUCHI KOTORYH RASPOLOZHENY V VOZRASTAYUSHCHEM PORYADKE: $K_1K_i$, TO PEREJTI NA~\stp{5}; ESLI $K=K_i$, ALGORITM ZAKANCHIVAETSYA UDACHNO. \st[kORREKTIROVKA~$u$]. uSTANOVITX $u\asg i-1$ I VERNUTXSYA K SHAGU~\stp{2}. \st[kORREKTIROVKA~$l$.] uSTANOVITX $l\asg i+1$ I VERNUTXSYA K SHAGU~\stp{2}. \algend %%485 \picture{rIS. 3. bINARNYJ POISK.} rISUNOK~4 ILLYUSTRIRUET POVEDENIE ALGORITMA v V DVUH SLUCHAYAH: KOGDA RAZYSKIVAETSYA ARGUMENT, RAVNYJ IMEYUSHCHEMUSYA V TABLICE CHISLU~653, I KOGDA RAZYSKIVAETSYA OTSUTSTVUYUSHCHIJ ARGUMENT~400. sKOBKI SOOTVETSTVUYUT UKAZATELYAM $l$ I~$u$, PODCHERKNUTYJ KLYUCH PREDSTAVLYAET~$K_i$. v OBOIH SLUCHAYAH POISK KONCHAETSYA POSLE CHETYREH SRAVNENIJ. \prog B.(bINARNYJ POISK.) kAK I V PROGRAMMAH \S~6.1, PREDPOLAGAETSYA, CHTO $K_i$ ZANIMAET POLNOE SLOVO PO ADRESU $|KEY|+i$. pRIVODIMAYA NIZHE PROGRAMMA ISPOLXZUET $|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)~pOISK CHISLA 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)~pOISK CHISLA 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{rIS. 4. pRIMERY BINARNOGO POISKA.}\cr } $$ } %%486 \code START & ENT1 & 1 & 1 & Bl. nACHALXNAYA USTANOVKA. $l\asg 1$. & ENT2 & N & 1 & $u\asg N$. & JMP & 2F & 1 & nA B2. 5H & JE & SUCCESS & C1 & pEREHOD, ESLI $K=K_i$. & ENT1 & 1,3 & C1-S& B5. kORREKTIROVKA $l$. $l\asg l+1$. 2H & ENTA & 0,1 &C+1-S& B2. nAHOZHDENIE SEREDINY. & INCA & 0,2 &C+1-S& $|rA|\asg l+u$. & SRB & 1 &C+1-S& $|rA|\asg\floor{|rA|/2}$. (mENYAETSYA I~|rX|.) & STA & TEMP &C+1-S& & CMP1 & TEMP &C+1-S& & JG & FAILURE &C+1-S& pEREHOD, ESLI $uK_8$, ISPOLXZUETSYA PRAVOE PODDEREVO. nEUDACHNYJ POISK VEDET V ODIN IZ "VNESHNIH" KVADRATNYH UZLOV, ZANUMEROVANNYH OT~\leaf{0} DO~\leaf{$N$}; NAPRIMER, MY DOSTIGNEM UZLA~\leaf{6} TOGDA I TOLXKO TOGDA, KOGDA $K_6K_8$, $KK_i$, TO PEREJTI NA~\stp{4}; PRI $K=K_i$ ALGORITM OKANCHIVAETSYA UDACHNO. \st[uMENXSHENIE $i$.] (mY OPREDELILI POLOZHENIE INTERVALA, GDE NUZHNO PRODOLZHATX POISK. oN SODERZHIT $m$ ILI $m-1$~ZAPISEJ; $i$ UKAZYVAET NA PERVYJ |LEMENT SPRAVA OT INTERVALA.) eSLI $m=0$, TO ALGORITM OKANCHIVAETSYA NEUDACHNO. v PROTIVNOM SLUCHAE USTANOVITX $i\asg i-\ceil{m/2}$; $m\asg\floor{m/2}$ I VERNUTXSYA NA~\stp{2}. \st[uVELICHENIE $i$.] (sITUACIYA TA ZHE, CHTO I V SHAGE~\stp{3}, TOLXKO $i$~UKAZYVAET NA PERVYJ |LEMENT \emph{SLEVA} OT INTERVALA.) eSLI $m=0$, TO ALGORITM OKANCHIVAETSYA NEUDACHNO. v PROTIVNOM SLUCHAE USTANOVITX $i\asg i+\ceil{m/2}$; $m\asg\floor{m/2}$ I VERNUTXSYA NA~\stp{2}. \algend nA RIS.~6 PREDSTAVLENO BINARNOE DEREVO, SOOTVETSTVUYUSHCHEE POISKU PRI $N=10$. pRI NEUDACHNOM POISKE KAK RAZ PERED OKONCHANIEM %%490 RABOTY ALGORITMA MOZHET PROIZVODITXSYA LISHNEE SRAVNENIE; UZLY, OTVECHAYUSHCHIE |TIM SRAVNENIYAM, ZASHTRIHOVANY. dANNYJ PROCESS POISKA MOZHNO NAZVATX \emph{ODNORODNYM}, TAK KAK RAZNOSTX MEZHDU CHISLOM V UZLE UROVNYA~$\ell$ I CHISLOM V UZLE-PREDSHESTVENNIKE UROVNYA~$\ell-1$ ESTX POSTOYANNAYA VELICHINA~$\delta$ DLYA VSEH UZLOV UROVNYA~$\ell$. oBOSNOVATX PRAVILXNOSTX ALGORITMA~U MOZHNO SLEDUYUSHCHIM OBRAZOM. pREDPOLOZHIM, CHTO POISK NUZHNO PROIZVESTI V INTERVALE \picture{rIS. 6. bINARNOE DEREVO DLYA "ODNORODNOGO" BINARNOGO POISKA ($N=10$).} DLINY~$n-1$; SRAVNENIE SO SREDNIM |LEMENTOM (ESLI $n$ CHETNO) ILI S ODNIM IZ DVUH SREDNIH (ESLI $n$ NECHETNO) VYDELYAET DVA INTERVALA DLINY~$\floor{n/2}-1$ I~$\ceil{n/2}-1$. pOSLE POVTORENIYA |TOJ PROCEDURY $k$~RAZ MY POLUCHIM $2^k$~INTERVALOV S MINIMALXNOJ DLINOJ~$\floor{n/2^k}-1$ I MAKSIMALXNOJ DLINOJ~$\ceil{n/2^k}-1$. sLEDOVATELXNO, NA KAZHDOM |TAPE DLINY DVUH INTERVALOV RAZLICHAYUTSYA SAMOE BOLXSHEE NA~1, CHTO DELAET VOZMOZHNYM VYBOR PODHODYASHCHEGO "SREDNEGO" |LEMENTA BEZ ZAPOMINANIYA POSLEDOVATELXNOSTI TOCHNYH ZNACHENIJ DLIN. vAZHNOE PREIMUSHCHESTVO ALGORITMA~U SOSTOIT V TOM, CHTO NAM SOVSEM NE NUZHNO SOHRANYATX ZNACHENIE~$m$; NUZHNO LISHX SSYLATXSYA NA KOROTENXKUYU TABLICU ZNACHENIJ~$\delta$ DLYA KAZHDOGO UROVNYA. tAKIM OBRAZOM, ALGORITM SVODITSYA K SLEDUYUSHCHEJ PROCEDURE, ODINAKOVO HOROSHEJ I DLYA DVOICHNYH, I DLYA DESYATICHNYH evm. \alg C.(oDNORODNYJ BINARNYJ POISK.) aLGORITM ANALOGICHEN ALGORITMU~U, NO VMESTO VYCHISLENIJ, OTNOSYASHCHIHSYA K~$m$, ISPOLXZUET VSPOMOGATELXNUYU TABLICU VELICHIN $$ |DELTA|[j]=\floor{{N+2^{j-1}\over 2^j}}=\left({N\over 2^j}\right) \hbox{ OKRUGLENNOE}; \qquad 1\le j \le \floor{\log_2 N}+2. \eqno(6) $$ \st[nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg|DELTA| [1]$, $j\asg2$. %%491 \st[sRAVNENIE:] eSLI $KK_i$, TO PEREJTI NA~\stp{4}. pRI $K=K_i$ ALGORITM OKANCHIVAETSYA UDACHNO. \st[uMENXSHENIE $i$.] eSLI $|DELTA|[j]=0$, TO ALGORITM OKANCHIVAETSYA NEUDACHNO. v PROTIVNOM SLUCHAE USTANOVITX $i\asg i-|DELTA|[j]$, $j\asg j+1$ I VERNUTXSYA NA~\stp{2}. \st[uVELICHENIE~$i$.] eSLI $|DELTA|[j]=0$, ALGORITM OKANCHIVAETSYA NEUDACHNO. v PROTIVNOM SLUCHAE USTANOVITX $i\asg i+|DELTA|[j]$, $j\asg j+1$ I VERNUTXSYA NA~\stp{2}. \algend v UPR.~8 BUDET POKAZANO, CHTO ALGORITM SSYLAETSYA NA VSPOMOGATELXNYJ KLYUCH~$K_0=-\infty$ LISHX PRI CHETNYH~$N$. \prog C.(oDNORODNYJ BINARNYJ POISK.) eTA PROGRAMMA NA BAZE ALGORITMA~C PRODELYVAET TU ZHE RABOTU, CHTO I PROGRAMMA~B. iSPOLXZUYUTSYA $|rA|\equiv K$, $|rI1|\equiv i$, $|rI2|\equiv j$, $|rI3|\equiv |DELTA| [j]$. \code START & ENT1 & N+1/2 & 1 & C1. nACHALXNAYA USTANOVKA. & ENT2 & 2 & 1 & $j\asg 2$. & LDA & k & 1 & & JMP & 2F & 1 & 3H & JE & SUCCESS& C1 & pEREHOD, ESLI $K=K_i$. & J3Z & FAILURE& C1-S & pEREHOD, ESLI $|DELTA|[j]=0$. & DEC1 & 0,3 & C1-S-A& C3. uMENXSHENIE~$i$. 5H & INC2 & 1 & C-1 & $j\asg j+1$. 2H & LD3 & DELTA,2& C & C2. sRAVNENIE. & smra & KEY.1 & C & & JLE & 3B & C & pEREHOD, ESLI $K\le K_i$. & INC1 & 0,3 & C2 & C4. uVELICHENIE $i$. & J3NZ & 5B & C2 & pEREHOD, ESLI $|DELTA|[j]\ne0$. FAILURE& EQU & * & 1-S & vYHOD, ESLI NET V TABLICE. \endcode \progend pRI UDACHNOM POISKE |TOT ALGORITM SOOTVETSTVUET BINARNOMU DEREVU S TOJ ZHE DLINOJ VNUTRENNEGO PUTI, CHTO I ALGORITM~v, PO|TOMU SREDNEE CHISLO SRAVNENIJ~$C_N$ DAETSYA FORMULOJ~(4). pRI NEUDACHNOM POISKE ALGORITM~C VSEGDA SOVERSHAET ROVNO $\floor{\log_2N}+1$~SRAVNENIJ. pOLNOE VREMYA RABOTY PROGRAMMY~C NE VPOLNE SIMMETRICHNO PO OTNOSHENIYU K LEVYM I PRAVYM VETVYAM, TAK KAK $C1$ IMEET VES, BOLXSHIJ CHEM $C2$, NO V UPR.~9 BUDET POKAZANO, CHTO SLUCHAJ $K>K_i$ VSTRECHAETSYA PRIMERNO TAK ZHE CHASTO, KAK I~$KK_i$ I~$N>2^k$ USTANAVLIVAEM $i=i'=N+1-2^\ell$, GDE $\ell=\floor{\log_2(N-2^k)}+1$, I, DELAYA VID, CHTO PERVYM SRAVNENIEM BYLO $K>K_{i'}$, ISPOLXZUEM ODNORODNYJ POISK S $\delta=2^{\ell-1}$, $2^{\ell-2}$,~\dots, $1$, $0$. rISUNOK~7 ILLYUSTRIRUET METOD shERA PRI $N=10$. v METODE shERA NIKOGDA NE TREBUETSYA BOLEE $\floor{\log_2 N}+1$~SRAVNENIJ; SLEDOVATELXNO, ON DAET ODNO IZ LUCHSHIH SREDNIH CHISEL SRAVNENIYA, NESMOTRYA NA TO CHTO INOGDA PROHODIT CHEREZ NESKOLXKO POSLEDOVATELXNYH IZBYTOCHNYH SHAGOV (SR. S UPR.~12). eSHCHE ODNA MODIFIKACIYA BINARNOGO POISKA, ULUCHSHAYUSHCHAYA VSE RASSMOTRENNYE METODY PRI OCHENX BOLXSHIH $N$, OBSUZHDAETSYA V UPR.~23. v UPR.~24 IZLOZHEN ESHCHE BOLEE BYSTRYJ METOD! \section fIBONACHCHIEV POISK. pRI RASSMOTRENII MNOGOFAZNOGO SLIYANIYA (P.~5.4.2) MY VIDELI, CHTO CHISLA fIBONACHCHI MOGUT IGRATX ROLX, ANALOGICHNUYU STEPENYAM~$2$. pOHOZHEE YAVLENIE IMEET MESTO I V SLUCHAE POISKA, KOGDA S POMOSHCHXYU CHISEL fIBONACHCHI SOZDAYUTSYA METODY, SPOSOBNYE SOPERNICHATX S BINARNYM POISKOM. pREDLAGAEMYJ METOD DLYA NEKOTORYH evm PREDPOCHTITELXNEE BINARNOGO, TAK KAK ON VKLYUCHAET LISHX SLOZHENIE I VYCHITANIE; NET NEOBHODIMOSTI V DELENII NA~$2$. sLEDUET OTLICHATX PROCEDURU, KOTORUYU MY SOBI- %%493 RAEMSYA OBSUZHDATX, OT IZVESTNOJ CHISLENNOJ PROCEDURY "FIBONACHCHIEVA POISKA", KOTORAYA ISPOLXZUETSYA DLYA NAHOZHDENIYA MAKSIMUMA ODNOVERSHINNOJ FUNKCII [SR.~S~Fibonacci Quarterly, 4 (1966), 265--269]; SHOZHESTX NAZVANIJ VEDET K NEKOTOROJ PUTANICE. nA PERVYJ VZGLYAD FIBONACHCHIEV POISK KAZHETSYA VESXMA TAINSTVENNYM; ESLI PROSTO VZYATX PROGRAMMU I POPYTATXSYA OB®YASNITX EE RABOTU, TO SOZDASTSYA VPECHATLENIE, CHTO ONA RABOTAET S POMOSHCHXYU MAGII. nO TUMAN TAINSTVENNOSTI RASSEETSYA, KAK TOLXKO MY POSTROIM \picture{rIS. 8. dEREVO fIBONACHCHI PORYADKA 6.} SOOTVETSTVUYUSHCHEE DEREVO POISKA. pO|TOMU IZUCHENIE RASSMATRIVAEMOGO METODA NACHNEM S RASSKAZA O "FIBONACHCHIEVYH DEREVXYAH". nA RIS.~8 IZOBRAZHENO DEREVO fIBONACHCHI PORYADKA~$6$. zAMETXTE, CHTO ONO NESKOLXKO BOLXSHE NAPOMINAET REALXNYJ KUST, CHEM RASSMATRIVAVSHIESYA RANEE DEREVXYA, VOZMOZHNO, POTOMU, CHTO MNOGIE PRIRODNYE PROCESSY UDOVLETVORYAYUT ZAKONU fIBONACHCHI. vOOBSHCHE FIBONACHCHIEVO DEREVO PORYADKA~$k$ IMEET $F_{k+1}-1$~VNUTRENNIH (KRUGLYH) UZLOV I~$F_{k+1}$~VNESHNIH (KVADRATNYH) UZLOV; ONO STROITSYA SLEDUYUSHCHIM OBRAZOM: {\medskip\narrower \item{eSLI}~$k=0$ ILI~$k=1$, DEREVO SVODITSYA PROSTO K~\leaf{0}. \item{eSLI}~$k\ge2$, KORNEM YAVLYAETSYA~\node{F_k}; LEVOE PODDEREVO ESTX DEREVO fIBONACHCHI PORYADKA~$k-1$; PRAVOE PODDEREVO ESTX DEREVO fIBONACHCHI PORYADKA~$k-2$ S CHISLAMI V UZLAH, UVELICHENNYMI NA~$F_k$. \medskip} \noindent zAMETIM, CHTO, ZA ISKLYUCHENIEM VNESHNIH UZLOV, CHISLA, SOOTVETSTVUYUSHCHIE PREEMNIKAM KAZHDOGO VNUTRENNEGO UZLA, OTLICHAYUTSYA OT CHISLA V |TOM UZLE NA ODNU I TU ZHE VELICHINU, A IMENNO NA CHISLO fIBONACHCHI. tAK, $5=8-F_4$, $11=8+F_4$ (RIS.~8). eSLI RAZNOSTX BYLA RAVNA~$F_j$, TO NA SLEDUYUSHCHEM UROVNE SOOTVETSTVUYUSHCHAYA %%494 RAZNOSTX SOSTAVIT DLYA LEVOJ VETVI $F_{j-1}$, A DLYA PRAVOJ~$F_{j-2}$. tAK, NAPRIMER, $3=5-F_3$, a~$10=11-F_2$. eTI NABLYUDENIYA V SOVOKUPNOSTI S PODHODYASHCHIM MEHANIZMOM RASPOZNAVANIYA VNESHNIH UZLOV DAYUT \alg F.(fIBONACHCHIEV POISK.) aLGORITM PREDNAZNACHAETSYA DLYA POISKA ARGUMENTA~$K$ V TABLICE ZAPISEJ $R_1$, $R_2$,~\dots, $R_N$, RASPOLOZHENNYH V PORYADKE VOZRASTANIYA KLYUCHEJ $K_1K_i$, TO PEREJTI NA~\stp{4}; ESLI $K=K_i$, ALGORITM ZAKANCHIVAETSYA UDACHNO. \st[uMENXSHENIE~$i$.] eSLI~$q=0$, ALGORITM ZAKANCHIVAETSYA NEUDACHNO. eSLI~$q\ne 0$, TO USTANOVITX $i\asg i-q$, ZAMENITX $(p, q)$ NA~$(q, p-q)$ I VERNUTXSYA NA~\stp{2}. \st[uVELICHENIE~$i$.] eSLI~$p=1$, ALGORITM ZAKANCHIVAETSYA NEUDACHNO. eSLI~$p\ne1$, USTANOVITX $i\asg i+q$, $p\asg p-q$, $q\asg q-p$ I VERNUTXSYA NA~\stp{2}. \algend v PRIVODIMOJ NIZHE REALIZACII ALGORITMA~F DLYA MASHINY \MIX\ SKOROSTX UVELICHIVAETSYA ZA SCHET DUBLIROVANIYA VNUTRENNEGO CIKLA, V ODNOM IZ |KZEMPLYAROV KOTOROGO $p$~HRANITSYA V~|rI2|, A~$q$---V~|rI3|, V DRUGOM ZHE REGISTRY MENYAYUTSYA ROLYAMI; |TO UPROSHCHAET SHAG~F3. nA SAMOM DELE PROGRAMMA HRANIT V REGISTRAH $p-1$ I~$q-1$, CHTO UPROSHCHAET PROVERKU "$p=1$?" V SHAGE~F4. \prog F.(fIBONACHCHIEV POISK.) zNACHENIYA REGISTROV: $|rA|\equiv K$, $|rI1|\equiv i$, $(|rI2|, |rI3|)\equiv p-l$, $(|rI3|, |rI2|)\equiv q-l$. \code START & LDA & K & 1 & F1. nACHALXNAYA USTANOVKA. & 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 & nA F2. \twocols F4A & INC1 &1,3 & F4B &INC1 &1,2 & C2-S-A & F4. uVELICHENIE $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 & F2v &CMPA &KEY,1 & G & F2. sRAVNENIE. & JL &F3A & &JL &F3B & G & nA Fz, ESLI $K0$. & JMP &FAILURE& &JMP &FAILURE& 1-S-A & vYHOD, ESLI NET V TABLICE. \endtwocols \endcode \progend v UPR.~18 ANALIZIRUETSYA VREMYA RABOTY |TOJ PROGRAMMY. rISUNOK~8 POKAZYVAET, A ANALIZ DOKAZYVAET, CHTO VLEVO MY IDEM NESKOLXKO CHASHCHE, CHEM VPRAVO. chEREZ $C$, $C1$ I~$C2-S$ OBOZNACHIM CHISLO VYPOLNENIJ SHAGOV F2, F3 I~F4 SOOTVETSTVENNO. iMEEM $$ \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) $$ zNACHIT, LEVAYA VETVX VYBIRAETSYA PRIMERNO V $\phi=1.618$~RAZA CHASHCHE PRAVOJ (|TO MOZHNO BYLO PREDVIDETX, TAK KAK KAZHDAYA PROBA DELIT RASSMATRIVAEMYJ INTERVAL NA DVE CHASTI, PRICHEM LEVAYA CHASTX PRIMERNO V $\phi$~RAZ DLINNEE PRAVOJ). sREDNEE VREMYA RABOTY PROGRAMMY F SOSTAVLYAET PRIMERNO $$ \eqalign{ (6\phi k/\sqrt{5}-(2+22\phi)/5)u &\approx (6.252\log_2 N-4.6)u \rem {DLYA UDACHNOGO POISKA;}\cr (6\phi k/\sqrt{5}+(58/(27\phi))/5)u&\approx (6.252\log_2 N+5.8)u \rem{DLYA NEUDACHNOGO POISKA.}\cr } \eqno(9) $$ eTO NESKOLXKO LUCHSHE, CHEM~(7), HOTYA V NAIHUDSHEM SLUCHAE PROGRAMMA~F RABOTAET PRIMERNO $(8.6\log_2 N)u$, T.E. CHUTX-CHUTX MEDLENNEE PROGRAMMY~s. \section iNTERPOLYACIONNYJ POISK. zABUDEM NA MINUTU O VYCHISLITELXNYH MASHINAH I PROANALIZIRUEM, KAK PROIZVODIT POISK CHELOVEK. iNOGDA POVSEDNEVNAYA ZHIZNX PODSKAZYVAET PUTX K SOZDANIYU HOROSHIH ALGORITMOV. pREDSTAVXTE, CHTO VY ISHCHETE SLOVO V SLOVARE. mALOVEROYATNO, CHTO VY SNACHALA ZAGLYANETE V SEREDINU SLOVARYA, ZATEM OTSTUPITE OT NACHALA NA~$1/4$ ILI~$3/4$ I~T.~D., KAK V BINARNOM POISKE, I UZH SOVSEM NEVEROYATNO, CHTO VY VOSPOLXZUETESX FIBONACHCHIEVYM POISKOM! eSLI NUZHNOE SLOVO NACHINAETSYA S BUKVY~A, VY, PO-VIDIMOMU, NACHNETE POISK GDE-TO V NACHALE SLOVARYA. vO MNOGIH SLOVARYAH %%496 IMEYUTSYA "POBUKVENNYE VYSECHKI" DLYA BOLXSHOGO PALXCA, KOTORYE POKAZYVAYUT STRANICU, GDE NACHINAYUTSYA SLOVA NA DANNUYU BUKVU. tAKUYU PALXCEVUYU TEHNIKU LEGKO PRISPOSOBITX K evm, CHTO USKORIT POISK; SOOTVETSTVUYUSHCHIE ALGORITMY ISSLEDUYUTSYA V \S~6.3. kOGDA NAJDENA OTPRAVNAYA TOCHKA DLYA POISKA, VASHI DALXNEJSHIE DEJSTVIYA MALO POHOZHI NA RASSMOTRENNYE METODY. eSLI VY ZAMETITE, CHTO NUZHNOE SLOVO DOLZHNO NAHODITXSYA GORAZDO DALXSHE OTKRYTOJ STRANICY, VY PROPUSTITE PORYADOCHNOE IH KOLICHESTVO, PREZHDE CHEM SDELATX SLEDUYUSHCHUYU POPYTKU. eTO V KORNE OTLICHAETSYA OT PREDYDUSHCHIH ALGORITMOV, KOTORYE NE DELAYUT RAZLICHIYA MEZHDU "MNOGO BOLXSHE" I "CHUTX BOLXSHE". mY PRIHODIM K TAKOMU ALGORITMU, NAZYVAEMOMU "INTERPOLYACIONNYM POISKOM": ESLI IZVESTNO, CHTO $K$ LEZHIT MEZHDU~$K_l$ I~$K_u$, TO SLEDUYUSHCHUYU PROBU DELAEM PRIMERNO NA RASSTOYANII $(u-l)(K-K_l)/(K_u-K_l)$ OT~$l$, PREDPOLAGAYA, CHTO KLYUCHI YAVLYAYUTSYA CHISLAMI, VOZRASTAYUSHCHIMI PRIBLIZITELXNO KAK ARIFMETICHESKAYA PROGRESSIYA. iNTERPOLYACIONNYJ POISK ASIMPTOTICHESKI PREDPOCHTITELXNEE BINARNOGO; PO SUSHCHESTVU, ODIN SHAG BINARNOGO POISKA UMENXSHAET KOLICHESTVO "PODOZREVAEMYH" ZAPISEJ S~$n$ DO~${1\over2}n$, A ODIN SHAG INTERPOLYACIONNOGO (ESLI KLYUCHI V TABLICE RASPREDELENY SLUCHAJNYM OBRAZOM)---S~$n$ DO~$\sqrt{n}$. mOZHNO POKAZATX, CHTO INTERPOLYACIONNYJ POISK TREBUET V SREDNEM OKOLO $\log_2 \log_2 N$~SHAGOV (UPR.~22). k SOZHALENIYU, |KSPERIMENTY NA evm POKAZALI, CHTO INTERPOLYACIONNYJ POISK UMENXSHAET CHISLO SRAVNENIJ NE NASTOLXKO, CHTOBY KOMPENSIROVATX VOZNIKAYUSHCHIJ DOPOLNITELXNYJ RASHOD VREMENI, KOGDA TABLICA, V KOTOROJ PROIZVODITSYA POISK, HRANITSYA VO VNUTRENNEJ ("BYSTROJ") PAMYATI. rAZNOSTX MEZHDU $\log_2 \log_2 N$ I~$\log_2 N$ STANOVITSYA SUSHCHESTVENNOJ LISHX DLYA VESXMA BOLXSHIH~$N$, A TIPICHNYE FAJLY NEDOSTATOCHNO SLUCHAJNY. iNTERPOLYACIYA USPESHNA DO NEKOTOROJ STEPENI LISHX V PRIMENENII K POISKU NA \emph{VNESHNIH} ZAPOMINAYUSHCHIH USTROJSTVAH. (zAMETIM, CHTO RUCHNOJ PROSMOTR SLOVARYA ESTX, V SUSHCHNOSTI, NE VNUTRENNIJ, A VNESHNIJ POISK; |TO YAVLYAETSYA TEMOJ POSLEDUYUSHCHIH RASSMOTRENIJ.) \section iSTORIYA I BIBLIOGRAFIYA. pERVYM IZVESTNYM PRIMEROM DLINNOGO PERECHNYA |LEMENTOV, UPORYADOCHENNYH DLYA OBLEGCHENIYA POISKA, YAVLYAETSYA ZNAMENITAYA VAVILONSKAYA TABLICA OBRATNYH VELICHIN Inakibit-Anu, DATIRUEMAYA PRIMERNO 200~G. DO~N.|. eTA GLINYANAYA PLASTINKA, OCHEVIDNO, OTKRYVALA SERIYU IZ TREH TABLICHEK, SODERZHASHCHIH BOLEE 500 MNOGOZNACHNYH SHESTIDESYATERICHNYH CHISEL I OBRATNYH IM VELICHIN, OTSORTIROVANNYH V LEKSIKOGRAFICHESKOM PORYADKE. nAPRIMER, VSTRECHAETSYA TAKAYA POSLEDOVATELXNOSTX: %%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 } sORTIROVKA 500 PODOBNYH CHISEL SREDSTVAMI TEH VREMEN KAZHETSYA FENOMENALXNOJ. [sM. TAKZHE D.~e.~Knuth, {\sl CACM\/}, {\bf 15} (1972), 671--677, GDE SODERZHITSYA MNOGO DOPOLNITELXNYH SVEDENIJ.] dOVOLXNO ESTESTVENNO RASPOLAGATX PO PORYADKU CHISLA, NO OTNOSHENIE PORYADKA MEZHDU BUKVAMI ILI SLOVAMI NE PREDSTAVLYAETSYA SAMO SOBOJ OCHEVIDNYM. oDNAKO POSLEDOVATELXNOSTI DLYA SRAVNIVANIYA BUKV PRISUTSTVOVALI UZHE V NAIBOLEE DREVNIH ALFAVITAH. nAPRIMER, MNOGIE BIBLEJSKIE PSALMY SODERZHAT STIHI, SLEDUYUSHCHIE DRUG ZA DRUGOM V STROGO ALFAVITNOM PORYADKE: PERVYJ STIH NACHINAETSYA S~ALEFA, VTOROJ S~BETA I~T.~D.; |TO OBLEGCHALO ZAPOMINANIE. iNOGDA STANDARTNAYA POSLEDOVATELXNOSTX BUKV ISPOLXZOVALASX SEMITAMI I GREKAMI DLYA OBOZNACHENIYA CHISEL; NAPRIMER, $\alpha$, $\beta$, $\gamma$ OBOZNACHALI 1, 2, 3 SOOTVETSTVENNO. oDNAKO ISPOLXZOVANIE ALFAVITNOGO PORYADKA DLYA SLOV CELIKOM BYLO, VEROYATNO, GORAZDO BOLEE POZDNIM IZOBRETENIEM; VESHCHI, OCHEVIDNYE SEJCHAS DAZHE DLYA REBENKA, KOGDA-TO TREBOVALOSX OB®YASNYATX VZROSLYM! nEKOTORYE DOKUMENTY, DATIRUEMYE PRIMERNO 300~G. DO~N.|., NAJDENNYE NA OSTROVAH eGEJSKOGO MORYA, SODERZHAT SPISKI CHLENOV NESKOLXKIH RELIGIOZNYH OBSHCHIN; ONI UPORYADOCHENY, NO TOLXKO PO PERVOJ BUKVE, T.~E. PREDSTAVLYAYUT SOBOJ REZULXTAT LISHX PERVOGO PROHODA SLEVA NAPRAVO PORAZRYADNOJ SORTIROVKI. gRECHESKIE PAPIRUSY 134--135~G. N.~|. SODERZHAT FRAGMENTY SCHETOV, V KOTORYH FAMILII NALOGOPLATELXSHCHIKOV UPORYADOCHENY PO PERVYM DVUM BUKVAM. aPOLLONIJ sOFIST% \note{1}{oDIN IZ GRAMMATIKOV DREVNOSTI, RODOM IZ aLEKSANDRII.---{\sl pRIM. PEREV.\/}} ISPOLXZOVAL ALFAVITNOE UPORYADOCHENIE PO PERVYM DVUM, A CHASTO I PO POSLEDUYUSHCHIM BUKVAM V SVOEM "sLOVARE GOMEROVSKIH SLOV" (I~VEK N.~|.). iZVESTNO NESKOLXKO PRIMEROV BOLEE SOVERSHENNOGO ALFAVITNOGO UPORYADOCHENIYA, SKAZHEM VYDAYUSHCHIESYA "kOMMENTARII K gIPPOKRATU" gALENA% \note{2}{rIMSKIJ VRACH I ESTESTVOISPYTATELX, KLASSIK ANTICHNOJ MEDICINY.---{\sl pRIM. PEREV.\/}} (OKOLO 200~G.), NO |TO BYLO OCHENX REDKIM YAVLENIEM. tAK, V HRONIKE sV.~iSIDORA% \note{3}{iSIDOR sEVILXSKIJ---ISPANSKIJ EPISKOP, VYDAYUSHCHIJSYA UCHENYJ I PISATELX.---{\sl pRIM. PEREV.\/}} "Etymologiarum" (OKOLO 630~G., KNIGA~X) SLOVA UPORYADOCHENY LISHX PO PERVOJ BUKVE, A V NAIBOLEE RANNEM IZ IZVESTNYH DVUYAZYCHNYH SLOVAREJ "Corpus Glossary" (OKOLO 725~G.) --- TOLXKO PO DVUM PERVYM. dVE POSLEDNIE RABOTY BYLI, VEROYATNO, KRUPNEJSHIMI NECHISLOVYMI FAJLAMI DANNYH, SKOMPILIROVANNYMI V SREDNIE VEKA. %% 498 tOLXKO V KNIGE dZHOVANNI gENU|ZSKOGO "Catholicon" (1286~G.) MY NAHODIM PODROBNOE OPISANIE PRAVILXNOGO ALFAVITNOGO PORYADKA. v PREDISLOVII dZHOVANNI OB®YASNYAET, CHTO \ctable{ \hfill\it # \bskip & PREDSHESTVUET \it #\hfill\cr amo & bibo \cr abeo & adeo \cr amatus & amor \cr imprudens & impudens\cr iusticia & iustus\cr polisintheton & polissenus \cr } (T.~E. PRIVODIT PRIMERY SITUACIJ, KOGDA PORYADOK OPREDELYAETSYA PO $1$, $2$,~\dots, $6\hbox{-J}$~BUKVAM) "I DALEE ANALOGICHNO". oN ZAMECHAET, .CHTO OTKRYTIE |TOGO PRAVILA POTREBOVALO ZNACHITELXNYH.USILIJ. "ya PROSHU vAS, UVAZHAEMYJ CHITATELX, NE PREZIRATX |TU MOYU BOLXSHUYU RABOTU I |TOT PORYADOK KAK NECHTO NICHEGO NE STOYASHCHEE". rAZVITIE ALFAVITNOGO PORYADKA DO MOMENTA IZOBRETENIYA KNIGOPECHATANIYA PODROBNO IZUCHIL l.~u.~dEJLI ({\sl Collection Latomus,\/} {\bf 90} (1967), 100~pp.). oN OBNARUZHIL NESKOLXKO INTERESNYH STARINNYH RUKOPISEJ, KOTORYE, NESOMNENNO, ISPOLXZOVALISX KAK CHERNOVIKI PRI SORTIROVKE SLOV PO PERVOJ BUKVE (SM. STR.~87--90 EGO MONOGRAFII). pERVYJ SLOVARX ANGLIJSKOGO YAZYKA rOBERTA kODRI "Table Alphabeticall" (London, 1604) SODERZHIT SLEDUYUSHCHIE INSTRUKCII: {\narrower eSLI SLOVO, KOTOROE TEBE NUZHNO NAJTI, NACHINAETSYA S~(a), SMOTRI V NACHALO |TOJ KNIGI, A ESLI S~(v)---TO V KONEC. oPYATX ESLI SLOVO NACHINAETSYA S~(ca), SMOTRI V NACHALO BUKVY~(c), A ESLI S~(cu) TO V KONEC. i TAK DO KONCA SLOVA. } \noindent iNTERESNO ZAMETITX, CHTO kODRI VO VREMYA PODGOTOVKI SLOVARYA, VEROYATNO, SAM UCHILSYA RASSTAVLYATX SLOVA V ALFAVITNOM PORYADKE; NA NESKOLXKIH PERVYH STRANICAH VSTRECHAETSYA MNOGO NEPRAVILXNO STOYASHCHIH SLOV, ZATO DALXSHE CHISLO OSHIBOK SUSHCHESTVENNO UMENXSHAETSYA. bINARNYJ POISK VPERVYE UPOMYANUT dZHONOM mOCHLI V DISKUSSII, KOTORAYA BYLA, POZHALUJ, PERVYM OPUBLIKOVANNYM OBSUZHDENIEM METODOV NECHISLENNOGO PROGRAMMIROVANIYA [SM. Theory and techniques for the design of electronic digital computers, ed. by G.~W.~Patterson, 3 (1946); 22.8--22.9]. v TECHENIE 50-H~GODOV METOD STANOVITSYA "HOROSHO IZVESTNYM", NO, KAZHETSYA, NIKTO NE RAZRABATYVAL DETALI ALGORITMA DLYA~$N\ne 2^n-1$. [sM. A.~D.~Booth, {\sl Nature,\/} {\bf 176} (1955), 565; A.~I.~Dumey, {\sl Computers and Automation, \/} {\bf 5} (December, 1956), 7, GDE BINARNYJ POISK IMEET NAZVANIE "dVADCATX VOPROSOV"; D.~D.~McCracken, Digital Computer Programming (Wiley, 1957), 201--203; M.~Halpern, {\sl CACM\/} {\bf 1, 2} (February, 1958), 1--3.] %%499 pO-VIDIMOMU, ALGORITM BINARNOGO POISKA, PRIGODNYJ DLYA VSEH~$N$, VPERVYE OPUBLIKOVAN bOTTENBRUKOM [{\sl JACM,\/} {\bf 9} (1962), 214]. oN PREDSTAVIL INTERESNUYU MODIFIKACIYU ALGORITMA~B, KOGDA PROVERKI NA RAVENSTVO OTODVIGAYUTSYA V KONEC ALGORITMA. iSPOLXZUYA V SHAGE~B2 $i\asg\ceil{(l+u)/2}$ VMESTO~$\floor{(l+u)/2}$, ON USTANAVLIVAET $l\asg i$ PRI~$K\ge K_i$; TOGDA $u-l$ UMENXSHAETSYA POSLE KAZHDOGO SHAGA. v KONCE, KOGDA $l=u$, IMEEM $K_l\le K1$, PRI KOTORYH ALGORITMY~v I~s ABSOLYUTNO |KVIVALENTNY V TOM SMYSLE, CHTO ONI SOVERSHAYUT ODINAKOVYE, POSLEDOVATELXNOSTI SRAVNENIJ PRI VSEH ARGUMENTAH POISKA? \ex[21] oB®YASNITE, KAK NAPISATX \MIX-PROGRAMMU DLYA ALGORITMA~C, SODERZHASHCHUYU PRIMERNO $7\log_2 N$~KOMAND, VREMYA RABOTY KOTOROJ SOSTAVIT PRIBLIZITELXNO $4.5\log_2 N$~EDINIC? \ex[20] nARISUJTE DEREVO BINARNOGO POISKA, SOOTVETSTVUYUSHCHEE METODU shERA PRI~$N=12$. \ex[m24] zATABULIRUJTE SREDNIE CHISLA SRAVNENIJ V METODE shERA DLYA $1\le N<16$, RASSMATRIVAYA KAK UDACHNYE, TAK I NEUDACHNYE POISKI. \ex[21] oB®YASNITE, KAK PRISPOSOBITX ALGORITM~F DLYA RABOTY S LYUBYM~$N\ge 1$. \ex[21] nA RIS.~9 IZOBRAZHENA DIAGRAMMA RAZMNOZHENIYA KROLIKOV V ISHODNOJ ZADACHE fIBONACHCHI (SR.~S~P.~1.2.8). sUSHCHESTVUET LI PROSTAYA SVYAZX MEZHDU |TOJ DIAGRAMMOJ I FIBONACHCHIEVYM DEREVOM RESHENIJ? \ex[m19] pRI KAKIH ZNACHENIYAH~$k$ FIBONACHCHIEVO DEREVO PORYADKA~$k$ OPREDELYAET OPTIMALXNUYU PROCEDURU POISKA, T.~E. TAKUYU, PRI KOTOROJ SREDNEE CHISLO SRAVNENIJ MINIMALXNO? \ex[m21] iZ UPR.~1.2.8-34 (ILI UPR.~5.4.2-10) MY ZNAEM, CHTO LYUBOE NATURALXNOE CHISLO~$n$ EDINSTVENNYM OBRAZOM PREDSTAVLYAETSYA V VIDE SUMMU CHISEL fIBONACHCHI: $n=F_{a_1}+F_{a_2}+\cdots+F_{a_r}$, GDE $r\ge 1$, $a_j\ge a_{j+1}+2$ PRI~$1\le j1$.} $$ eTO PROISHODIT POTOMU, CHTO POSLE PERVOGO SRAVNENIYA POISK PRIMERNO S VEROYATNOSTXYU~$p$ SVODITSYA K POISKU SREDI $pN$~|LEMENTOV I S VEROYATNOSTXYU $q$---K POISKU SREDI $qN$~|LEMENTOV. pRI BOLXSHIH~$N$ MOZHNO PRENEBRECHX |FFEKTOM NIZSHEGO PORYADKA, SVYAZANNYM S TEM, CHTO CHISLA~$pN$ I~$qN$ NE CELYE. \medskip \item{a)} pOKAZHITE, CHTO $C(N)=\log_b N$ TOCHNO UDOVLETVORYAET UKAZANNYM SOOTNOSHENIYAM PRI NEKOTOROM~$b$. dLYA BINARNOGO I FIBONACHCHIEVA POISKOV VELICHINA~$b$ POLUCHAETSYA IZ VYVEDENNYH RANEE FORMUL. \item{b)} nEKTO RASSUZHDAL TAK: "s VEROYATNOSTXYU~$p$ DLINA RASSMATRIVAEMOGO INTERVALA DELITSYA NA~$1/p$, S VEROYATNOSTXYU~$q$---NA~$1/q$. sLEDOVATELXNO INTERVAL DELITSYA V SREDNEM NA~$p(1/p)+q (1/q)=2$, TAK CHTO ALGORITM V TOCHNOSTI TAK ZHE HOROSH, KAK I BINARNYJ POISK, NEZAVISIMO OT~$p$ I~$q$". eSTX LI OSHIBKA V |TIH RASSUZHDENIYAH? \medskip \ex[20] nARISUJTE BINARNOE DEREVO, SOOTVETSTVUYUSHCHEE INTERPOLYACIONNOMU POISKU PRI~$N=10$. \ex[m43] (e.~k.~yaO I~f.~f.~yaO.) pOKAZHITE,, CHTO DOLZHNYM OBRAZOM OFORMLENNYJ INTERPOLYACIONNYJ POISK V SREDNEM TREBUET (ASIMPTOTICHESKI) $\log_2\log_2 N$~SRAVNENIJ, ESLI $N$~OTSORTIROVANNYH KLYUCHEJ IMEYUT NEZAVISIMYE RAVNOMERNYE RASPREDELENIYA. bOLEE TOGO, VSE ALGORITMY POISKA PO TAKIM TABLICAM DOLZHNY SOVERSHATX V SREDNEM $\log_2 \log_2 N$~SRAVNENIJ (OCENKA ASIMPTOTICHESKAYA). \rex[25] aLGORITM BINARNOGO POISKA g.~bOTTENBRUKA, UPOMYANUTYJ V KONCE PUNKTA, "OTKLADYVAET" PROVERKI NA RAVENSTVO DO SAMOGO KONCA POISKA. (vO %%502 VREMYA RABOTY ALGORITMA MY ZNAEM, CHTO $K_l\le K2^{36}$ KOMPENSIRUETSYA NEOBHODIMOSTX DOPOLNITELXNOJ ITERACII!) pOKAZHITE, CHTO \emph{LYUBOJ} ALGORITM POISKA, SOOTVETSTVUYUSHCHIJ BINARNOMU DEREVU I RAZVETVLYAYUSHCHIJSYA PO TREM NAPRAVLENIYAM ($<$, $=$, ILI~$>$), MOZHNO PEREDELATX V ALGORITM, RAZVETVLYAYUSHCHIJSYA VO VNUTRENNIH UZLAH LISHX PO DVUM NAPRAVLENIYAM ($<$ ILI~$\ge$). v CHASTNOSTI, MODIFICIRUJTE TAKIM SPOSOBOM ALGORITM~C. \rex[23] pOLNOE BINARNOE DEREVO YAVLYAETSYA UDOBNYM SPOSOBOM PREDSTAVLENIYA V POSLEDOVATELXNYH YACHEJKAH DEREVA S MINIMALXNOJ DLINOJ PUTI. (sR. S P.~2.3.4.5.) pRIDUMAJTE |FFEKTIVNYJ METOD POISKA, OSNOVANNYJ NA TAKOM PREDSTAVLENII. [\emph{uKAZANIE:} MOZHNO LI V BINARNOM POISKE ISPOLXZOVATX UMNOZHENIE NA~$2$ VMESTO DELENIYA NA~$2$?] \rex[m25] pREDPOLOZHIM, CHTO U BINARNOGO DEREVA IMEETSYA $a_k$~VNUTRENNIH I $b_k$~VNESHNIH UZLOV NA UROVNE~$k$, $k=0$, $1$,~\dots. (kORENX NAHODITSYA NA NULEVOM UROVNE.) tAK, DLYA RIS.~8 IMEEM $(a_0, a_1,~\ldots, a_6)=(1, 2, 4, 4, 1, 0)$ I $(b_0, b_1,~\ldots, b_6)=(0, 0, 0, 4, 7, 2)$. (a)~pOKAZHITE, CHTO SUSHCHESTVUET PROSTOE ALGEBRAICHESKOE SOOTNOSHENIE, SVYAZYVAYUSHCHEE PROIZVODYASHCHIE FUNKCII $A(z)=\sum_{k}a_kz^k$ I~$B(z)=\sum_k b_kz^k$. (b)~rASPREDELENIE VEROYATNOSTEJ PRI UDACHNOM POISKE PO BINARNOMU DEREVU IMEET PROIZVODYASHCHUYU FUNKCIYU $g(z)=zA(z)/N$, A PRI NEUDACHNOM POISKE PROIZVODYASHCHAYA FUNKCIYA ESTX $h(z)=B(z)/(N+1)$. (v OBOZNACHENIYAH P.~6.2.1 $C_N=\mean(g)$, $C'_N=\mean(h)$, A SOOTNOSHENIE~(2) SVYAZYVAET |TI VELICHINY.) nAJDITE ZAVISIMOSTX MEZHDU $\var(g)$ I~$\var(h)$. \ex[22] pOKAZHITE, CHTO DEREVO fIBONACHCHI SVYAZANO S SORTIROVKOJ MNOGOFAZNYM SLIYANIEM NA TREH LENTAH. \ex[M30] (X.~s.~sTOUN I dZH.~lINI.) rASSMOTRIM PROCESS POISKA, OSNOVANNYJ TOLXKO NA SRAVNENIYAH KLYUCHEJ I ISPOLXZUYUSHCHIJ ODNOVREMENNO $k$~PROCESSOROV. pRI KAZHDOM SHAGE POISKA OPREDELYAYUTSYA $k$~INDEKSOV $i_1$, $i_2$,~\dots, $i_k$ I MY SOVERSHAEM $k$~ODNOVREMENNYH SRAVNENIJ: ESLI~$K=K_j$ DLYA NEKOTOROGO~$j$, POISK KONCHAETSYA UDACHNO, V PROTIVNOM SLUCHAE PEREHODIM K SLEDUYUSHCHEMU SHAGU POISKA, OSNOVYVAYASX NA $2^k$~VOZMOZHNYH ISHODAH~$KK_{i_j}$, $1\le j\le k$. pOKAZHITE, CHTO TAKOJ PROCESS PRI~$N\to\infty$ DOLZHEN SOVERSHATX V SREDNEM PO KRAJNEJ MERE $\log_{k+1}N$~SHAGOV. (pREDPOLAGAETSYA, CHTO VSE KLYUCHI V TABLICE, TAKZHE KAK I ARGUMENT POISKA, RAVNOVEROYATNY.) (zNACHIT, PO SRAVNENIYU S ODNOPROCESSORNYM BINARNYM POISKOM MY VYIGRYVAEM V SKOROSTI NE V $k$~RAZ, KAK MOZHNO BYLO BY OZHIDATX, A LISHX V $\log_2(k+1)$~RAZ. v |TOM SMYSLE VYGODNEE KAZHDYJ PROCESSOR ISPOLXZOVATX DLYA OTDELXNOGO POISKA, A NE OB®EDINYATX IH.) \subsubchap{pOISK PO BINARNOMU DEREVU} %% 6.2.2 v PREDYDUSHCHEM PUNKTE MY VIDELI, CHTO ISPOLXZOVANIE NEYAVNOJ STRUKTURY BINARNOGO DEREVA OBLEGCHAET PONIMANIE BINARNOGO I FIBONACHCHIEVA POISKOV. rASSMOTRENIE SOOTVETSTVUYUSHCHIH DEREVXEV POZVOLILO ZAKLYUCHITX, CHTO PRI DANNOM~$N$ SREDI VSEH METODOV POISKA PUTEM SRAVNENIYA KLYUCHEJ BINARNYJ POISK SOVERSHAET MINIMALXNOE CHISLO SRAVNENIJ. nO METODY PREDYDUSHCHEGO PUNKTA PREDNAZNACHENY GLAVNYM OBRAZOM DLYA TABLIC FIKSIROVANNOGO RAZMERA, TAK KAK POSLEDOVATELXNOE RASPOLOZHENIE ZAPISEJ DELAET VSTAVKI I UDALENIYA DOVOLXNO TRUDOEMKIMI. eSLI TABLICA %%503 DINAMICHESKI IZMENYAETSYA, TO |KONOMIYA OT ISPOLXZOVANIYA BINARNOGO POISKA NE POKROET ZATRAT NA PODDERZHANIE UPORYADOCHENNOGO RASPOLOZHENIYA KLYUCHEJ. \emph{yaVNOE} ISPOLXZOVANIE STRUKTURY BINARNOGO DEREVA POZVOLYAET BYSTRO VSTAVLYATX I UDALYATX ZAPISI I PROIZVODITX |FFEKTIVNYJ POISK PO TABLICE. v REZULXTATE MY POLUCHAEM METOD, POLEZNYJ KAK DLYA POISKA, TAK I DLYA SORTIROVKI. tAKAYA GIBKOSTX DOSTIGAETSYA \picture{rIS. 10. bINARNOE DEREVO POISKA.} PUTEM DOBAVLENIYA V KAZHDUYU ZAPISX DVUH POLEJ DLYA HRANENIYA SSYLOK. mETODY POISKA PO RASTUSHCHIM TABLICAM, CHASTO NAZYVAYUT \emph{ALGORITMAMI TABLIC SIMVOLOV}, TAK KAK ASSEMBLERY, KOMPILYATORY I DRUGIE SISTEMNYE PROGRAMMY OBYCHNO ISPOLXZUYUT IH DLYA HRANENIYA OPREDELYAEMYH POLXZOVATELEM SIMVOLOV. nAPRIMER, KLYUCHOM ZAPISI V KOMPILYATORE MOZHET SLUZHITX SIMVOLICHESKIJ IDENTIFIKATOR, OBOZNACHAYUSHCHIJ PEREMENNUYU V NEKOTOROJ PROGRAMME NA fORTRANE ILI aLGOLE, A OSTALXNYE POLYA ZAPISI MOGUT SODERZHATX INFORMACIYU O TIPE PEREMENNOJ I EE RASPOLOZHENII V PAMYATI. iLI ZHE KLYUCHOM MOZHET BYTX SIMVOL PROGRAMMY DLYA \MIX, A OSTAVSHAYASYA CHASTX ZAPISI MOZHET SODERZHATX |KVIVALENT |TOGO SIMVOLA. pROGRAMMY POISKA S VSTAVKOJ PO DEREVU, KOTORYE BUDUT OPISANY V |TOM PUNKTE, OTLICHNO PODHODYAT DLYA ISPOLXZOVANIYA V KACHESTVE ALGORITMOV TABLIC SIMVOLOV, OSOBENNO ESLI ZHELATELXNO RASPECHATYVATX SIMVOLY V ALFAVITNOM PORYADKE. dRUGIE ALGORITMY, TABLIC SIMVOLOV OPISANY V \S~6.3 I~6.4. %%504 nA RIS.~10 IZOBRAZHENO BINARNOE DEREVO POISKA, SODERZHASHCHEE NAZVANIYA ODINNADCATI ZNAKOV ZODIAKA% \note{1}{zNAKI ZODIAKA, UPORYADOCHENNYE PO MESYACAM: kOZEROG, vODOLEJ, rYBY, oVEN, tELEC, bLIZNECY, rAK, lEV, dEVA, vESY, sKORPION, sTRELEC,---{\sl pRIM. PEREV.\/}}. eSLI TEPERX, OTPRAVLYAYASX OT KORNYA DEREVA, MY BUDEM ISKATX DVENADCATOE NAZVANIE, |SAGITTARIUS|, TO UVIDIM, CHTO ONO BOLXSHE, CHEM |CAPRICORN|, PO|TOMU NUZHNO IDTI VPRAVO; ONO BOLXSHE, CHEM |PISCES|,---SNOVA IDEM VPRAVO; ONO MENXSHE, CHEM |TAURUS|,---IDEM VLEVO; ONO MENXSHE, CHEM |SCORPIO|,--- I MY POPADAEM VO VNESHNIJ UZEL~\leaf{8}. pOISK BYL NEUDACHNYM; TEPERX PO OKONCHANII POISKA MY MOZHEM \emph{VSTAVITX} |SAGITTARIUS|, "PODVYAZYVAYA" EGO K DEREVU VMESTO VNESHNEGO UZLA~\leaf{8}. tAKIM OBRAZOM, TABLICA MOZHET RASTI BEZ PEREMESHCHENIYA SUSHCHESTVUYUSHCHIH ZAPISEJ. rISUNOK~10 POLUCHEN POSLEDOVATELXNOJ VSTAVKOJ, NACHINAYA S PUSTOGO DEREVA, KLYUCHEJ |CAPRICORN|, |AQUARIUS|, |PISCES|, |ARIES|, |TAURUS|, |GEMINI|, |CANCER|, |LEO|, |VIRGO|, |LIBRA|, |SCORPIO| V UKAZANNOM PORYADKE. nA RIS.~10 VSE KLYUCHI LEVOGO PODDEREVA KORNYA PREDSHESTVUYUT PO ALFAVITU SLOVU |CAPRICORN|, A V PRAVOM PODDEREVE STOYAT POSLE NEGO. aNALOGICHNOE UTVERZHDENIE SPRAVEDLIVO DLYA LEVOGO I PRAVOGO PODDEREVXEV LYUBOGO UZLA. oTSYUDA SLEDUET, CHTO PRI OBHODE DEREVA V \emph{SIMMETRICHNOM PORYADKE} KLYUCHI RASPOLAGAYUTSYA STROGO V ALFAVITNOM PORYADKE: $$ \displaylines{ |AQUARIUS|, |ARIES|, |CANCER|, |CAPRICORN|, |GEMINI|, \cr |LEO|, \ldots, |VIRGO|,\cr } $$ TAK KAK SIMMETRICHNYJ PORYADOK OSNOVAN NA PROHOZHDENII SNACHALA LEVOGO PODDEREVA KAZHDOGO UZLA, ZATEM SAMOGO UZLA, A ZATEM EGO PRAVOGO PODDEREVA (SR. S P.~2.3.1). nIZHE DAETSYA PODROBNOE OPISANIE PROCESSA POISKA S VSTAVKOJ. \alg t.(pOISK S VSTAVKOJ PO DEREVU.) dANA TABLICA ZAPISEJ, OBRAZUYUSHCHIH BINARNOE DEREVO. pROIZVODITSYA POISK ZADANNOGO ARGUMENTA~$K$. eSLI EGO NET V TABLICE, TO V PODHODYASHCHEM MESTE V DEREVO VSTAVLYAETSYA NOVYJ UZEL, SODERZHASHCHIJ~$K$. pREDPOLAGAETSYA, CHTO UZLY DEREVA SODERZHAT PO KRAJNEJ MERE SLEDUYUSHCHIE POLYA: $$ \eqalign{ |KEY|(|P|)&=\hbox{KLYUCH, HRANYASHCHIJSYA V UZLE $|NODE|(|P|)$};\cr |LLINK|(|P|)&=\hbox{UKAZATELX NA LEVOE PODDEREVO UZLA~$|NODE|(|P|)$};\cr |RLINK|(|P|)&=\hbox{UKAZATELX NA PRAVOE PODDEREVO UZLA~$|NODE|(|P|)$}.\cr } $$ pUSTYE PODDEREVXYA (VNESHNIE UZLY NA RIS.~10) PREDSTAVLYAYUTSYA PUSTYMI UKAZATELYAMI~$\NULL$. pEREMENNAYA~|ROOT| UKAZYVAET NA KORENX DEREVA. dLYA UDOBSTVA PREDPOLAGAETSYA, CHTO DEREVO NE PUSTO %%505 ($|ROOT|\ne\NULL$), TAK KAK PRI~$|ROOT|=\NULL$ OPERACII STANOVYATSYA TRIVIALXNYMI. \st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|P|\asg |ROOT|$. (uKAZATELX~|P| BUDET PRODVIGATXSYA VNIZ PO DEREVU.) \st[sRAVNENIE.] eSLI~$K<|KEY|(|P|)$, TO PEREJTI NA~\stp{3}; ESLI $K>|KEY|(|P|)$, TO PEREJTI NA~\stp{4}; ESLI $K=|KEY|(|P|)$, POISK ZAVERSHEN UDACHNO. \st[shAG VLEVO.] eSLI~$|LLINK|(|P|)\ne\NULL$, USTANOVITX $|P|\asg|LLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}. v PROTIVNOM SLUCHAE PEREJTI NA~\stp{5}. \st[shAG VPRAVO.] eSLI~$|RLINK|(|P|)\ne\NULL$, USTANOVITX $|P|\asg|RLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}. \st[vSTAVKA V DEREVO.] (pOISK NEUDACHEN; TEPERX MY POMESTIM $K$ V DEREVO.) vYPOLNITX $|Q|\Asg|AVAIL|$; |Q| TEPERX UKAZYVAET NA NOVYJ UZEL. uSTANOVITX $|KEY|(|Q|)\asg K$, $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. (nA SAMOM DELE NUZHNO PROIZVESTI NACHALXNUYU USTANOVKU I DRUGIH POLEJ NOVOGO UZLA.) eSLI $K$ BYLO MENXSHE $|KEY|(|P|)$, USTANOVITX $|LLINK|(|P|)\asg|Q|$; V PROTIVNOM SLUCHAE USTANOVITX $|RLINK|(|P|)\asg|Q|$. (v |TOT MOMENT MY MOGLI BY PRISVOITX $|P|\asg|Q|$ I UDACHNO ZAVERSHITX RABOTU ALGORITMA.) \algend aLGORITM SAM PODSKAZYVAET REALIZACIYU NA YAZYKE~\MIXAL. pREDPOLOZHIM, NAPRIMER, CHTO UZLY DEREVA IMEYUT SLEDUYUSHCHUYU STRUKTURU: \picture{rIS. STR. 505} vOZMOZHNO, DALEE RASPOLOZHENY DOPOLNITELXNYE SLOVA |INFO|. kAK I V GL.~2, |AVAIL| ESTX SPISOK SVOBODNOJ PAMYATI. iTAK, POLUCHAETSYA SLEDUYUSHCHAYA PROGRAMMA DLYA \MIX. \prog t.(pOISK S VSTAVKOJ PO DEREVU.) $|rA|\equiv K$, $|rI1|\equiv|P|$, $|rI2|\equiv Q$. \code LLINK & EQU &2:3 RLINK & EQU &4:5 START & LDA &k & 1 & t1. nACHALXNAYA USTANOVKA. & LD1 &ROOT & 1 & $|P|\asg|ROOT|$. & JMP &2F & 1 4H & LD2 &0,1(RLINK) & C2 & T4. shAG VPRAVO. $|Q|\asg|RLlNK|(|P|)$. & J2Z &5F & C2 & nA T5, ESLI $|Q|=\NULL$. 1H & ENT1 &0,2 & C-l & $|P|\asg|Q|$. 2H & CMPA &1,1 & C & T2. sRAVNENIE. & JG & 4v & C & nA T4, ESLI $K>|KEY|(|P|)$. & JE &SUCCESS & C1 & vYHOD, ESLI $K=|KEY|(|P|)$. & LD2 &0,1 (LLINK) & C1-S & Tz. shAG VLEVO. $|Q|\asg|LLINK|(|P|)$. %%506 & J2NZ & 1B & C1-S & nA T2, ESLI $|Q|\ne\NULL$. 5n & LD2 & AVAIL & 1-S & T5 vSTAVKI V DEREVO. & 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$ BYL MENXSHE $|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 & vYHOD POSLE VSTAVKI. \endcode \progend pERVYE 13~STROK PROGRAMMY OSUSHCHESTVLYAYUT POISK, POSLEDNIE 11~STROK---VSTAVKU. vREMYA RABOTY POISKOVOJ FAZY RAVNO $(7C+C1-3S+4)u$, GDE $$ \eqalign{ C &=\hbox{CHISLO PROIZVEDENNYH SRAVNENIJ};\cr Cl& =\hbox{CHISLO SLUCHAEV, KOGDA $K\le|KEY|(|P|)$};\cr S& =\hbox{ 1 PRI UDACHNOM POISKE I 0 V PROTIVNOM SLUCHAE}.\cr } $$ v SREDNEM IMEEM $C1={1\over2}(C+S)$; DEJSTVITELXNO, $C1+C2=C$ I $C1-S\approx C2$. pO|TOMU VREMYA POISKA PRIMERNO RAVNO $(7.5C-2.5S+4)u$. \picture{rIS 11. pOISK S VSTAVKOJ PO DEREVU.} pROGRAMMY BINARNOGO POISKA, ISPOLXZUYUSHCHIE NEYAVNYE DEREVXYA, RABOTAYUT DOLXSHE! (sR. S PROGRAMMOJ~6.2.1s.) pRODUBLIROVAV KOMANDY, KAK. I V PROGRAMME~6.2.1F, MOZHNO IZBAVITXSYA OT STROKI~08 V PROGRAMME~t, UMENXSHIV TEM SAMYM VREMYA POISKA DO~$(6.5C-2.5S+5)u$. eSLI POISK NEUDACHEN, FAZA VSTAVKI ZAJMET ESHCHE VREMYA $14u$ ILI~$15u$. aLGORITM~t LEGKO PRISPOSOBITX K RABOTE S KLYUCHAMI I ZAPISYAMI \emph{PEREMENNOJ DLINY}. nAPRIMER, ESLI MY RASPREDELYAEM %%507 IMEYUSHCHEESYA V NALICHII PROSTRANSTVO POSLEDOVATELXNO, SPOSOBOM "POSLEDNIM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA" (LIFO), TO LEGKO SMOZHEM SOZDAVATX UZLY RAZLICHNOGO RAZMERA; PERVOE SLOVO DEREVA~(1) MOZHET UKAZYVATX DLINU. tAKOE |FFEKTIVNOE ISPOLXZOVANIE PAMYATI DELAET ALGORITMY TABLIC SIMVOLOV, OSNOVANNYE NA DREVOVIDNOJ STRUKTURE, OSOBENNO PRIVLEKATELXNYMI DLYA RAZRABOTCHIKOV KOMPILYATOROV, ASSEMBLEROV I ZAGRUZCHIKOV. \qsection a KAK NASCHET NAIHUDSHEGO SLUCHAYA? mNOGIE PROGRAMMISTY SNACHALA SKEPTICHESKI VOSPRINIMAYUT ALGORITM~T. eSLI BY KLYUCHI RIS.~10 POSTUPALI V ALFAVITNOM PORYADKE |AQUARIUS|,~\dots, |VIRGO|, a NE V KALENDARNOM |CAPRICORN|,~\dots, |SCORPIO|, TO ALGORITM VYSTROIL BY VYROZHDENNOE DEREVO, KOTOROE, V SUSHCHNOSTI, OPREDELYAET \emph{POSLEDOVATELXNYJ} POISK. (vSE POLYA |LLINK| RAVNYALISX BY ~$\NULL$.) aNALOGICHNO, ESLI KLYUCHI POSTUPAYUT V NEOBYCHNOM PORYADKE: $$ \displaylines{ |AQUARIUS|, |VIRGO|, |ARIES|, |TAURUS|, |CANCER|, |SCORPIO|,\cr |CAPRICORN|, |PISCES|, |GEMINI|, |LIBRA|, |LEO|,\cr } $$ MY POLUCHIM ZIGZAGOOBRAZNOE DEREVO, CHTO NICHUTX NE LUCHSHE. (pOSTROJTE |TO DEREVO!) s DRUGOJ STORONY, DLYA UDACHNOGO POISKA PO DEREVU RIS.~10 TREBUETSYA V SREDNEM VSEGO LISHX $3{2\over11}$~SRAVNENIJ, CHTO NEMNOGIM BOLXSHE OPTIMALXNOGO SREDNEGO CHISLA SRAVNENIJ~3, KOTOROE DOSTIGAETSYA PRI POISKE PO NAILUCHSHEMU IZ VOZMOZHNYH BINARNYH DEREVXEV. dLYA DOSTATOCHNO HOROSHO SBALANSIROVANNOGO DEREVA VREMYA POISKA PRIMERNO, PROPORCIONALXNO~$\log_2N$, A DLYA VYROZHDENNOGO DEREVA---$N$. v UPR.~2.3.4.5-5 DOKAZYVAETSYA, CHTO, ESLI SCHITATX VSE BINARNYE DEREVXYA IZ $N$~UZLOV RAVNOVEROYATNYMI, SREDNEE VREMYA POISKA PRIBLIZITELXNO PROPORCIONALXNO~$\sqrt{N}$. chEGO ZHE NAM OZHIDATX OT ALGORITMA~T? k SCHASTXYU, MOZHNO DOKAZATX, CHTO POISK PO DEREVU TREBUET LISHX OKOLO $2\ln N \approx 1.386\log_2 N$ SRAVNENIJ, ESLI KLYUCHI DOBAVLYAYUTSYA K DEREVU V SLUCHAJNOM PORYADKE; HOROSHO SBALANSIROVANNYE DEREVXYA---PRAVILO, A VYROZHDENNYE---ISKLYUCHENIE. dOKAZATX |TOT FAKT UDIVITELXNO PROSTO. pREDPOLOZHIM, CHTO KAZHDAYA IZ $N!$~PERESTANOVOK $N$~KLYUCHEJ S RAVNOJ VEROYATNOSTXYU ISPOLXZUETSYA DLYA POSTROENIYA DEREVA PUTEM VSTAVOK. chISLO SRAVNENIJ, NUZHNYH DLYA NAHOZHDENIYA KLYUCHA, ROVNO NA EDINICU BOLXSHE CHISLA SRAVNENIJ, POTREBOVAVSHIHSYA PRI VSTAVKE EGO V DEREVO. sLEDOVATELXNO, ESLI CHEREZ $C_N$ OBOZNACHITX SREDNEE CHISLO SRAVNENIJ PRI UDACHNOM POISKE, A CHEREZ $C'_N$---PRI NEUDACHNOM, MY POLUCHIM $$ C_N=1+{C'_0+C'_1+\cdots+C'_{N-1}\over N}. \eqno(2) $$ %%508 nO SOGLASNO SOOTNOSHENIYU MEZHDU DLINAMI VNUTRENNEGO I VNESHNEGO PUTEJ (6.2.1-2) $$ C_N=\left(1+{1\over N}\right)C'_N-1. \eqno(3) $$ pODSTAVLYAYA $C_N$ IZ~(3) V~(2), IMEEM $$ (N+1)C'_N=2N+C'_0+C'_1+\cdots+C'_{N-1}. \eqno(4) $$ iZ |TOGO REKURRENTNOGO SOOTNOSHENIYA $C'_N$ NAHODITSYA LEGKO. vYCHITANIE RAVENSTVA $$ NC'_{N-1}=2(N-1)+C'_0+C'_1+\cdots+C'_{N-2} $$ DAET $$ \eqalign{ (N+1)C'_N-NC'_{N-1}&=2+C'_{N-1},\cr C'_N&=C'_{N-1}+2/(N+1).\cr } $$ tAK KAK $C'_0=0$, TO $$ C'_N=2H_{N+1}-2. \eqno(5) $$ pRIMENIV~(3), POSLE UPROSHCHENIJ POLUCHAEM $$ C_N=2\left(1+{1\over N}\right) H_N-3. \eqno(3) $$ uPRAZHNENIYA 6--8 DAYUT BOLEE DETALXNUYU INFORMACIYU: MOZHNO NAJTI NE TOLXKO SREDNIE ZNACHENIYA~$C_N$ I~$C'_N$, NO I IH VEROYATNOSTNYE RASPREDELENIYA. \section sORTIROVKA VSTAVKOJ V DEREVO. aLGORITM~T PREDNAZNACHALSYA DLYA POISKA, NO EGO MOZHNO PRINYATX ZA OSNOVU ALGORITMA VNUTRENNEJ \emph{SORTIROVKI}, TAK KAK ON YAVLYAETSYA ESTESTVENNYM OBOBSHCHENIEM ALGORITMA VSTAVOK V SPISOK~5.2.1L. uMELO ZAPROGRAMMIROVANNYJ, ON BUDET RABOTATX LISHX NEMNOGO MEDLENNEE LUCHSHIH ALGORITMOV, OBSUZHDAVSHIHSYA V GL.~5. kOGDA POSTROENIE DEREVA ZAVERSHENO, OSTAETSYA SIMMETRICHNO OBOJTI EGO (ALGORITM~2.3.1T)---MY "POSETIM" ZAPISI V OTSORTIROVANNOM PORYADKE. oDNAKO NEOBHODIMO BYTX OSTOROZHNYM. yaSNO, CHTO V SHAGE~T2 PRI $K=|KEY|(|P|)$ NADO DEJSTVOVATX PO-DRUGOMU, TAK KAK MY SORTIRUEM, A NE ISHCHEM. mOZHNO, NAPRIMER, REAGIROVATX NA $K=|KEY|(|P|)$ TAK ZHE, KAK I NA $K>|KEY|(|P|)$; |TO DAST PRAVILXNYJ METOD SORTIROVKI. (zAMETIM, VPROCHEM, CHTO RAVNYE KLYUCHI NE OBYAZATELXNO DOLZHNY NAHODITXSYA V SMEZHNYH UZLAH, LISHX BY ONI PROHODILISX POSLEDOVATELXNO PRI SIMMETRICHNOM OBHODE.) pRI BOLXSHOM KOLICHESTVE POVTORYAYUSHCHIHSYA KLYUCHEJ |TOT METOD PRIVEDET K VESXMA NESBALANSIROVANNOMU DEREVU, I SORTIROVKA ZAMEDLITSYA. dRUGIM METODOM YAVLYAETSYA HRANENIE V KAZHDOM UZLE SPISKA ZAPISEJ S ODNIM I TEM ZHE KLYUCHOM; POTREBUETSYA DOPOLNITELXNOE POLE DLYA SSYLKI, NO |TO USKORIT SORTIROVKU V SLUCHAE, KOGDA VSTRECHAETSYA MNOGO ODINAKOVYH KLYUCHEJ. %%509 tAKIM OBRAZOM, ALGORITM~T, PRIMENYAEMYJ TOLXKO DLYA SORTIROVKI, NEPLOH, NO ESTX I LUCHSHIE. eSLI ZHE NUZHNO SOCHETATX POISK I SORTIROVKU, ISPOLXZOVANIE DREVOVIDNOJ STRUKTURY SLEDUET NASTOYATELXNO REKOMENDOVATX. iNTERESNO OTMETITX TESNUYU SVYAZX MEZHDU ANALIZOM SORTIROVKI VSTAVKOJ V DEREVO I ANALIZOM OBMENNOJ SORTIROVKI S RAZDELENIEM ("BYSTROJ SORTIROVKI"), HOTYA NA PERVYJ VZGLYAD |TI METODY SOVERSHENNO RAZLICHNY. pRI VSTAVKE V PERVONACHALXNO PUSTOE DEREVO $N$~KLYUCHEJ V SREDNEM SOVERSHAETSYA TO ZHE CHISLO SRAVNENIJ, CHTO I V ALGORITME~5.2.2Q (ZA NEBOLXSHIMI ISKLYUCHENIYAMI). nAPRIMER, PRI VSTAVKE V DEREVO KAZHDYJ KLYUCH SRAVNIVAETSYA S $K_1$, A KAZHDYJ KLYUCH, MENXSHIJ $K_1$, SRAVNIVAETSYA S PERVYM KLYUCHOM, MENXSHIM $K_1$, I T. D.; PRI BYSTROJ SORTIROVKE KAZHDYJ KLYUCH SRAVNIVAETSYA S PERVYM RAZDELYAYUSHCHIM |LEMENTOM~$K$, A ZATEM KAZHDYJ KLYUCH, MENXSHIJ $K$, SRAVNIVAETSYA S OPREDELENNYM, MENXSHIM $K$ |LEMENTOM I T.~D. sREDNEE CHISLO SRAVNENIJ V OBOIH SLUCHAYAH RAVNO $NC_N$. (pRAVDA, NA SAMOM DELE, CHTOBY USKORITX VNUTRENNIJ CIKL, ALGORITM~5.2.2Q SOVERSHAET NESKOLXKO BOLXSHE SRAVNENIJ.) \section uDALENIYA. iNOGDA BYVAET NUZHNO ZASTAVITX evm ZABYTX ODIN IZ |LEMENTOV TABLICY. lEGKO UDALITX "LIST" (UZEL, OBA PODDEREVA KOTOROGO PUSTY) ILI UZEL, V KOTOROM $|LLINK|=\NULL$ ILI~$|RLINK|=\NULL$. nO ESLI OBE SSYLKI NE PUSTY, NADO DEJSTVOVATX OSOBYM OBRAZOM---VEDX NELXZYA V ODNOM MESTE HRANITX DVA UKAZATELYA. v KACHESTVE PRIMERA SNOVA RASSMOTRIM RIS.~10. kAK UDALITX |CAPRICORN|? vOT ODNO IZ RESHENIJ: UDALITX \emph{SLEDUYUSHCHIJ} BLIZHAJSHIJ UZEL, LEVAYA SSYLKA KOTOROGO PUSTA, I ZATEM VERNUTX EGO NA MESTO UZLA, KOTORYJ DEJSTVITELXNO TREBUETSYA UDALITX. nAPRIMER, NA RIS.~10 SNACHALA UDALYAETSYA |GEMINI|, ZATEM |CAPRICORN| ZAMENYAETSYA NA |GEMINI|. tAKAYA OPERACIYA SOHRANYAET PORYADOK |LEMENTOV TABLICY. aLGORITM~D REALIZUET |TU IDEYU. \alg D.(uDALENIE IZ DEREVA.) chEREZ |Q| OBOZNACHIM PEREMENNUYU, UKAZYVAYUSHCHUYU NA UZEL BINARNOGO DEREVA POISKA, KOTOROE PREDSTAVLENO KAK V ALGORITME~T. dANNYJ ALGORITM UDALYAET |TOT UZEL, OSTAVLYAYA BINARNOE DEREVO POISKA. (nA SAMOM DELE MY IMEEM ILI $|Q|\equiv|ROOT|$, ILI $|Q|\equiv|LLINK|(|P|)$, ILI $|Q|\equiv|RLINK|(|P|)$ DLYA NEKOTOROGO UZLA~|P|. aLGORITM IZMENYAET V PAMYATI ZNACHENIE~|Q| V SOOTVETSTVII S OSUSHCHESTVL¸NNYM UDALENIEM.) \st[sSYLKA |RLINK| PUSTA?] uSTANOVITX $|T|\asg |Q|$. eSLI $|RLINK|(|T|)=\NULL$, USTANOVITX $|Q|\asg|LLINK|(|T|)$ I PEREJTI NA~\stp{4}. \st [nAJTI PREEMNIKA.] uSTANOVITX $|R|\asg|RLINK|(|T|)$. eSLI $|LLINK|(|R|)=\NULL$, USTANOVITX $|LLINK|(|R|)\asg|LLINK|(|T|)$, $|Q|\asg|R|$ I PEREJTI NA~\stp{4}. %%510 \st[nAJTI PUSTUYU SSYLKU |LLINK|.] uSTANOVITX $|S|\asg|LLINK|(|R|)$. eSLI $|LLINK|(|S|)\ne\NULL$, USTANOVITX $|R|\asg|S|$ I POVTORYATX SHAG DO TEH POR, POKA NE POLUCHIM $|LLINK|(|S|)=\NULL$. (tEPERX |S| UKAZYVAET NA SLEDUYUSHCHIJ POSLE |Q| |LEMENT PRI SIMMETRICHNOM OBHODE.) nAKONEC, USTANOVITX $|LLINK|(|S|)\asg|LLINK|(|T|)$, $|LLINK|(|R|)\asg|RLINK|(|S|)$, $|RLINK|(|S|)\asg|RLINK|(|T|)$, $|Q|\asg|S|$. \st[oSVOBODITX UZEL.] vYPOLNITX $|AVAIL|\Asg|T|$ (T.~E. VERNUTX UZEL V PUL SVOBODNOJ PAMYATI). \algend chITATELX MOZHET ISPYTATX |TOT ALGORITM, UDALYAYA UZLY |AQUARIUS|, |CANCER| I~|CAPRICORN| DEREVA RIS.~10; KAZHDYJ SLUCHAJ IMEET SVOI OSOBENNOSTI. vNIMATELXNYJ CHITATELX, VEROYATNO, ZAMETIL, CHTO OTDELXNO NE VYDELEN SLUCHAJ $|RLINK|(|T|)\ne\NULL$, $|LLINK|(|T|)=\NULL$; MY OBSUDIM |TO NESKOLXKO POZZHE, TAK KAK ALGORITM V TOM VIDE, V KOTOROM ON PREDSTAVLEN ZDESX, OBLADAET VESXMA INTERESNYMI SVOJSTVAMI. pOSKOLXKU V ALGORITME~D NET NIKAKOJ SIMMETRII MEZHDU PRAVYM I LEVYM, TO KAZHETSYA, CHTO DLINNAYA POSLEDOVATELXNOSTX SLUCHAJNYH UDALENIJ I VSTAVOK RAZBALANSIRUET DEREVO, I VYVEDENNYE OCENKI |FFEKTIVNOSTI POTERYAYUT SILU. nO V DEJSTVITELXNOSTI VYROZHDENIYA VOVSE NE PROIZOJDET! \proclaim {tEOREMA n (t.~n.~hIBBARD, 1962)}. pOSLE UDALENIYA POSREDSTVOM ALGORITMA~D SLUCHAJNOGO UZLA SLUCHAJNOGO DEREVA VNOVX POLUCHAETSYA SLUCHAJNOE DEREVO. [nE LYUBYASHCHIE MATEMATIKU, PROPUSTITE, POZHALUJSTA, VPLOTX DO (10)!] tAKAYA FORMULIROVKA TEOREMY, RAZUMEETSYA, VESXMA TUMANNA. oPISHEM SITUACIYU BOLEE TOCHNO. pUSTX $\cJ$---DEREVO IZ $n$~|LEMENTOV, A $P(\cJ)$---VEROYATNOSTX POYAVLENIYA~$\cJ$, ESLI EGO KLYUCHI VSTAVLYAYUTSYA SLUCHAJNYM OBRAZOM S POMOSHCHXYU ALGORITMA~T. nEKOTORYE DEREVXYA POYAVLYAYUTSYA S BOLXSHEJ VEROYATNOSTXYU, CHEM DRUGIE. chEREZ $Q(\cJ)$ OBOZNACHIM VEROYATNOSTX POLUCHENIYA~$\cJ$ POSLE VSTAVKI V SLUCHAJNOM PORYADKE $n+1$~KLYUCHEJ (POSREDSTVOM ALGORITMA~T) I POSLEDUYUSHCHEGO UDALENIYA S POMOSHCHXYU ALGORITMA~D ODNOGO IZ |TIH |LEMENTOV, VYBRANNOGO SLUCHAJNO. pRI VYCHISLENII~$P(\cJ)$ PREDPOLAGAETSYA, CHTO VSE $n~$~PERESTANOVOK KLYUCHEJ RAVNOVEROYATNY; PRI NAHOZHDENII $Q(\cJ)$ MY SCHITAEM, CHTO $(n+1)(n+1)!$~PERESTANOVOK KLYUCHEJ I VYBOROV KLYUCHA DLYA UDALENIYA RAVNOVEROYATNY. tEOREMA UTVERZHDAET, CHTO $P(\cJ)=Q(\cJ)$ DLYA VSEH~$\cJ$. \proof pO USLOVIYU RAVNOVEROYATNY NE DEREVXYA, A PERESTANOVKI, PO|TOMU BUDEM DOKAZYVATX TEOREMU, RASSMATRIVAYA V KACHESTVE SLUCHAJNYH OB®EKTOV \emph{PERESTANOVKI}. oPREDELIM SNACHALA UDALENIE IZ PERESTANOVKI I ZATEM DOKAZHEM, CHTO "POSLE UDALENIYA IZ SLUCHAJNOJ PERESTANOVKI SLUCHAJNOGO |LEMENTA OSTAETSYA SLUCHAJNAYA PERESTANOVKA". %%511 pUSTX $a_1$ $a_2$~\dots $a_{n+1}$---PERESTANOVKA MNOZHESTVA $\{\,1, 2,~\ldots, n+1\,\}$; MY HOTIM OPREDELITX OPERACIYU UDALENIYA |LEMENTA~$a_i$, POLUCHIV V REZULXTATE PERESTANOVKU $b_1$ $b_2$~\dots $b_n$ MNOZHESTVA $\{\,1, 2,~\ldots, n\,\}$. eTA OPERACIYA DOLZHNA BYTX SOGLASOVANA S ALGORITMAMI~t I~D, T.~E. ESLI OTPRAVITXSYA OT DEREVA, POSTROENNOGO POSLEDOVATELXNYMI VSTAVKAMI $a_1$, $a_2$,~\dots, $a_{n+1}$, I UDALITX~$a_i$ S PERENUMERACIEJ KLYUCHEJ CHISLAMI OT~1 DO~$n$, TO POLUCHITSYA DEREVO, KOTOROE MOGLO BYTX POSTROENO POSLEDOVATELXNYMI VSTAVKAMI $b_1$ $b_2$~\dots $b_n$. k SCHASTXYU, OPREDELITX TAKUYU OPERACIYU NETRUDNO. vOZMOZHNY DVA SLUCHAYA: \medskip{ \narrower \noindent{\sl sLUCHAJ 1:\/} $a_i=n+1$ ILI~$a_i+1=a_j$ DLYA NEKOTOROGO $ji$. zAMENYAEM $a_i$ NA~$a_j$, UDALYAEM $a_j$ S PERVONACHALXNOJ POZICII I VYCHITAEM, EDINICU IZ VSEH |LEMENTOV, BOLXSHIH~$a_i$. }\medskip nAPRIMER, RASSMOTRIM PERESTANOVKU 4~6~1~3~5~2. eSLI POMETITX |LEMENT, KOTORYJ NUZHNO UDALITX, ZAKLYUCHIV EGO V KRUZHOK, TO POLUCHITSYA {\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 } $$ } pOSKOLXKU VSEGO MOZHNO SDELATX $(n+1)(n+1)!$ RAZLICHNYH UDALENIJ, TEOREMA BUDET USTANOVLENA, ESLI MY POKAZHEM, CHTO KAZHDUYU PERESTANOVKU MNOZHESTVA $\{\, 1, 2,~\dots, n\,\}$ MOZHNO POLUCHITX KAK REZULXTAT PRIMENENIYA ROVNO $(n+1)^2$~UDALENIJ. rASSMOTRIM PERESTANOVKU $b_1$ $b_2$~\dots $b_n$ MNOZHESTVA $\{\, 1, 2,~\dots, n\,\}$. oPREDELIM $(n+1)^2$~UDALENIJ, NO ODNOMU DLYA KAZHDOJ PARY $i, j$ ($1\le i,j\le n+1$). eSLI $ij$, ISKOMYM UDALENIEM BUDET $$ b'_1\ldots b'_{i-1} \roundit{b_j} b'_i \ldots b'_n, \eqno(8) $$ CHTO SOOTVETSTVUET {\sl SLUCHAYU~1.\/} %% 512 nAKONEC, PRI $i=j$ IMEEM DRUGIE UDALENIYA: \picture{rIS. STR. 512} KOTORYE TOZHE OPISYVAYUTSYA {\sl SLUCHAEM~1.\/} pOLOZHIV $n=4$, RASSMOTRIM V KACHESTVE PRIMERA 25~UDALENIJ, PRIVODYASHCHIH K PERESTANOVKE 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 }} pOMECHENNYJ |LEMENT VSEGDA STOIT V $i\hbox{-J}$ POZICII, I DLYA FIKSIROVANNOGO~$i$ MY POSTROILI $(n+1)$ RAZLICHNYH UDALENIJ, PO ODNOMU DLYA KAZHDOGO~$j$; SLEDOVATELXNO, DLYA KAZHDOJ PERESTANOVKI $b_1$ $b_2$~\dots $b_n$ POSTROENO $(n+1)^2$ RAZLICHNYH UDALENIJ. dLYA ZAVERSHENIYA DOKAZATELXSTVA ZAMETIM, CHTO VSEGO IMEETSYA $(n+1)^2!$~UDALENIJ. \proofend dOKAZATELXSTVO TEOREMY~H NE TOLXKO OPISYVAET SITUACIYU POSLE UDALENIJ, NO I POMOGAET PRI ANALIZE SREDNEGO VREMENI UDALENIYA. uPRAZHNENIE~12 POKAZYVAET, CHTO PRI UDALENII SLUCHAJNOGO |LEMENTA IZ SLUCHAJNOJ TABLICY SHAG~D2 VYPOLNYAETSYA V SREDNEM CHUTX REZHE, CHEM V POLOVINE SLUCHAEV. rASSMOTRIM TEPERX, SKOLXKO RAZ PROHODITSYA CIKL V SHAGE~D3. pREDPOLOZHIM, CHTO UDALYAETSYA UZEL, RASPOLOZHENNYJ NA UROVNE~$l$, A \emph{VNESHNIJ} UZEL, NEPOSREDSTVENNO SLEDUYUSHCHIJ ZA NIM PRI SIMMETRICHNOM OBHODE, NAHODITSYA NA UROVNE~$k$. nAPRIMER, PRI UDALENII UZLA |CAPRICORN| (RIS.~10) IMEEM $l=0$ I~$k=3$, TAK KAK UZEL~\leaf{4} RASPOLOZHEN NA UROVNE~3. eSLI $k=l+1$, TO $|RLINK|(|T|)=\NULL$ V SHAGE~D1; ESLI $k>l+1$, MY BUDEM PRISVAIVATX $|S|\asg |LLINK|(|R|)$ (SHAG~D3) ROVNO $k-l-2$~RAZ. sREDNEE ZNACHENIE~$l$ RAVNO $$ (\hbox{DLINA VNUTRENNEGO PUTI})/N; $$ SREDNEE ZNACHENIE~$k$ RAVNO $$ (\hbox{DLINA VNESHNEGO PUTI})/N -(\hbox{RASSTOYANIE DO SAMOGO LEVOGO VNESHNEGO UZLA})/N. $$ rASSTOYANIE DO SAMOGO LEVOGO VNESHNEGO UZLA RAVNO KOLICHESTVU TAKIH~$a_i$ IZ VSTAVLYAEMOJ POSLEDOVATELXNOSTI, CHTO $a_i0$ VZVESHENNAYA DLINA VNESHNEGO PUTI NE MENXSHE $$ Q+\sum_{0\le i l_1>\ldots>l_m$ I DEJSTVITELXNYE POSTOYANNYE$0=x_0