\input style \chapnotrue\chapno=5\subchno=4\subsubchno=2 TAK KAK V SHAGAH~A3 I~A5 VYPOLNYAETSYA TOLXKO "POLOVINA PROHODA", T.~E.\ S|KONOMLENO OKOLO 25\% VREMENI. v DEJSTVITELXNOSTI MOZHNO DAZHE POLNOSTXYU USTRANITX KOPIROVANIE, ESLI NACHATX S $F_n$~OTREZKOV NA LENTE~T1 I S $F_{n-1}$~OTREZKOV NA~T2, GDE~$F_n$ I~$F_{n-1}$---POSLEDOVATELXNYE CHISLA fIBONACHCHI. rASSMOTRIM, NAPRIMER, SLUCHAJ~$n=7$, $S=F_n+F_{n-1}=13+8=21$: {\def\cm{\hfil$-$\hfil}\def\hd#1{\multispan{3}\hfil#1\hfil}\let\f=\hfil\ctable{ #\bskip& #&#&#\bskip&\bskip#&#&#\bskip&\bskip#&#&#&#\hfil\cr &\hd{sODERZHIMOE~t1} & \hd{sODERZHIMOE~t2} & \hd{sODERZHIMOE~T3} & pRIMECHANIYA \cr fAZA~1.& 1, 1, 1, 1, &1, 1, 1, 1, &1, 1, 1, 1, 1& 1, 1, &1, 1, 1, 1, & 1, 1 & & & & nACHALXNOE RASPREDELENIE\cr fAZA~2.& & &1, 1, 1, 1, 1& &\cm & & 2, 2, 2, & 2,2, & 2,2,2 & sLIYANIE 8~OTREZKOV NA~T3\cr fAZA~3.& &\cm & & &3, 3, 3, 3, & 3 & & & 2,2,2 & sLIYANIE 5~OTREZKOV NA~T3\cr fAZA~4.& &\f 5, 5, 5 & & &\f 3, & 3 & & \cm & & sLIYANIE 3~OTREZKOV NA~T1\cr fAZA~5.& &\f 5 & & &\cm & & &\f 8,8 & & sLIYANIE 2~OTREZKOV NA~T3\cr fAZA~6.& &\cm & & &\f 13 \f & & &\f 8 & & sLIYANIE 1~OTREZKA NA~T2\cr fAZA~7.& &\f 21 \f & & &\cm & & &\cm & & sLIYANIE 1~OTREZKA NA~T1\cr }}% zDESX "2, 2, 2, 2, 2, 2, 2, 2", NAPRIMER, OBOZNACHAET VOSEMX OTREZKOV OTNOSITELXNOJ DLINY~2, ESLI SCHITATX OTNOSITELXNUYU DLINU KAZHDOGO NACHALXNOGO OTREZKA RAVNOJ~1. vSYUDU V |TOJ TABLICE CHISLA fIBONACHCHI! pOLNYJ PROHOD PO DANNYM OSUSHCHESTVLYAYUT TOLXKO FAZY~1 I~7; FAZA~2 OBRABATYVAET LISHX $16/21$~OBSHCHEGO CHISLA NACHALXNYH OTREZKOV, FAZA~3---LISHX~$15/21$ I~T. D.; TAKIM OBRAZOM, SUMMARNOE CHISLO "PROHODOV" RAVNO~$(21+16+15+15+16+13+21)/21=5{4\over7}$, ESLI PREDPOLOZHITX, CHTO NACHALXNYE OTREZKI IMEYUT PRIMERNO RAVNUYU DLINU. dLYA SRAVNENIYA ZAMETIM, CHTO RASSMOTRENNAYA VYSHE DVUHFAZNAYA PROCEDURA ZATRATILA BY 8~PROHODOV NA SORTIROVKU |TIH ZHE NACHALXNYH OTREZKOV. mY UVIDIM, CHTO V OBSHCHEM SLUCHAE |TA SHEMA fIBONACHCHI TREBUET PRIBLIZITELXNO $1.04\log_2 S+0.99$~PROHODOV, CHTO DELAET EE SRAVNIMOJ S \emph{CHETYREHLENTOCHNYM} SBALANSIROVANNYM SLIYANIEM, HOTYA ONA ISPOLXZUET TOLXKO TRI LENTY. eTU IDEYU MOZHNO OBOBSHCHITX NA SLUCHAJ $T$~LENT PRI LYUBOM~$T\ge 3$, ISPOLXZUYA $(T-1)\hbox{-PUTEVOE}$~SLIYANIE. mY UVIDIM, NAPRIMER, CHTO V SLUCHAE CHETYREH LENT TREBUETSYA TOLXKO OKOLO $0.703\log_2 S+0.96$~PROHODOV PO DANNYM. oBOBSHCHENNAYA SHEMA ISPOLXZUET OBOBSHCHENNYE CHISLA fIBONACHCHI. rASSMOTRIM SLEDUYUSHCHIJ PRIMER S SHESTXYU LENTAMI: \ctable{ #\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&\hfil$#$&\hfil$\hbox{}#$\cr & & & & & & & \hbox{chISLO OBRABATYVAEMYH NACHALXNYH OTREZKOV}\cr & T1 & T2 & T3 & T4 & T5 & T6 & \cr fAZA~1.& 1^{31}& 1^{30}& 1^{28}& 1^{24}& 1^{16}& - & 31+30+28+24+16 =&129\cr fAZA~2.& 1^{15}& 1^{14}& 1^{12}& 1^8 & - & 5^{16}& 16\times 5 =& 80\cr fAZA~3.& 1^7 & 1^6 & 1^4 & - & 9^8 & 5^8 & 8\times 9 =& 72\cr fAZA~4.& 1^3 & 1^2 & - & 17^4 & 9^4 & 5^4 & 4\times 17 =& 68\cr fAZA~5.& 1^1 & - & 33^2 & 17^2 & 9^2 & 5^2 & 2\times 33 =& 66\cr fAZA~6.& - & 65^1 & 33^1 & 17^1 & 9^1 & 5^1 & 1\times 65 =& 65\cr fAZA~7.& 129^1 & - & - & - & - & - & 1\times 129=&129\cr } %%320 zDESX $1^{31}$~OBOZNACHAET 31~OTREZOK OTNOSITELXNOJ DLINY~1 I~T.D.; VEZDE ISPOLXZUETSYA PYATIPUTEVOE SLIYANIE. eTA OBSHCHAYA SHEMA BYLA RAZRABOTANA r.~l.~gILST|DOM [Proc.\ AFIPS Eastern Jt.\ Computer Conf., 18 (1960), 143--148], KOTORYJ NAZVAL EE MNOGOFAZNYM SLIYANIEM. sLUCHAJ TREH LENT BYL RANEE OTKRYT b.~k.~bETCEM [NEOPUBLIKOVANNAYA ZAMETKA, Minneapolis-Honeywell Regulator Co.\ (1956)]. chTOBY ZASTAVITX MNOGOFAZNOE SLIYANIE RABOTATX, KAK V PREDYDUSHCHEM PRIMERE, NEOBHODIMO POSLE KAZHDOJ FAZY IMETX "TOCHNOE FIBONACHCHIEVO RASPREDELENIE" OTREZKOV PO LENTAM. chITAYA PRIVEDENNUYU VYSHE TABLICU SNIZU VVERH, MOZHNO ZAMETITX, CHTO PERVYE SEMX TOCHNYH FIBONACHCHIEVYH RASPREDELENIJ PRI~$T=6$ SUTX $\set{1, 0, 0, 0, 0}$, $\set{1, 1, 1, 1, 1}$, $\set{2, 2, 2, 2, 1}$, $\set{4, 4, 4, 3, 2}$, $\set{8, 8, 7, 6, 4}$, $\set{16, 15, 14, 12, 8}$ I~$\set{31, 30, 28, 24, 16}$. tEPERX PERED NAMI STOYAT SLEDUYUSHCHIE VAZHNYE VOPROSY: \enumerate \li kAKOE PRAVILO SKRYTO ZA |TIMI TOCHNYMI FIBONACHCHIEVYMI RASPREDELENIYAMI? \li chTO DELATX, ESLI~$S$ NE SOOTVETSTVUET TOCHNOMU FIBONACHCHIEVOMU RASPREDELENIYU? \li kAK POSTROITX NACHALXNYJ PROHOD RASPREDELENIYA, CHTOBY ON POROZHDAL NUZHNOE RASPOLOZHENIE OTREZKOV NA LENTAH? \li sKOLXKO "PROHODOV" PO DANNYM POTREBUET $T\hbox{-LENTOCHNOE}$ MNOGOFAZNOE SLIYANIE (KAK FUNKCIYA OT~$S$---CHISLA NACHALXNYH OTREZKOV)? \enumend mY OBSUDIM |TI CHETYRE VOPROSA PO OCHEREDI, PRI |TOM SNACHALA DADIM "PROSTYE OTVETY", A ZATEM ZAJMEMSYA BOLEE GLUBOKIM ANALIZOM. tOCHNYE FIBONACHCHIEVY RASPREDELENIYA MOZHNO POLUCHITX, "PROKRUCHIVAYA" RASSMOTRENNUYU SHEMU V OBRATNUYU STORONU, CIKLICHESKI PERESTAVLYAYA SODERZHIMOE LENT. nAPRIMER, PRI~$T=6$ IMEEM SLEDUYUSHCHEE RASPREDELENIE OTREZKOV: $$ \vcenter{\halign{ \hfil # \hfil &\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr uROVENX & T1 & T2 & T3 & T4& T5 & \hbox{sUMMA} & \hbox{lENTA S OKONCHATELXNYM REZULXTATOM}\cr 0 & 1 & 0& 0& 0 & 0& 1& T1\cr 1 & 1 & 1& 1& 1 & 1& 5& T6\cr 2 & 2 & 2& 2& 2 & 1& 9& T5\cr 3 & 4 & 4& 4& 3 & 2& 17& T4\cr 4 & 8 & 8& 7& 6 & 4& 33& T3\cr 5 & 16 & 15& 14& 12 & 8& 65& T2\cr 6 & 31 & 30& 28& 24 & 16& 129& T1\cr 7 & 61 & 59& 55& 47 & 31& 253& T6\cr 8 & 120 & 116& 108& 92 & 61& 497& T5\cr \multispan{8}\dotfill\cr n & a_n & b_n & c_n & d_n & e_n & t_n & T(k) \cr n+1 & a_n+b_n & a_n+c_n & a_n+d_n & a_n+e_n & a_n & t_n+4a_n & T(k-1)\cr \multispan{8}\dotfill\cr }} \eqno(1) $$ %%321 (pOSLE NACHALXNOGO RASPREDELENIYA LENTA~T6 VSEGDA BUDET PUSTOJ.) iZ PRAVILA PEREHODA OT UROVNYA~$n$ K UROVNYU~$n+1$ YASNO, CHTO USLOVIYA $$ a_n \ge b_n \ge c_n \ge d_n \ge e_n \eqno (2) $$ VYPOLNYAYUTSYA NA LYUBOM UROVNE. v SAMOM DELE, LEGKO VIDETX IZ~(1), CHTO $$ \eqalign{ e_n &= a_{n-1},\cr d_n &= a_{n-1}+e_{n-1}=a_{n-1}+a_{n-2},\cr c_n &= a_{n-1}+d_{n-1}=a_{n-1}+a_{n-2}+a_{n-3},\cr b_n &= a_{n-1}+c_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4},\cr a_n &= a_{n-1}+b_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5},\cr } \eqno (3) $$ GDE~$a_0=1$ I GDE MY POLAGAEM~$a_n=0$ PRI~$n=-1$, $-2$, $-3$, $-4$. \def\Fib#1,#2.{F^{(#1)}_{#2}} \dfn{chISLA fIBONACHCHI $p\hbox{-GO}$~PORYADKA~$\Fib p, n.$} OPREDELYAYUTSYA PRAVILAMI $$ \eqalign{ \Fib p, n. &=\Fib p, n-1.+\Fib p, n-2.+\cdots+\Fib p, n-p. \rem{PRI $n\ge p$;}\cr \Fib p, n. &=0 \rem{PRI $0\le n \le p-2$;}\cr \Fib p, p-1. &=1.\cr } \eqno (4) $$ dRUGIMI SLOVAMI, MY NACHINAEM S $p-1$~NULEJ, ZATEM PISHEM~1, A KAZHDOE SLEDUYUSHCHEE CHISLO YAVLYAETSYA SUMMOJ $p$~PREDYDUSHCHIH CHISEL. pRI~$p=2$ |TO OBYCHNAYA POSLEDOVATELXNOSTX fIBONACHCHI; DLYA BOLXSHIH ZNACHENIJ~$p$ |TU POSLEDOVATELXNOSTX VPERVYE IZUCHIL, PO-VIDIMOMU, v.~shLEGELX V [{\sl El Progreso Matematico,\/} {\bf 4} (1894), 173--174]. shLEGELX VYVEL PROIZVODYASHCHUYU FUNKCIYU $$ \sum_{n\ge 0}\Fib p, n. z^n= {z^{p-1}\over 1-z-z^2-\cdots-z^p}= {z^{p-1}-z^p \over 1-2z+z^{p+1}}. \eqno (5) $$ fORMULA~(3) POKAZYVAET, CHTO CHISLO OTREZKOV NA~T1 V PROCESSE SHESTILENTOCHNOGO MNOGOFAZNOGO SLIYANIYA YAVLYAETSYA CHISLOM fIBONACHCHI PYATOGO PORYADKA~$a_n=\Fib 5, n+4.$. v OBSHCHEM SLUCHAE, ESLI POLOZHITX~$P=T-1$, RASPREDELENIYA V MNOGOFAZNOM SLIYANII DLYA $T$~LENT BUDUT ANALOGICHNYM OBRAZOM SOOTVETSTVOVATX CHISLAM fIBONACHCHI $P\hbox{-GO}$~PORYADKA. v TOCHNOM RASPREDELENII $n\hbox{-GO}$~UROVNYA NA $k\hbox{-J}$~LENTE BUDET $$ \Fib P, n+P-2. + \Fib P, n+P-3. +\cdots+ \Fib P, n+k-2. $$ %% 322 NACHALXNYH OTREZKOV DLYA~$1\le k \le P$, A OBSHCHEE KOLICHESTVO NACHALXNYH OTREZKOV NA VSEH LENTAH BUDET, SLEDOVATELXNO, RAVNO $$ t_n=P\Fib P, n+P-2. + (P-1)\Fib P, n+P-3. + \cdots + \Fib P, n-1. . \eqno(6) $$ eTO RESHAET VOPROS O "TOCHNOM FIBONACHCHIEVOM RASPREDELENII". nO CHTO MY DOLZHNY DELATX, ESLI~$S$ NE RAVNO V TOCHNOSTI~$t_n$ NI PRI KAKOM~$n$? kAK PERVONACHALXNO POMESTITX OTREZKI NA LENTY? eSLI~$S$ NE YAVLYAETSYA TOCHNYM CHISLOM fIBONACHCHI (A CHISEL fIBONACHCHI NE TAK UZH MNOGO), TO MOZHNO DEJSTVOVATX, KAK V SBALANSIROVANNOM $P\hbox{-PUTEVOM}$ SLIYANII, DOBAVLYAYA "FIKTIVNYE \picture{rIS.~68. sORTIROVKA MNOGOFAZNYM SLIYANIEM.} OTREZKI"; PO|TOMU MOZHNO SCHITATX, CHTO~$S$, V KONCE KONCOV, BUDET TOCHNYM. eSTX NESKOLXKO SPOSOBOV DOBAVLENIYA FIKTIVNYH OTREZKOV; MY ESHCHE NE ZNAEM, KAK |TO SDELATX "NAILUCHSHIM" SPOSOBOM. v PERVUYU OCHEREDX RASSMOTRIM METOD RASPREDELENIYA OTREZKOV I PRIPISYVANIYA FIKTIVNYH OTREZKOV, KOTORYJ HOTYA I NE SAMYJ OPTIMALXNYJ, NO ZATO DOSTATOCHNO PROSTOJ I, PO-VIDIMOMU, LUCHSHE VSEH DRUGIH METODOV TAKOJ ZHE STEPENI SLOZHNOSTI. \alg D.(sORTIROVKA MNOGOFAZNYM SLIYANIEM S ISPOLXZOVANIEM "GORIZONTALXNOGO" RASPREDELENIYA.) eTOT ALGORITM BERET NACHALXNYE OTREZKI I RASPREDELYAET IH ODIN ZA DRUGIM PO LENTAM, POKA ZAPAS NACHALXNYH OTREZKOV NE ISCHERPAETSYA. zATEM ON OPREDELYAET, KAK NADO SLIVATX LENTY, ISPOLXZUYA $P\hbox{-PUTEVOE}$ SLIYANIE, V PREDPOLOZHENII, CHTO IMEYUTSYA $T=P+1\ge 3$~LENTOPROTYAZHNYH USTROJSTV. lENTU~$T$ MOZHNO ISPOLXZOVATX DLYA HRANENIYA VVODA, TAK KAK NA NEE NE ZAPISYVAETSYA NI ODNOGO NACHALXNOGO OTREZKA. v PAMYATI HRANYATSYA SLEDUYUSHCHIE TABLICY: %%323 \descrtable{ $|A|[j]$, $1 \le j \le T$: & tOCHNOE FIBONACHCHIEVOE RASPREDELENIE, K KOTOROMU MY STREMIMSYA. \cr $|D|[j]$, $1 \le j \le T$: & chISLO FIKTIVNYH OTREZKOV, KOTORYE SCHITAYUTSYA PRISUTSTVUYUSHCHIMI V NACHALE LENTY NA LOGICHESKOM USTROJSTVE S NOMEROM~$j$.\cr $|TAPE|[j]$, $1 \le j \le T$: & nOMER FIZICHESKOGO LENTOPROTYAZHNOGO USTROJSTVA, SOOTVETSTVUYUSHCHEGO LOGICHESKOMU USTROJSTVU S NOMEROM~$j$.\cr } (oKAZALOSX, CHTO UDOBNO RABOTATX S "NOMERAMI LOGICHESKIH LENTOPROTYAZHNYH USTROJSTV", SOOTVETSTVIE KOTORYH FIZICHESKIM USTROJSTVAM MENYAETSYA V PROCESSE VYPOLNENIYA ALGORITMA.) \st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$|A|[j]\asg |D|[j]\asg 1$ I~$|TAPE|[j]\asg j$ PRI~$1\le j < T$. uSTANOVITX~$|A|[T]\asg |D|[T]\asg 0$ I~$|TAPE|[T]\asg T$. zATEM USTANOVITX~$l\asg 1$, $j\asg 1$. \st[vVOD NA LENTU~$j$.] zAPISATX ODIN OTREZOK NA LENTU~$j$ I UMENXSHITX~$|D|[j]$ NA~1. zATEM, ESLI VVOD ISCHERPAN, PEREMOTATX VSE LENTY I PEREJTI K SHAGU~\stp{5}. \st[pRODVIZHENIE~$j$.] eSLI~$|D|[j]<|D|[j+1]$, TO UVELICHITX~$j$ NA~1 I VERNUTXSYA K SHAGU~\stp{2}. v PROTIVNOM SLUCHAE, ESLI~$|D|[j]=0$, PEREJTI K SHAGU~\stp{4}, A ESLI~$|D|[j]\ne 0$, USTANOVITX~$j\asg 1$ I VERNUTXSYA K SHAGU~\stp{2}. \st[pODNYATXSYA NA ODIN UROVENX.] uSTANOVITX~$l\asg l+1$, $a\asg |A|[1]$, ZATEM DLYA~$j=1$, 2,~\dots, $P$ (IMENNO V |TOM PORYADKE) USTANOVITX~$|D|[j]\asg a+|A|[j+1]-|A|[j]$ I~$|A|[j]\asg a+|A|[j+1]$. (sM.~(1). oTMETIM, CHTO~$|A|[P+1]$ VSEGDA~0. v |TOM MESTE BUDEM IMETX~$|D|[1]>|D|[2]>\ldots>|D|[T]$.) tEPERX USTANOVITX~$j\asg 1$ I VERNUTXSYA K SHAGU~\stp{2}. \st[sLIYANIE.] eSLI~$l=0$, TO SORTIROVKA ZAVERSHENA, REZULXTAT NAHODITSYA NA~$|TAPE|[1]$. v PROTIVNOM SLUCHAE SLIVATX OTREZKI S LENT~$|TAPE|[1]$,~\dots, $|TAPE|[P]$ NA~$|TAPE|[T]$ DO TEH POR, POKA~$|TAPE|[P]$ NE STANET PUSTOJ I~$|D|[P]$ NE OBRATITSYA V~$0$. pROCESS SLIYANIYA DLYA KAZHDOGO SLIVAEMOGO OTREZKA DOLZHEN PROTEKATX SLEDUYUSHCHIM OBRAZOM. eSLI~$|D|[j]>0$ DLYA VSEH~$j$, $1\le j \le P$, TO UVELICHITX~$|D|[T]$ NA~1 I UMENXSHITX KAZHDOE~$|D|[j]$ NA~1 DLYA~$1\le j \le P$; V PROTIVNOM SLUCHAE SLIVATX PO ODNOMU OTREZKU S KAZHDOJ LENTY~$|TAPE|[j]$, TAKOJ, CHTO~$|D|[j]=0$, I UMENXSHITX~$|D|[j]$ NA~1 DLYA OSTALXNYH~$j$. (tAKIM OBRAZOM, SCHITAETSYA, CHTO FIKTIVNYE OTREZKI NAHODYATSYA V \emph{NACHALE} LENTY, A NE V KONCE.) \st[oPUSTITXSYA NA ODIN UROVENX.] uSTANOVITX~$l\asg l-1$. pEREMOTATX LENTY~$|TAPE|[P]$ I~$|TAPE|[T]$. (v DEJSTVITELXNOSTI PEREMOTKA~$|TAPE|[P]$ MOGLA BYTX NACHATA NA SHAGE~\stp{5} POSLE VVODA S NEE POSLEDNEGO BLOKA.) zATEM USTANOVITX~$(|TAPE|[1], %%324 |TAPE|[2],~\ldots, |TAPE|[T])\asg (|TAPE|[T], |TAPE|[1],~\ldots, |TAPE|[T-1])$, $(|D|[1], |D|[2],~\ldots, |D|[T])\asg(|D|[T], |D|[1],~\ldots, |D|[T-1])$ I VERNUTXSYA K SHAGU~\stp{5}. \algend pRAVILO RASPREDELENIYA, KOTOROE TAK LAKONICHNO SFORMULIROVANO V SHAGE~D3 |TOGO ALGORITMA, STREMITSYA PO VOZMOZHNOSTI URAVNYATX CHISLA FIKTIVNYH OTREZKOV NA KAZHDOJ LENTE. rISUNOK~69 ILLYUSTRIRUET PORYADOK RASPREDELENIYA, KOGDA MY PEREHODIM OT UROVNYA~4 (33~OTREZKA) K UROVNYU~5 (65~OTREZKOV) V SORTIROVKE S SHESTXYU LENTAMI; ESLI BYLO BY, SKAZHEM, TOLXKO 53~NACHALXNYH \picture{ rIS.~69. pORYADOK, V KOTOROM OTREZKI S~34-GO PO~65-J RASPREDELYAYUTSYA NA LENTY PRI PEREHODE S UROVNYA~4 NA UROVENX~5. (sM.~TABLICU TOCHNYH RASPREDELENIJ NA STR.~320.) zASHTRIHOVANNYE OBLASTI SOOTVETSTVUYUT PERVYM 33~OTREZKAM, KOTORYE BYLI RASPREDELENY K MOMENTU DOSTIZHENIYA UROVNYA~4. } OTREZKA, TO VSE OTREZKI S NOMERAMI~54 I VYSHE RASSMATRIVALISX BY KAK FIKTIVNYE. (nA SAMOM DELE OTREZKI ZAPISYVAYUTSYA V KONEC LENTY, NO UDOBNEE SCHITATX, CHTO ONI ZAPISYVAYUTSYA V NACHALO, TAK KAK PREDPOLAGAETSYA, CHTO FIKTIVNYE OTREZKI NAHODYATSYA V NACHALE LENTY.) mY UZHE RASSMOTRELI PERVYE TRI IZ POSTAVLENNYH VYSHE VOPROSOV, OSTALOSX VYYASNITX CHISLO "PROHODOV" PO DANNYM. sRAVNIVAYA NASH SHESTILENTOCHNYJ PRIMER S TABLICEJ~(1), MY VIDIM, CHTO SUMMARNOE KOLICHESTVO OBRABOTANNYH NACHALXNYH OTREZKOV PRI~$S=t_6$ ESTX~$a_5t_1+a_4t_2+a_3t_3+a_2t_4+a_1t_5+a_0t_6$, ESLI ISKLYUCHITX NACHALXNYJ PROHOD RASPREDELENIYA. v UPR.~4 VYVODYATSYA %%325 PROIZVODYASHCHIE FUNKCII $$ \eqalign{ a(z)&=\sum_{n\ge0}a_nz^n={1\over 1-z-z^2-z^3-z^4-z^5},\cr t(z)&=\sum_{n\ge1} t_nz^n={5z+4z^2+3z^3+2z^4+z^5\over 1-z-z^2-z^3-z^4-z^5}.\cr } \eqno(7) $$ oTSYUDA SLEDUET, CHTO V OBSHCHEM SLUCHAE CHISLO OBRABATYVAEMYH NACHALXNYH OTREZKOV PRI~$S=t_n$ RAVNO KO|FFICIENTU PRI~$z^n$ V PROIZVEDENII~$a(z)\cdot t(z)$ PLYUS~$t_n$ (|TO DAET NACHALXNYJ PROHOD RASPREDELENIYA). tEPERX MY MOZHEM VYCHISLITX ASIMPTOTICHESKOE POVEDENIE MNOGOFAZNOGO SLIYANIYA, KAK POKAZANO V UPR.~5--7, I POLUCHAEM REZULXTATY, PRIVEDENNYE V TABL.~1. v TABL.~1 "OTNOSHENIE ROSTA" ESTX PREDEL~$\lim_{n\to\infty} t_{n+1}t_n$, POKAZYVAYUSHCHIJ, VO SKOLXKO PRIBLIZITELXNO RAZ VOZRASTAET CHISLO \htable{tABLICA~1}% {aPPROKSIMACIYA POVEDENIYA SORTIROVKI MNOGOFAZNYM SLIYANIEM}% {\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \hbox{lENTY} & \hbox{fAZY} & \hbox{pROHODY} & \hbox{pROHODY/FAZY,} & \hbox{oTNOSHENIE}\cr & & & & \hbox{V PROCENTAH ROSTA}\cr \noalign{\hrule} 3 & 2.078 \ln S+0.678 & 1.504 \ln S+0.992 & 72 & 1.6180340\cr 4 & 1.641 \ln S+0.364 & 1.015 \ln S+0.965 & 62 & 1.8392868\cr 5 & 1.524 \ln S+0.078 & 0.863 \ln S+0.921 & 57 & 1.9275620\cr 6 & 1.479 \ln S-0.185 & 0.795 \ln S+0.864 & 54 & 1.9659482\cr 7 & 1.460 \ln S-0.424 & 0.762 \ln S+0.797 & 52 & 1.9835826\cr 8 & 1.451 \ln S-0.642 & 0.744 \ln S+0.723 & 51 & 1.9919642\cr 9 & 1.447 \ln S-0.838 & 0.734 \ln S+0.646 & 51 & 1.9960312\cr 10 & 1.445 \ln S-1.017 & 0.728 \ln S+0.568 & 50 & 1.9980295\cr 20 & 1.443 \ln S-2.170 & 0.721 \ln S-0.030 & 50 & 1.9999981\cr \noalign{\hrule} } OTREZKOV NA KAZHDOM UROVNE. "pROHODY" OBOZNACHAYUT SREDNEE KOLICHESTVO OBRABOTOK KAZHDOJ ZAPISI, A IMENNO~$(1/S)$, UMNOZHENNOE NA OBSHCHEE CHISLO NACHALXNYH OTREZKOV, OBRABATYVAEMYH V TECHENIE FAZ RASPREDELENIYA I SLIYANIYA. uSTANOVLENNYE CHISLA PROHODOV I FAZ SPRAVEDLIVY V KAZHDOM SLUCHAE S TOCHNOSTXYU DO~$O(S^{-\varepsilon})$ PRI NEKOTOROM~$\varepsilon>0$ DLYA TOCHNOGO RASPREDELENIYA PRI~$S\to\infty$. nA RIS.~70 IZOBRAZHENY V VIDE FUNKCIJ OT~$S$ SREDNIE KOLICHESTVA SLIYANIJ KAZHDOJ ZAPISI PRI ISPOLXZOVANII ALGORITMA~D V SLUCHAE NETOCHNYH CHISEL. zAMETIM, CHTO PRI ISPOLXZOVANII TREH LENT KAK RAZ POSLE TOCHNYH RASPREDELENIJ POYAVLYAYUTSYA "PIKI" OTNOSITELXNOJ NE|FFEKTIVNOSTI, NO |TO YAVLENIE V ZNACHITELXNOJ STEPENI ISCHEZAET PRI CHETYREH ILI BOLXSHEM CHISLE LENT. iSPOLXZOVANIE %%326 VOSXMI ILI BOLEE LENT DAET SRAVNITELXNO MALOE ULUCHSHENIE PO SRAVNENIYU S SHESTXYU ILI SEMXYU LENTAMI. \section *bOLEE DETALXNOE RASSMOTRENIE. v SBALANSIROVANNOM SLIYANII, TREBUYUSHCHEM $k$~PROHODOV, KAZHDAYA ZAPISX OBRABATYVAETSYA V HODE SORTIROVKI ROVNO $k$~RAZ. nO MNOGOFAZNAYA PROCEDURA NE YAVLYAETSYA TAKOJ BESPRISTRASTNOJ: NEKOTORYE ZAPISI MOGUT OBRABATYVATXSYA \picture{rIS.~70. eFFEKTIVNOSTX MNOGOFAZNOGO SLIYANIYA, ISPOLXZUYUSHCHEGO ALGORITM~D.} MNOGO BOLXSHEE CHISLO RAZ, CHEM DRUGIE, I MY MOZHEM UVELICHITX SKOROSTX, ESLI USLOVIMSYA POMESHCHATX FIKTIVNYE OTREZKI V CHASTO OBRABATYVAEMYE POZICII. pO |TOJ PRICHINE IZUCHIM BOLEE PODROBNO MNOGOFAZNOE RASPREDELENIE. vMESTO TOGO CHTOBY INTERESOVATXSYA TOLXKO CHISLOM OTREZKOV NA KAZHDOJ LENTE, KAK V~(1), PRIPISHEM KAZHDOMU OTREZKU EGO \emph{CHISLO SLIYANIJ}---SKOLXKO RAZ ON OBRABATYVAETSYA V TECHENIE VSEGO PROCESSA SORTIROVKI. vMESTO~(1) POLUCHIM SLEDUYUSHCHUYU TABLICU: %%327 $$ \matrix{ \hbox{uROVENX} & T1 & T2 & T3 & T4 & T5 \cr 0 & 0 & - & - & - & - \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 21 & 21 & 21 & 21 & 2\cr 3 & 3221 & 3221 & 3221 & 322 & 32 \cr 4 & 43323221 & 43323221 & 4332322 & 433232 & 4332 \cr 5 & 5443433243323221 & 544343324332322 & 54434332433232 & 544343324332 & 54434332 \cr \multispan{6}{\dotfill}\cr n & A_n & B_n & C_n & D_n & E_n \cr n+1& (A_n+1)B_n & (A_n+1)C_n & (A_n+1)D_n & (A_n+1)E_n & A_n+1\cr \multispan{6}{\dotfill}\cr } \eqno(8) $$ zDESX $A_n$~ESTX CEPOCHKA IZ $a_n$~ZNACHENIJ, PREDSTAVLYAYUSHCHIH CHISLA SLIYANIJ KAZHDOGO OTREZKA NA~$T1$, ESLI MY NACHINAEM S RASPREDELENIYA $n\hbox{-GO}$~UROVNYA; $B_n$~ESTX SOOTVETSTVUYUSHCHAYA CEPOCHKA DLYA~T2 I~T.~D.\ oBOZNACHENIE~"$(A_n+1)B_n$" CHITAETSYA: "$A_n$, VSE ZNACHENIYA KOTOROJ UVELICHENY NA~1, A ZA NEYU~$B_n$". rISUNOK~71~(A), NA KOTOROM "SNIZU VVERH" IZOBRAZHENY~$A_5$, $B_5$, $C_5$, $D_5$, $E_5$, DEMONSTRIRUET, KAKIM OBRAZOM CHISLA SLIYANIJ DLYA KAZHDOGO OTREZKA POYAVLYAYUTSYA NA LENTE; ZAMETIM, CHTO OTREZOK V NACHALE LYUBOJ LENTY BUDET OBRABATYVATXSYA 5~RAZ, V TO VREMYA KAK OTREZOK V KONCE~T1 BUDET OBRABATYVATXSYA LISHX ODNAZHDY. \picture{rIS.~71. aNALIZ MNOGOFAZNOGO RASPREDELENIYA PYATOGO UROVNYA NA SHESTI LENTAH: (a)---CHISLA SLIYANIJ; (b)---OPTIMALXNYJ PORYADOK RASPREDELENIYA.} eTA "DISKRIMINACIYA" PRI MNOGOFAZNOM SLIYANII PRIVODIT K TOMU, CHTO FIKTIVNYE OTREZKI LUCHSHE POMESHCHATX V NACHALO LENTY, A NE V KONEC. nA RIS.~71~(b) PREDSTAVLEN OPTIMALXNYJ PORYADOK RASPREDELENIYA OTREZKOV DLYA SLUCHAYA PYATIUROVNEVOGO MNOGOFAZNOGO SLIYANIYA; KAZHDYJ NOVYJ OTREZOK POMESHCHAETSYA V POZICIYU S NAIMENXSHIM IZ OSTAVSHIHSYA CHISLOM SLIYANIJ. zAMETIM, CHTO ALGORITM~D %%328 (RIS.~69) NESKOLXKO HUZHE, TAK KAK ON ZAPOLNYAET NEKOTORYE POZICII~"4" DO TOGO, KAK ZAPOLNENY VSE POZICII~"3". rEKURRENTNYE SOOTNOSHENIYA~(8) POKAZYVAYUT, CHTO VSE~$B_n$, $C_n$, $D_n$, $E_n$ YAVLYAYUTSYA NACHALXNYMI PODCEPOCHKAMI~$A_n$. v DEJSTVITELXNOSTI, ISPOLXZUYA~(8), MOZHNO VYVESTI FORMULY $$ \eqalign{ E_n&=(A_{n-1})+1,\cr D_n&=(A_{n-1}A_{n-2})+1,\cr C_n&=(A_{n-1}A_{n-2}A_{n-3})+1,\cr B_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4})+1,\cr A_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4}A_{n-5})+1,\cr } \eqno(9) $$ OBOBSHCHAYUSHCHIE SOOTNOSHENIYA~(3), KOTORYE IMEYUT DELO TOLXKO S DLINAMI |TIH CEPOCHEK. kROME TOGO, IZ PRAVIL, OPREDELYAYUSHCHIH CEPOCHKI~$A$, SLEDUET, CHTO STRUKTURA V NACHALE KAZHDOGO UROVNYA, V SUSHCHNOSTI, ODNA I TA ZHE; IMEEM $$ A_n=n-Q_n, \eqno(10) $$ GDE $Q_n$~ESTX CEPOCHKA IZ $a_n$~ZNACHENIJ, OPREDELYAEMAYA ZAKONOM $$ \displaynarrow{ Q_n=Q_{n-1}(Q_{n-2}+1)(Q_{n-3}+2)(Q_{n-4}+3)(Q_{n-5}+4) \rem{PRI $n\ge 1$},\cr Q_0=\hbox{'0'}; Q_n=\hbox{(PUSTO)} \rem{PRI $n<0$.}\cr } \eqno(11) $$ tAK KAK~$Q_n$ NACHINAETSYA S~$Q_{n-1}$, TO MOZHNO RASSMOTRETX \emph{BESKONECHNUYU} CEPOCHKU~$Q_\infty$, PERVYE $a_n$~|LEMENTOV KOTOROJ SOVPADAYUT S~$Q_n$; |TA CEPOCHKA, PO SUSHCHESTVU, OPISYVAET VSE CHISLA SLIYANIJ V MNOGOFAZNOM RASPREDELENII. v SLUCHAE SHESTI LENT IMEEM $$ Q_\infty=011212231223233412232334233434412232334233434452334344534454512232\ldots\,. \eqno (12) $$ v UPR.~11 SODERZHITSYA INTERESNAYA INTERPRETACIYA |TOJ CEPOCHKI. pRI USLOVII CHTO~$A_n$ ESTX CEPOCHKA~$m_1m_2\ldots m_{a_n}$, OBOZNACHIM CHEREZ~$A_n(x)=x^{m_1}+x^{m_2}+\cdots+x^{m_{a_n}}$ SOOTVETSTVUYUSHCHUYU PROIZVODYASHCHUYU FUNKCIYU, OPISYVAYUSHCHUYU, SKOLXKO RAZ POYAVLYAETSYA KAZHDOE CHISLO SLIYANIJ; ANALOGICHNO VVEDEM~$B_n(x)$, $C_n(x)$, $D_n(x)$, $E_n(x)$. nAPRIMER, $A_4(x)=x^4+x^3+x^3+x^2+x^3+x^2+x^2+x=x^4+3x^3+3x^2+x$. v SILU SOOTNOSHENIJ~(9) IMEEM PRI~$n\ge1$ $$ \eqalign{ E_n(x)&=x(A_{n-1}(x)),\cr D_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)),\cr C_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)),\cr B_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)),\cr A_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)+A_{n-5}(x)),\cr } \eqno(13) $$ %%329 GDE~$A_0(x)=1$ I~$A_n(x)=0$ PRI~$n=-1$, $-2$, $-3$, $-4$. sLEDOVATELXNO, $$ \sum_{n\ge 0} A_n(x)z^n={1\over 1-x(z+z^2+z^3+z^4+z^5)}= \sum_{k\ge 0} x^k(z+z^2+z^3+z^4+z^5)^k. \eqno(14) $$ rASSMATRIVAYA OTREZKI NA VSEH LENTAH, POLOZHIM $$ T_n(x)=A_n(x)+B_n(x)+C_n(x)+D_n(x)+E_n(x), \qquad n\ge 1; \eqno (15) $$ IZ~(13) NEMEDLENNO POLUCHAEM $$ T_n(x)=5A_{n-1}(x)+4A_{n-2}(x)+3A_{n-3}(x)+2A_{n-4}(x)+A_{n-5}(x), $$ A ZNACHIT, I $$ \sum_{n\ge 1} T_n(x)z^n= {x(5z+4z^2+3z^3+2z^4+z^5)\over 1-x(z+z^2+z^3+z^4+z^5)}. \eqno(16) $$ sOOTNOSHENIE~(16) POKAZYVAET, CHTO LEGKO VYCHISLITX KO|FFICIENTY~$T_n(x)$: $$ \matrix{ & z &z^2 & z^3 & z^4 & z^5 & z^6 & z^7 & z^8 & z^9 & z^{10} & z^{11} & z^{12} & z^{13} & z^{14} \cr x & 5 & 4 & 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr x^2 & 0 & 5 & 9 & 12 & 14 & 15 & 10 & 6 & 3 & 1 & 0 & 0 & 0 & 0 \cr x^3 & 0 & 0 & 5 & 14 & 26 & 40 & 55 & 60 & 57 & 48 & 35 & 20 & 10 & 4 \cr x^4 & 0 & 0 & 0 & 5 & 19 & 45 & 85 & 140 & 195 & 238 & 260 & 255 & 220 & 170\cr x^5 & 0 & 0 & 0 & 0 & 5 & 24 & 69 & 154 & 294 & 484 & 703 & 918 & 1088 & 1168 \cr } \eqno(17) $$ sTOLBCY |TOJ TABLICY DAYUT~$T_n(x)$; NAPRIMER, $T_4(x)=2x+12x^2+14x^3+5x^4$. kAZHDYJ |LEMENT |TOJ TABLICY (KROME |LEMENTOV PERVOJ STROKI) YAVLYAETSYA SUMMOJ PYATI |LEMENTOV, RASPOLOZHENNYH V PREDYDUSHCHEJ STROKE NEPOSREDSTVENNO LEVEE NEGO. chISLO OTREZKOV V TOCHNOM RASPREDELENII $n\hbox{-GO}$~UROVNYA RAVNO~$T_n(1)$, A OBSHCHEE KOLICHESTVO OBRABATYVAEMYH OTREZKOV V PROCESSE IH SLIYANIYA RAVNO PROIZVODNOJ~$T'_n(1)$. dALEE, $$ \sum_{n\ge 1} T'_n(x)z^n= {5z+4z^2+3z^3+2z^4+z^5\over (1-x(z+z^2+z^3+z^4+z^5))^2}; \eqno(18) $$ POLAGAYA~$x=1$ V~(16) I~(18), POLUCHAEM, CHTO CHISLO SLIYANIJ DLYA TOCHNOGO RASPREDELENIYA P-GO UROVNYA ESTX KO|FFICIENT PRI~$z^n$ V~$a(z)t(z)$ [SR.~(7)]. eTO SOGLASUETSYA S NASHIMI PREDYDUSHCHIMI RASSUZHDENIYAMI. fUNKCII~$T_n(x)$ MOZHNO ISPOLXZOVATX DLYA OPREDELENIYA SOVERSHAEMOJ RABOTY, KOGDA FIKTIVNYE OTREZKI DOBAVLYAYUTSYA OPTIMALXNYM OBRAZOM. pUSTX~$\sum_n (m)$ ESTX SUMMA NAIMENXSHIH $m$~CHISEL SLIYANIJ V RASPREDELENII $n\hbox{-GO}$~UROVNYA. pOSMOTREV NA STOLBCY~(17), %%330 MY BEZ TRUDA VYCHISLIM |TI SUMMY~$\sum_n(m)$: {\let\i=\infty $$\vcenter{\halign{ $#$\bskip&&\bskip\hfill$#$\bskip\cr \span m=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \cr n=1 & 1 & 2 & 3 & 4 & 5 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i& \i & \i & \i & \i & \i & \i \cr n=2 & 1 & 2 & 3 & 4 & B & 8 & 10 & 12 & 14 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i \cr n=3 & 1 & 2 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 24 & 27 & 30 &33 & 36 & \i & \i & \i & \i \cr n=4 & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr n=5 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr n=6 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 33 & 36 & 38 & 42 & 45 & 48 \cr n=7 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 23 & 26 & 29 & 32 & 35 & 38 & 41 & 44 & 47 & 50 & 53 \cr }} \eqno(19) $$}% nAPRIMER, ESLI MY HOTIM OTSORTIROVATX 17~OTREZKOV, ISPOLXZUYA RASPREDELENIE 3-GO~UROVNYA, TO OBSHCHEE KOLICHESTVO OPERACIJ ESTX~$\sum_3 (17)=36$, NO ESLI ISPOLXZOVATX RASPREDELENIE~4-GO ILI 5-GO~UROVNYA, TO OBSHCHEE KOLICHESTVO OPERACIJ V PROCESSE SLIYANIYA BUDET TOLXKO~$\sum_4(17)=\sum_5 (17)=35$. vYGODNEE ISPOLXZOVATX UROVENX~4, HOTYA CHISLO~17 SOOTVETSTVUET TOCHNOMU RASPREDELENIYU 3-GO~UROVNYA! v SAMOM DELE, PO. MERE VOZRASTANIYA~$S$ OPTIMALXNYJ NOMER UROVNYA OKAZYVAETSYA ZNACHITELXNO BOLXSHE, CHEM ISPOLXZUEMYJ V ALGORITME~D. uPRAZHNENIE~14 POKAZYVAET, CHTO SUSHCHESTVUET NEUBYVAYUSHCHAYA POSLEDOVATELXNOSTX CHISEL~$M_n$, TAKAYA, CHTO UROVENX~$n$ OPTIMALEN DLYA~$M_n\le S < M_{n+1}$, NO NE DLYA~$S\ge M_{n+1}$. v SLUCHAE SHESTI LENT TOLXKO CHTO VYCHISLENNAYA TABLICA~$\sum_n (m)$ DAET $$ M_0=0,\quad M_1=2,\quad M_2=6,\quad M_3=10,\quad M_4=14. $$ vYSHE MY IMELI DELO TOLXKO SO SLUCHAEM SHESTI LENT, ODNAKO YASNO, CHTO TE ZHE IDEI PRIMENIMY K MNOGOFAZNOJ SORTIROVKE S~$T$~LENTAMI DLYA LYUBOGO~$T\ge3$; PROSTO V SOOTVETSTVUYUSHCHIH MESTAH NADO ZAMENITX~5 NA~$P=T-1$. v TABL.~2 IZOBRAZHENY POSLEDOVATELXNOSTI~$M_n$, POLUCHENNYE DLYA RAZLICHNYH ZNACHENIJ~$T$. tABLICA~3 I RIS.~72 DAYUT PREDSTAVLENIE OB OBSHCHEM KOLICHESTVE OBRABATYVAEMYH NACHALXNYH OTREZKOV POSLE VYPOLNENIYA OPTIMALXNOGO RASPREDELENIYA FIKTIVNYH OTREZKOV. (fORMULY VNIZU TABL.~3 SLEDUET PRINIMATX S OSTOROZHNOSTXYU, TAK KAK |TO PRIBLIZHENIE PO METODU NAIMENXSHIH KVADRATOV NA OBLASTI~$1\le S \le 5000$ ($1\le S \le 10\, 000$ PRI~$T=3$), CHTO PRIVODIT K NEKOTOROMU OTKLONENIYU, POSKOLXKU DANNAYA OBLASTX ZNACHENIJ~$S$ NE YAVLYAETSYA ODINAKOVO PODHODYASHCHEJ DLYA VSEH~$T$. pRI~$S\to\infty$ CHISLO OBRABATYVAEMYH NACHALXNYH OTREZKOV POSLE OPTIMALXNOGO MNOGOFAZNOGO RASPREDELENIYA ASIMPTOTICHESKI RAVNO~$S\log_p S$, NO SHODIMOSTX K |TOMU ASIMPTOTICHESKOMU PREDELU KRAJNE MEDLENNAYA.) pRI POMOSHCHI TABL.~4 MOZHNO SRAVNITX METOD RASPREDELENIYA ALGORITMA~D S REZULXTATAMI OPTIMALXNOGO RASPREDELENIYA, PRIVEDENNYMI V TABL.~3. yaSNO, CHTO ALGORITM~D NE OCHENX BLIZOK K OPTIMALXNOMU PRI BOLXSHIH~$S$ I~$T$; ODNAKO NEPONYATNO, MOZHNO LI POSTUPITX V |TIH SLUCHAYAH SUSHCHESTVENNO LUCHSHE ALGORITMA~D, NE PRIBEGAYA K ZNACHITELXNYM USLOZHNENIYAM, OSOBENNO ESLI MY NE %%331 ZNAEM~$S$ ZARANEE. k SCHASTXYU, ZABOTITXSYA O BOLXSHIH~$S$ PRIHODITSYA DOVOLXNO REDKO (SM.~P.~5.4.6), TAK CHTO ALGORITM~D NA PRAKTIKE NE TAK UZH PLOH, NA SAMOM DELE---DAZHE VESXMA NEPLOH. mATEMATICHESKI MNOGOFAZNAYA SORTIROVKA VPERVYE BYLA PROANALIZIROVANA u.~k.~kARTEROM [rGOS.\ IFIP Congress (1962), 62--66]. \picture{rIS.~72. eFFEKTIVNOSTX MNOGOFAZNOGO SLIYANIYA S OPTIMALXNYM NACHALXNYM RASPREDELENIEM (SR.~S~RIS.~70).} mNOGIE IZ PRIVEDENNYH REZULXTATOV OTNOSITELXNO OPTIMALXNOGO RAZMESHCHENIYA FIKTIVNYH OTREZKOV PRINADLEZHAT b.~s|KMANU I~t.~sINGLERU [A vector model for merge sort analisis, NEOPUBLIKOVANNYJ DOKLAD, PREDSTAVLENNYJ NA SIMPOZIUM~ACM PO SORTIROVKE (NOYABRX 1962), STR.~21]. pOZDNEE s|KMAN PREDLOZHIL GORIZONTALXNYJ METOD RASPREDELENIYA, ISPOLXZUEMYJ V ALGORITME~D; dONALXD shELL [{\sl CACM,\/} {\bf 14} (1971), 713--719; {\bf 15} (1972), 28], NEZAVISIMO RAZVIV |TU TEORIYU, UKAZAL NA SOOTNOSHENIE~(10) I PODROBNO IZUCHIL NESKOLXKO RAZLICHNYH ALGORITMOV RASPREDELENIYA. dALXNEJSHIE POLEZNYE USOVERSHENSTVOVANIYA I UPROSHCHENIYA BYLI POLUCHENY dEREKOM~e.~z|JVOM [{\sl JACM,\/} BUDET OPUBLIKOVANO]. %%332 \htable{tABLICA 2}% {chISLO OTREZKOV, PRI KOTOROM DANNYJ UROVENX OPTIMALEN} { \hfill$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\bskip$#$\hfill\cr \hbox{uROVENX}& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & M_1 \cr 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & M_2 \cr 3 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & M_3 \cr 4 & 6 & 10 & 14 & 14 & 17 & 20 & 23 & 26 & M_4 \cr 5 & 9 & 18 & 23 & 29 & 20 & 24 & 28 & 32 & M_5 \cr 6 & 14 & 32 & 35 & 43 & 53 & 27 & 32 & 37 & M_6 \cr 7 & 22 & 55 & 76 & 61 & 73 & 88 & 35 & 41 & M_7 \cr 8 & 35 & 96 &109 &194 & 98 &115 &136 & 44 & M_8 \cr 9 & 56 &173 &244 &216 &283 &148 &171 &199 & M_9 \cr 10 & 90 &280 &359 &269 &386 &168 &213 &243 & M_{10}\cr 11 &145 &535 &456 &779 &481 &640 &240 &295 & M_{11}\cr 12 &234 &820 &1197&1034&555 &792 &1002&330 & M_{12}\cr 13 &378 &1635&1563&1249&1996&922 &1228&1499& M_{13}\cr 14 &611 &2401&4034&3910&2486&1017&1432&1818& M_{14}\cr 15 &988 &4959&5379&4970&2901&4397&1598&2116& M_{15}\cr 16 &1598&7029&6456&5841&10578&5251&1713&2374&M_{16}\cr 17 &2574&14953&18561&19409&13097&5979&8683&2576&M_{17}\cr 18 &3955&20583&22876&23918&15336&6499&10069&2709&M_{18}\cr 19 &6528&44899&64189&27557&17029&30164&11259&15787& M_{19}\cr \noalign{\hrule} } {\def\m#1#2{\matrix{\hfill #1\cr\hfill #2\cr}} \htable{tABLICA~3}% {chISLO NACHALXNYH OTREZKOV, OBRABATYVAEMYH PRI OPTIMALXNOM \nl MNOGOFAZNOM SLIYANII}% {\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr S& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 10& 36& 24& 19& 17& 15& 14& 13& 12\cr 20& 90& 60& 49& 44& 38& 36& 34& 33\cr 50& 294& 194& 158& 135& 128& 121& 113& 104\cr 100& 702& 454& 362& 325& 285& 271& 263& 254\cr 1000& 10371& 6680& 5430& 4672& 4347& 3872& 3739& 3632\cr 5000& 63578& 41286& 32905& 28620& 26426& 23880& 23114& 22073\cr \multispan{2} \hfil$ \displaystyle S\left\{\matrix{ \hfill (1.51\cr \hfill +(-.11\cr }\right. $ & \m{0.951}{+.14} & \m{0.761}{+.16} & \m{0.656}{+.19} & \m{0.589}{+.21} & \m{0.548}{+.20} & \m{0.539}{+.02} & \multispan{2} \hfill\bskip$\displaystyle\vcenter{\halign{\hfil$#$&$\hbox{}#$\hfil\cr 0.488)&\cdot S \ln S \cr +.18)&\cdot S \cr }}$ \cr \noalign{\hrule} }} pROIZVODYASHCHAYA FUNKCIYA~(16) BYLA VPERVYE ISSLEDOVANA u.~bURZHEM [rGOS. IFIP Congress (1971), I, 454--459]. \qsection a KAK OBSTOIT DELO S VREMENEM PEREMOTKI? dO SIH POR MY ISPOLXZOVALI "OBRABATYVAEMYE NACHALXNYE OTREZKI" KAK EDINSTVENNUYU MERU |FFEKTIVNOSTI DLYA SRAVNENIYA STRATEGIJ LENTOCHNOGO SLIYANIYA. nO POSLE KAZHDOJ IZ FAZ~2--6 V PRIMERAH V NACHALE |TOGO PUNKTA evm DOLZHNA OZHIDATX PEREMOTKI DVUH LENT; KAK PREDYDUSHCHAYA VYVODNAYA LENTA, TAK I NOVAYA TEKUSHCHAYA VYVODNAYA %%333 \htable{tABLICA~4}% {chISLO NACHALXNYH OTREZKOV, OBRABATYVAEMYH PRI STANDARTNOM \nl MNOGOFAZNOM SLIYANII}% {\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr S& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 10& 36& 24& 19& 17& 15& 14& 13& 12\cr 20& 90& 62& 49& 44& 41& 37& 34& 33\cr 50& 294& 194& 167& 143& 134& 131& 120& 114\cr 100& 714& 459& 393& 339& 319& 312& 292& 277\cr 1000& 10730& 6920& 5774& 5370& 4913& 4716& 4597& 4552\cr 5000& 64740& 43210& 36497& 32781& 31442& 29533& 28817& 28080\cr \noalign{\hrule} } LENTA DOLZHNY BYTX PEREMOTANY V NACHALO, PREZHDE CHEM SMOZHET VYPOLNYATXSYA SLEDUYUSHCHAYA FAZA. eTO MOZHET VYZVATX SUSHCHESTVENNUYU ZADERZHKU, TAK KAK V OBSHCHEM SLUCHAE PREDYDUSHCHAYA VYVODNAYA LENTA SODERZHIT ZNACHITELXNYJ PROCENT SORTIRUEMYH ZAPISEJ (SM. STOLBEC "PROHODY/FAZY" V TABL.~1). dOSADNO, KOGDA evm PROSTAIVAET VO VREMYA OPERACIJ PEREMOTKI, TOGDA KAK MOZHNO BYLO BY, ISPOLXZUYA INUYU SHEMU SLIYANIYA, VYPOLNITX POLEZNUYU RABOTU S OSTALXNYMI LENTAMI. eTU ZADACHU RESHAET PROSTAYA MODIFIKACIYA MNOGOFAZNOJ PROCEDURY, HOTYA ONA TREBUET NE MENEE PYATI LENT [SM.~DISSERTACIYU i.~sEZARI (Univ.~of~Paris (1968), 25--27), GDE |TA IDEYA PRIPISYVAETSYA dZH.~k|JRONU]. kAZHDAYA FAZA SHEMY k|JRONA SLIVAET OTREZKI S $(T-3)$~LENT NA NEKOTORUYU DRUGUYU LENTU, V TO VREMYA KAK OSTAYUSHCHIESYA DVE LENTY PEREMATYVAYUTSYA. rASSMOTRIM, NAPRIMER, SLUCHAJ SHESTI LENT I 49~NACHALXNYH OTREZKOV. v SLEDUYUSHCHEJ TABLICE BUKVOJ~$R$ POMECHENY LENTY, PEREMATYVAYUSHCHIESYA VO VREMYA DANNOJ FAZY; PREDPOLAGAETSYA, CHTO $T5$~SODERZHIT PERVONACHALXNYE OTREZKI: \ctable{ \hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \omit\hfill fAZA\hfill & T1 & T2 & T3 & T4 & T5 & T6 & \omit\hfill vREMYA ZAPISI \hfill & \omit\hfill vREMYA PEREMOTKI \hfill \cr 1&1^{11}&1^{17}&1^{13}& 1^8& - & (R) & 49 & 17\cr 2& (R)& 1^9& 1^5& -& R & 3^8 & 8\times 3=24& 49-17=32\cr 3& 1^6& 1^4& - & R& 3^5 & R & 5\times 3=15& \max(8,24)\cr 4& 1^2& -& R & 5^4& R & 3^4 & 4\times 5=20& \max(13,15)\cr 5& - & R& 7^2& R& 3^3 & 3^2 & 2\times 7=14& \max(17,20)\cr 6& R & 11^2& R& 5^2& 3^1 & - & 2\times 11=22& \max(11,14)\cr 7& 15^1& R& 7^1& 5^1& - & R & 1\times 15=15& \max(22,24)\cr 8& R & 11^1& 7^0& -& R & 23^1 & 1\times 23=23& \max(15,16)\cr 9& 15^1 & 11^1& -& R& 33^0& R & 0\times 33= 0& \max(20,23)\cr 10&(15^0)& -& R&49^1& (R) & (23^0)& 1\times 49=49& 14\cr } zDESX VSE PEREMOTKI, PO SUSHCHESTVU, SOVMESHCHENY; ZA ISKLYUCHENIEM FAZY~9 ("FIKTIVNAYA FAZA", KOTORAYA PODGOTAVLIVAET OKONCHATELXNOE SLIYANIE) I PEREMOTKI POSLE NACHALXNOJ FAZY RASPREDELENIYA (KOGDA PEREMATYVAYUTSYA VSE LENTY). eSLI $t$~ESTX VREMYA, NEOBHODIMOE %%334 DLYA SLIYANIYA TAKOGO KOLICHESTVA ZAPISEJ, KAKOE SODERZHITSYA V ODNOM NACHALXNOM OTREZKE, A $r$---VREMYA PEREMOTKI NA ODIN NACHALXNYJ OTREZOK, TO |TOT PROCESS TRATIT OKOLO~$182t+40r$ PLYUS VREMYA NACHALXNOGO RASPREDELENIYA I ZAVERSHAYUSHCHEJ PEREMOTKI. sOOTVETSTVUYUSHCHIE VYRAZHENIYA DLYA STANDARTNOGO MNOGOFAZNOGO METODA, ISPOLXZUYUSHCHEGO ALGORITM~D, ESTX~$140t+104r$, CHTO NESKOLXKO HUZHE, ESLI~$r={3\over 4}t$, I NESKOLXKO LUCHSHE, ESLI~$r={1\over2}t$. vSE SKAZANNOE O STANDARTNOM MNOGOFAZNOM METODE PRILOZHIMO K MNOGOFAZNOMU METODU k|JRONA; NAPRIMER, POSLEDOVATELXNOSTX~$a_n$ TEPERX UDOVLETVORYAET REKURRENTNOMU SOOTNOSHENIYU $$ a_n=a_{n-2}+a_{n-3}+a_{n-4} \eqno (20) $$ VMESTO~(3). chITATELYU BUDET POLEZNO PROANALIZIROVATX |TOT METOD TAKIM ZHE OBRAZOM, KAK MY ANALIZIROVALI STANDARTNYJ MNOGOFAZNYJ, TAK KAK |TO ULUCHSHIT PONIMANIE OBOIH METODOV (SM., NAPRIMER, UPR.~19 I~20). v TABL.~5 SVEDENY FAKTY O MNOGOFAZNOM METODE k|JRONA, ANALOGICHNYE FAKTAM OB OBYCHNOM MNOGOFAZNOM METODE, PRIVEDENNYM V TABL.~1. zAMETIM, CHTO. NA SAMOM DELE PRI VOSXMI I BOLEE. LENTAH METOD k|JRONA STANOVITSYA \emph{LUCHSHE} MNOGOFAZNOGO KAK PO CHISLU OBRABATYVAEMYH OTREZKOV, TAK I PO VREMENI PEREMOTKI, NESMOTRYA NA TO CHTO ON VYPOLNYAET $(T-3)\hbox{-PUTEVOE}$ SLIYANIE VMESTO $(T-1)\hbox{-PUTEVOGO}$! eTO MOZHET KAZATXSYA, PARADOKSALXNYM, POKA MY NE POJMEM, CHTO \emph{VYSOKIJ PORYADOK SLIYANIYA NE OBYAZATELXNO OZNACHAET |FFEKTIVNUYU SORTIROVKU.} v KACHESTVE KRAJNEGO RASSMOTRIM SLUCHAJ, KOGDA NA LENTU~T1 POMESHCHAETSYA 1~OTREZOK I $n$~OTREZKOV---NA~T2, T3, \htable{tABLICA 5}% {pRIBLIZITELXNOE POVEDENIE MNOGOFAZNOGO SLIYANIYA k|JRONA}% { \hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \hbox{lENTY} & \hbox{fAZY} & \hbox{pROHODY} & \hbox{pROHODY/FAZY,} & \hbox{oTNOSHENIE}\cr & & & \hbox{V PROCENTAH} & \hbox{ROSTA} \cr \noalign{\hrule} 5& 3.566 \ln S +0.158 & 1.463 \ln S + 1.016 & 41 & 1.3247180\cr 6& 2.616 \ln S -0.166 & 0.951 \ln S + 1.014 & 36 & 1.4655712\cr 7& 2.337 \ln S -0.472 & 0.781 \ln S + 1.001 & 33 & 1.5341577\cr 8& 2.216 \ln S -0.762 & 0.699 \ln S + 0.980 & 32 & 1.5701473\cr 9& 2.156 \ln S -1.034 & 0.654 \ln S + 0.954 & 30 & 1.5900054\cr 10& 2.124 \ln S -1.290 & 0.626 \ln S + 0.922 & 29 & 1.6013473\cr 20& 2.078 \ln S -3.093 & 0.575 \ln S + 0.524 & 28 & 1.6179086\cr \noalign{\hrule} } T4, T5; ESLI MY BUDEM POOCHEREDNO VYPOLNYATX SLIYANIYA NA~T6 I~T1, POKA T2, T3, T4, T5 NE STANUT PUSTYMI, TO VREMYA OBRABOTKI BUDET RAVNO $(2n^2+3n)$~DLINAM NACHALXNYH OTREZKOV, T.~E., PO SUSHCHESTVU, PROPORCIONALXNO~$S^2$, A NE~$S\log S$, HOTYA VSE VREMYA PROIZVODITSYA PYATIPUTEVOE SLIYANIE. %%335 \section rASSHCHEPLENIE LENT. eFFEKTIVNOE SOVMESHCHENIE VREMENI PEREMOTKI YAVLYAETSYA PROBLEMOJ, VOZNIKAYUSHCHEJ VO MNOGIH PRILOZHENIYAH, A NE TOLXKO V SORTIROVKE; SUSHCHESTVUET OBSHCHIJ PODHOD, KOTORYJ CHASTO MOZHET BYTX ISPOLXZOVAN. rASSMOTRIM ITERATIVNYJ PROCESS, KOTORYJ ISPOLXZUET LENTY SLEDUYUSHCHIM OBRAZOM: \ctable{ #\bskip\hfill&&\bskip#\bskip\hfill\cr &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill\cr fAZA~1& vYVOD~1 & \omit\hfill $-$ \hfill \cr & pEREMOTKA & \omit\hfill $-$ \hfill \cr fAZA~2& vVOD~1 & vYVOD~2\cr & pEREMOTKA & pEREMOTKA\cr fAZA~3& vYVOD~3 & vVOD~2\cr & pEREMOTKA & pEREMOTKA\cr fAZA~4& vVOD~3 & vYVOD~4\cr & pEREMOTKA & pEREMOTKA\cr } I T. D., GDE "VYVOD~$k$" OZNACHAET ZAPISX V $k$-J VYVODNOJ FAJL, A "VVOD~$k$" OZNACHAET EGO CHTENIE. mOZHNO USTRANITX VREMYA PEREMOTKI, ESLI ISPOLXZOVATX TRI LENTY, KAK BYLO PREDLOZHENO k.~vEJSERTOM [{\sl CACM,\/} {\bf 5} (1962), 102]: \ctable{ #\bskip\hfill&&\bskip#\bskip\hfill\cr &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill& \omit\hfill T3 \hfill\cr fAZA~1 & vYVOD~1.1 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr & vYVOD~1.2 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr & pEREMOTKA & vYVOD~1.3 & \omit\hfill $-$ \hfill\cr fAZA~2 & vVOD~1.1 & vYVOD~2.1 & \omit\hfill $-$ \hfill\cr & vVOD~1.2 & pEREMOTKA & vYVOD~2.2\cr & pEREMOTKA & vVOD~1.3 & vYVOD~2.3\cr fAZA~3 & vYVOD~3.1 & vVOD~2.1 & pEREMOTKA\cr & vYVOD~3.2 & pEREMOTKA & vVOD~2.2\cr & pEREMOTKA & vYVOD~3.3 & vVOD~2.3\cr fAZA~4 & vVOD~3.1 & vYVOD~4.1 & pEREMOTKA\cr & vVOD~3.2 & pEREMOTKA & vYVOD~4.2\cr & pEREMOTKA & vVOD~3.3 & vYVOD~4.3\cr } I~T.~D. zDESX "VYVOD~$k.j$" OZNACHAET ZAPISX $j\hbox{-J}$~TRETI $k\hbox{-GO}$~VYVODNOGO FAJLA, A "VVOD~$k.j$" OZNACHAET EE CHTENIE. v KONCE KONCOV BUDET ISKLYUCHENO VSE VREMYA PEREMOTKI, ESLI PEREMOTKA PO KRAJNEJ MERE VDVOE BYSTREE CHTENIYA/ZAPISI. pODOBNAYA PROCEDURA, V KOTOROJ VYVOD V KAZHDOJ FAZE RAZDELYAETSYA MEZHDU LENTAMI, NAZYVAETSYA "RASSHCHEPLENIEM LENT". l.~mAK-aLLESTER [{\sl CACM\/}, {\bf 7} (1964), 158--159] POKAZAL, CHTO RASSHCHEPLENIE LENT PRIVODIT K |FFEKTIVNOMU METODU SOVMESHCHENIYA VREMENI PEREMOTKI V MNOGOFAZNOM SLIYANII. eGO METOD MOZHNO ISPOLXZOVATX S CHETYRXMYA ILI BOLXSHIM KOLICHESTVOM LENT, I ON OSUSHCHESTVLYAET $(T-2)\hbox{-PUTEVOE}$~SLIYANIE. %%336 pREDPOLOZHIM SNOVA, CHTO U NAS ESTX SHESTX LENT I POPYTAEMSYA POSTROITX SHEMU SLIYANIYA, KOTORAYA RABOTAET SLEDUYUSHCHIM OBRAZOM, RASSHCHEPLYAYA VYVOD NA KAZHDOM UROVNE (BUKVY~I, o I~R OBOZNACHAYUT SOOTVETSTVENNO VVOD, VYVOD I PEREMOTKU): $$ \vcenter{\halign{ \hfil$#$\hfil&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill$#$\hfill\bskip\cr & & & & & & & \hbox{chISLO VYVODIMYH}\cr uROVENX & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{OTREZKOV}\cr 7 & I & I & I & I & R & O & u_7 \cr & I & I & I & I & O & R & v_7 \cr 6 & I & I & I & R & O & I & u_6 \cr & I & I & I & O & R & I & v_6 \cr 5 & I & I & R & O & I & I & u_5 \cr & I & I & O & R & I & I & v_5 \cr 4 & I & R & O & I & I & I & u_4 \cr & I & O & R & I & I & I & v_4 \cr 3 & R & O & I & I & I & I & u_3 \cr & O & R & I & I & I & I & v_3 \cr 2 & O & I & I & I & I & R & u_2 \cr & R & I & I & I & I & O & v_2 \cr 1 & I & I & I & I & R & O & u_1 \cr & I & I & I & I & O & R & v_1 \cr 0 & I & I & I & R & O & I & u_0 \cr & I & I & I & O & R & I & \cr }} \eqno (21) $$ chTOBY ZAKONCHITX RABOTU S ODNIM OTREZKOM NA t4 I PUSTYMI OSTALXNYMI LENTAMI, MY DOLZHNY IMETX $$ \eqalign{ v_0 &= 1,\cr u_0+v_1&= 0,\cr u_1+v_2 &= u_0+v_0,\cr u_2+v_3 &= u_1+v_1+u_0+v_0,\cr u_3+v_4 &= u_2+v_2+u_1+v_1+u_0+v_0,\cr u_4+v_5 &= u_3+v_3+u_2+v_2+u_1+v_1+u_0+v_0,\cr u_5+v_6 &= u_4+v_4u_3+v_3+u_2+v_2+u_1+v_1,\cr } $$ I~T.~D.; V OBSHCHEM SLUCHAE TREBUETSYA, CHTOBY $$ u _n+v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4} \eqno (22) $$ PRI VSEH~$n\ge 0$, ESLI SCHITATX~$u_j=v_j=0$ PRI VSEH~$j<0$. u |TIH URAVNENIJ NET EDINSTVENNOGO RESHENIYA; V SAMOM DELE, ESLI POLOZHITX VSE~$u$ RAVNYMI NULYU, TO POLUCHIM OBYCHNOE MNOGOFAZNOE, SLIYANIE, PRICHEM ODNA LENTA BUDET LISHNEJ! nO ESLI %%337 VYBRATX~$u_n\approx v_{n+1}$, TO VREMYA PEREMOTKI BUDET UDOVLETVORITELXNO SOVMESHCHENO. mAK-aLLESTER PREDLOZHIL VZYATX~$u_n=v_{n-1}+v_{n-2}+v_{n-3}+v_{n-4}$, $v_{n+1}=u_{n-1}+u_{n-2}+u_{n-3}+u_{n-4}$, TAK CHTO POSLEDOVATELXNOSTX $$ \ = \ $$ UDOVLETVORYAET ODNORODNOMU REKURRENTNOMU SOOTNOSHENIYU $$ x_n=x_{n-3}+x_{n-5}+x_{n-7}+x_{n-9}. $$ oKAZALOSX, ODNAKO, CHTO LUCHSHE POLOZHITX $$ \eqalign{ v_{n+1} &= u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2},\cr u_n &= u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}.\cr } $$ eTA POSLEDOVATELXNOSTX NE TOLXKO NEMNOGO LUCHSHE PO VREMENI SLIYANIYA, EE BOLXSHOE PREIMUSHCHESTVO V TOM, CHTO SOOTVETSTVUYUSHCHEE VREMYA SLIYANIYA MOZHNO PROANALIZIROVATX MATEMATICHESKI. [vARIANT mAK-aLLESTERA DLYA ANALIZA KRAJNE TRUDEN, POTOMU CHTO V ODNOJ FAZE MOGUT VSTRECHATXSYA OTREZKI RAZNOJ DLINY; MY UVIDIM, CHTO TAKOGO NE MOZHET SLUCHITXSYA PRI~(23).] mOZHNO VYVESTI CHISLO OTREZKOV NA KAZHDOJ LENTE NA KAZHDOM UROVNE, DVIGAYASX NAZAD PO SHEME~(21); MY POLUCHAEM SLEDUYUSHCHUYU SHEMU SORTIROVKI: {\def\m#1{\displaystyle\matrix{#1}}\ctable{ \hfil#\hfil&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip\cr uROVENX & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{vREMYA ZAPISI} & \hbox{vREMYA PEREMOTKI}\cr & 1^{23} & 1^{21} & 1^{17} & 1^{10} & - & 1^{11} & 82 & 23\cr 7 & 1^{19} & 1^{17} & 1^{13} & 1^6 & R & 1^{11}4^4 & 4\times 4=16 & 82-23\cr & 1^{13} & 1^{11} & 1^7 & - & 4^6& R & 6\times 4=24 & 25 \cr 6 & 1^{10} & 1^8 & 1^4 & R & 4^9& 1^84^4 & 3\times 4=12 & 10 \cr & 1^6 & 1^4 & - & 4^4 & R & 1^44^4 & 4\times 4=16 & 36 \cr 5 & 1^5 & 1^3 & R & 4^47^1 & 4^8& 1^34^4 & 1\times 7=7 & 17 \cr & 1^2 & - & 7^3 & R & 4^5& 4^4 & 3\times 7=21 & 23 \cr 4 & 1^1 & R &7^3 13^1& 4^37^1 & 4^4& 4^3 & 1\times 13=13 & 21 \cr & - & 13^1 & R & 4^27^1 & 4^3& 4^2 & 1\times 13=13 & 34 \cr 3 & R & 13^1 19^1& 7^2 13^1 & 4^1 7^1 & 4^2 & 4^1 & 1\times 19=19 & 23 \cr & 19^1 & R & 7^1 13^1 & 7^1 & 4^1& - & 1\times 19=19 & 32 \cr 2 & 19^1 31^0& 13^1 19^1 & 7^1 13^1 & 7^1 & 4^1 & R & 0\times 31=0 & 25 \cr & R & 19^1 & 13^1 & 7^0 & - & 31^1 & 1\times 31=31 & 19 \cr $\m{ 1\cr \cr 0\cr}$ & \m{ 19^1 31^0 \cr 19^1 31^0 \cr 19^1 31^0 \cr}& \m{ 19^1 \cr 19^1 \cr 19^1 \cr } & \m{13^1 \cr 13^1 \cr 13^1 \cr } & \m{ 7^0 \cr - \cr R \cr } & \m{ R \cr 52^0 \cr 52^0 82^0 \cr } & \m{ 31^1 52^0 \cr R \cr 31^1 52^0 \cr } & \left.\m{ 0\times 52 = 0 \cr 0\times 52 = 0 \cr 0\times 82 = 0 \cr } \right\} \max(36, 31, 23)\span\cr & (31^0) & (19^0) & - & 82^1 & (R) & (52^0) & 1\times 82 = 82 & 0\cr }} nESOVMESHCHENNAYA PEREMOTKA VSTRECHAETSYA TOLXKO PRI PEREMOTKE VVODNOJ LENTY~T5 (82~EDINICY), V TECHENIE PERVOJ POLOVINY FAZY VTOROGO UROVNYA (25~EDINIC) I V TECHENIE OKONCHATELXNYH FAZ "FIKTIVNOGO SLIYANIYA" NA UROVNYAH~1 I~0 (36 EDINIC). tAKIM %% 338 OBRAZOM, VREMYA RABOTY MOZHNO OCENITX VELICHINOJ~$273t+143r$; DLYA ALGORITMA~D SOOTVETSTVUYUSHCHAYA VELICHINA~$268t+208r$ POCHTI VSEGDA HUZHE. nETRUDNO VIDETX (SM.~UPR.~23), CHTO DLINY OTREZKOV, VYVODIMYH VO VREMYA KAZHDOJ FAZY, SUTX POSLEDOVATELXNO $$ 4, 4, 7, 13, 19, 31, 52, 82, 133, \ldots \eqno(24) $$ PRI |TOM POSLEDOVATELXNOSTX~$\< t_1, t_2, t_3,~\ldots>$ UDOVLETVORYAET ZAKONU $$ t_n=t_{n-2}+2t_{n-3}+t_{n-4}, \eqno(25) $$ ESLI SCHITATX~$t_n=1$ PRI~$n \le 0$. mOZHNO TAKZHE PROANALIZIROVATX OPTIMALXNOE RAZMESHCHENIE FIKTIVNYH OTREZKOV, RASSMOTREV STROKI CHISEL SLIYANIJ, KAK MY DELALI DLYA STANDARTNOGO MNOGOFAZNOGO METODA [SR.~S~(8)]: $$ \vcenter{\halign{ \hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr & & & & & & \hbox{oKONCHATELXNYJ} \cr \hbox{uROVENX} & T1 & T2 & T3 & T4 & T6 & \hbox{VYVOD NA LENTE}\cr 1 & 1 & 1 & 1 & 1 & - & T5 \cr 2 & 1 & 1 & 1 & - & 1 & T4 \cr 3 & 21 & 21 & 2 & 2 & 1 & T3 \cr 4 & 2221 & 222 & 222 & 22 & 2 & T2 \cr 5 & 23222 & 23222 & 2322 & 23 & 222 & T1 \cr 6 & 333323222 & 33332322 & 333323 & 3333 & 2322 & T6 \cr \multispan{7}\dotfill\cr n & A_n & B_n & C_n & D_n & E_n & T(k) \cr n+1 & (A''_n E_n+1)B_n & (A''_nE_n+1)C_n & (A''_n E_n+1)D_n & A''_nE_n+1 & A'_n & T(k-1)\cr \multispan{7}\dotfill\cr }} \eqno(26) $$ GDE~$A_n=A'nA''_n$ I~$A''_n$ SOSTOIT IZ POSLEDNIH $u_n$~CHISEL SLIYANIJ~$A_n$. pRIVEDENNOE VYSHE PRAVILO PEREHODA S UROVNYA~$n$ NA UROVENX~$n+1$ SPRAVEDLIVO DLYA \emph{LYUBOJ} SHEMY, UDOVLETVORYAYUSHCHEJ~(22). eSLI MY OPREDELYAEM~$u$ I~$v$ POSREDSTVOM~(23), TO STROKI~$A_n$,~\dots, $E_n$ MOZHNO VYRAZITX V SLEDUYUSHCHEM, DOVOLXNO PROSTOM VIDE [SR.~S~(9)]: $$ \eqalign{ A_n &= (W_{n-1}W_{n-2}W_{n-3}W_{n-4})+1,\cr B_n &= (W_{n-1}W_{n-2}W_{n-3})+1,\cr C_n &= (W_{n-1}W_{n-2})+1,\cr D_n &= (W_{n-1})+1,\cr E_n &= (W_{n-2}W_{n-3})+1,\cr } \eqno(27) $$ GDE $$ \eqalign{ W_n &= (W_{n-3}W_{n-4}W_{n-2}W_{n-3})+1 \rem{PRI $n>0$;}\cr W_0 &=\hbox{'0'}\hbox{ I } W_n = \hbox{(PUSTO)} \rem{ PRI $n<0$.}\cr } \eqno(28) $$ %%339 iSHODYA IZ |TIH SOOTNOSHENIJ, LEGKO PODROBNO PROANALIZIROVATX SLUCHAJ SHESTI LENT. v OBSHCHEM SLUCHAE, ESLI IMEETSYA $T\ge 5$~LENT, TO POLOZHIM~$P=T-2$ I OPREDELIM POSLEDOVATELXNOSTI~$\$, $\$ PO PRAVILAM $$ \eqalign{ v_{n+1}&= u_{n-1}+v_{n-1}+\cdots+u_{n-r}+v_{n-r};\cr u_n &= u_{n-r-1}+v_{n-r-1}+\cdots+u_{n-P}+v_{n-P} \rem{PRI $n\ge 0$,}\cr } \eqno(29) $$ GDE~$r=\floor{P/2}$, $v_0=1$ I~$u_n=v_n=0$ PRI~$n<0$. eSLI~$w_n=u_n+v_n$, TO IMEEM $$ \eqalign{ w_n &= w_{n-2}+\cdots+w_{n-r}+2w_{n-r-1}+w_{n-r-2}+\cdots+w_{n-P}, \rem{$n>0$,}\cr w_0&=1 \hbox{ I } w_n=0 \rem{PRI $n<0$.}\cr } \eqno(30) $$ pRI NACHALXNOM RASPREDELENII DLYA UROVNYA~$n+1$ NA LENTU~$k$ POMESHCHAETSYA $w_n+w_{n-1}+\cdots+w_{n-P+k}$~OTREZKOV PRI~$1\le k \le P$ I~$w_{n-1}+\cdots+w_{n-r}$--- NA LENTU~$T$; LENTA~$T-1$ ISPOLXZUETSYA DLYA VVODA. zATEM $u_n$~OTREZKOV SLIVAYUTSYA NA LENTU~$T$, V TO VREMYA KAK LENTA~$T-1$ PEREMATYVAETSYA; $v_n$~OTREZKOV SLIVAYUTSYA NA~$T-1$, POKA~$T$ PEREMATYVAETSYA; $u_{n-1}$~OTREZKOV---NA~$T-1$, POKA $T-2$~PEREMATYVAETSYA, I~T.~D. \htable{tABLICA~6} {pRIBLIZITELXNOE POVEDENIE MNOGOFAZNOGO SLIYANIYA S RASSHCHEPLENIEM LENT}% {\hfill$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr \hbox{lENTY} & \hbox{FAZY} & \hbox{pROHODY} & \hbox{pROHODY/FAZY} & \hbox{oTNOSHENIE}\cr & & & \hbox{V PROCENTAH} & \hbox{ROSTA}\cr \noalign{\hrule} 4 & 2.885\ln S+0.000 & 1.443\ln S+1.000 & 50 & 1.4142136\cr 5 & 2.078\ln S+0.232 & 0.929\ln S+1.022 & 45 & 1.6180340\cr 6 & 2.078\ln S-0.170 & 0.752\ln S+1.024 & 34 & 1.6180340\cr 7 & 1.958\ln S-0.408 & 0.670\ln S+1.007 & 34 & 1.6663019\cr 8 & 2.008\ln S-0.762 & 0.624\ln S+0.994 & 31 & 1.6454116\cr 9 & 1.972\ln S-0.987 & 0.595\ln S+0.967 & 30 & 1.6604077\cr 10 & 2.013\ln S-1.300 & 0.580\ln S+0.94l & 29 & 1.6433803\cr 20 & 2.069\ln S-3.164 & 0.566\ln S+0.536 & 27 & 1.6214947\cr \noalign{\hrule} } tABLICA~6 POKAZYVAET PRIBLIZITELXNOE POVEDENIE |TOJ PROCEDURY, KOGDA~$S$ NE SLISHKOM MALO. sTOLBEC "PROHODY/FAZY" PRIMERNO UKAZYVAET, KAKAYA CHASTX VSEGO FAJLA PEREMATYVAETSYA VO VREMYA KAZHDOJ POLOVINY FAZY I KAKAYA CHASTX FAJLA ZAPISYVAETSYA ZA VREMYA KAZHDOJ POLNOJ FAZY. \emph{mETOD RASSHCHEPLENIYA LENT PREVOSHODIT STANDARTNYJ MNOGOFAZNYJ NA SHESTI ILI BOLEE LENTAH} I, VEROYATNO; TAKZHE NA PYATI LENTAH, PO KRAJNEJ MERE DLYA BOLXSHIH~$S$. eSLI~$T=4$, TO UKAZANNAYA PROCEDURA STALA BY, PO SUSHCHESTVU, |KVIVALENTNOJ SBALANSIROVANNOMU DVUHPUTEVOMU SLIYANIYU \emph{BEZ} SOVMESHCHENIYA VREMENI PEREMOTKI, TAK KAK~$w_{2n+1}$ BYLO BY RAVNO~$0$ %$390 PRI VSEH~$n$. pO|TOMU |LEMENTY TABL.~6 PRI~$T=4$ BYLI POLUCHENY POSREDSTVOM NEBOLXSHOJ MODIFIKACII, SOSTOYASHCHEJ V TOM, CHTO POLAGALOSX $$ \displaylines{ v_2=0, u_1=1, v_1=0, u_0=0, v_0=1\hbox{ I } v_{n+1}=u_{n-1}+v_{n-1},\cr u_n=u_{n-2}+v_{n-2}\rem{PRI $n \ge 2$.}\cr } $$ eTO PRIVODIT K OCHENX INTERESNOJ SHEME SORTIROVKI (SM.~UPR.~25 I~26). \excercises \ex[16] nA RIS.~69 UKAZAN PORYADOK, V KOTOROM ALGORITM~D RASPREDELYAET PO PYATI LENTAM OTREZKI S~34-GO PO~65-J; V KAKOM PORYADKE RASPREDELYAYUTSYA OTREZKI S~1-GO PO~33-J? \rex[21] vERNO LI, CHTO POSLE DVUH FAZ SLIYANIYA V ALGORITME~D, T.~E.~KOGDA MY VO VTOROJ RAZ DOSTIGNEM SHAGA~D6, VSE FIKTIVNYE OTREZKI ISCHEZAYUT? \rex[22] dOKAZHITE, CHTO PO OKONCHANII SHAGA~D4 VSEGDA VYPOLNENO USLOVIE $|D|[1]\ge |D|[2] \ge \ldots \ge |D|[T]$. oB®YASNITE, VAZHNOSTX |TOGO USLOVIYA DLYA PRAVILXNOJ RABOTY MEHANIZMA SHAGOV~D2 I~D3. \ex[m20] vYVEDITE PROIZVODYASHCHIE FUNKCII~(7). \ex[vm26] (e.~p.~mAJLS~ML., 1960.) dOKAZHITE, CHTO PRI VSEH~$p\ge 2$ MNOGOCHLEN~$f_p(z)=z^p-z^{p-1}-\cdots-z-1$ IMEET $p$~RAZLICHNYH KORNEJ, IZ KOTORYH ROVNO ODIN PREVOSHODIT~1 PO ABSOLYUTNOJ VELICHINE. [\emph{uKAZANIE:} RASSMOTRITE MNOGOCHLEN~$z^{p+1}-2z^p+1$.] \ex[vm24] cELX |TOGO UPRAZHNENIYA---RASSMOTRETX SPOSOB SOSTAVLENIYA TABL.~1, 5 I~6. pREDPOLOZHIM, CHTO IMEETSYA SHEMA SLIYANIYA, SVOJSTVA KOTOROJ SLEDUYUSHCHIM OBRAZOM HARAKTERIZUYUTSYA MNOGOCHLENAMI~$p(z)$ I~$q(z)$: (1)~chISLO NACHALXNYH OTREZKOV V "TOCHNOM RASPREDELENII", TREBUYUSHCHEM $n$~FAZ SLIYANIYA, RAVNO KO|FFICIENTU PRI~$z^n$ V~$p(z)/q(z)$. (2)~chISLO NACHALXNYH OTREZKOV, OBRABATYVAEMYH V TECHENIE |TIH $n$~FAZ SLIYANIYA, RAVNO KO|FFICIENTU PRI~$z^n$ V~$p(z)/q(z)^2$. (3)~u MNOGOCHLENA~$q(z^{-1})$ ESTX "GLAVNYJ KORENX"~$\alpha$, TAKOJ, CHTO~$q(\alpha^{-1})=0$, $q'(\alpha^{-1}) \ne 0$, $p(\alpha^{-1})\ne 0$, I IZ~$q(\beta^{-1})=0$ SLEDUET, CHTO~$\beta=\alpha$ ILI~$\abs{\beta}<\abs{\alpha}$. dOKAZHITE, CHTO SUSHCHESTVUET~$\varepsilon > 0$, TAKOE, CHTO ESLI $S$~RAVNO CHISLU OTREZKOV V TOCHNOM RASPREDELENII, TREBUYUSHCHEM $n$~FAZ SLIYANIYA, A VO VREMYA |TIH FAZ OBRABATYVAETSYA $\rho S$~OTREZKOV, TO~$n=a\ln S+b+O(S^\varepsilon)$, $\rho=c\ln S+d+O(S^{-\varepsilon})$, GDE $$ \displaylines{ a=(\ln \alpha)^{-1},\quad b= -a\ln\left({p(\alpha^{-1})\over -q'(\alpha^{-1})}\right)-1, \quad c=a{\alpha\over -q'(\alpha^{-1})},\cr d={(b+1)\alpha-p'(\alpha^{-1})/p(\alpha^{-1})+q''(\alpha^{-1})/q'\alpha^{-1} \over -q'(\alpha^{-1})}.\cr } $$ \ex[vm22] pUSTX~$\alpha_p$---GLAVNYJ KORENX MNOGOCHLENA~$f_p(z)$ IZ UPR.~5. kAKOVO ASIMPTOTICHESKOE POVEDENIE~$\alpha_p$ PRI~$p\to\infty$? \ex[m20] (e.~nETTO, 1901.) pUSTX~$N^{(p)}_m$ ESTX CHISLO SPOSOBOV VYRAZITX~$m$ V VIDE UPORYADOCHENNOJ SUMMY CELYH CHISEL~$\set{1, 2,~\ldots, p}$. nAPRIMER, ESLI~$p=3$ I~$m=5$, TO IMEETSYA 13~SPOSOBOV: $1+1+1+1+1=1+1+1+2=1+1+2+1=1+1+3=1+2+1+1 =1+2+2= 1+3+1=2+1+1+1=2+1+2=2+2+1=2+3=3+1+1=3+2$. pOKAZHITE, CHTO $N^{(p)}_m$~YAVLYAYUTSYA OBOBSHCHENNYMI CHISLAMI fIBONACHCHI. \ex[m20] pUSTX~$K^{(p)}_m$---CHISLO POSLEDOVATELXNOSTEJ IZ NULEJ I EDINIC, TAKIH, CHTO V NIH NET $p$~POSLEDOVATELXNYH EDINIC. nAPRIMER, ESLI~$p=3$ I~$m=5$, IMEETSYA 24~VARIANTA: $00000$, $00001$, $00010$, $00011$, $00100$, $00101$, $00110$, $01000$, $01001$,~\dots, $11011$. pOKAZHITE, CHTO $K^{(p)}_m$~YAVLYAYUTSYA OBOBSHCHENNYMI CHISLAMI fIBONACHCHI. %%341 \ex[m27]\exhead(sISTEMA SCHISLENIYA S OBOBSHCHENNYMI CHISLAMI fIBONACHCHI.) dOKAZHITE, CHTO KAZHDOE NEOTRICATELXNOE CELOE~$n$ IMEET EDINSTVENNOE PREDSTAVLENIE V VIDE SUMMY RAZLICHNYH CHISEL fIBONACHCHI $p\hbox{-GO}$~PORYADKA~$F^{(p)}_j$ PRI~$j\ge p$, UDOVLETVORYAYUSHCHEE USLOVIYU, CHTO NE ISPOLXZUYUTSYA NIKAKIE $p$~POSLEDOVATELXNYE CHISLA fIBONACHCHI. \ex[m24] dOKAZHITE, CHTO $n\hbox{-J}$~|LEMENT CEPOCHKI~$Q_\infty$ V~(12) RAVEN KOLICHESTVU RAZLICHNYH CHISEL fIBONACHCHI V PREDSTAVLENII |LEMENTA $n-1$~CHISLAMI fIBONACHCHI PYATOGO PORYADKA (SM.~UPR.~10). \rex[M20] nAJDITE ZAVISIMOSTX MEZHDU STEPENYAMI MATRICY $$ \pmatrix{ 0 & 1 & 0 & 0 & 0 \cr 0 & 0 & 1 & 0 & 0 \cr 0 & 0 & 0 & 1 & 0 \cr 0 & 0 & 0 & 0 & 1 \cr 1 & 1 & 1 & 1 & 1 \cr } $$ I TOCHNYM FIBONACHCHIEVYM RASPREDELENIEM V~(1). \rex[22] dOKAZHITE SLEDUYUSHCHEE INTERESNOE SVOJSTVO TOCHNYH FIBONACHCHIEVYH RASPREDELENIJ: ESLI OKONCHATELXNYJ VYVOD OKAZYVAETSYA NA LENTE NOMER~$T$, TO CHISLO OTREZKOV NA VSEH DRUGIH LENTAH \emph{NECHETNOE,} ESLI OKONCHATELXNYJ VYVOD OKAZYVAETSYA NA NEKOTOROJ LENTE, OTLICHNOJ OT~$T$, TO CHISLO OTREZKOV BUDET \emph{NECHETNYM} NA |TOJ LENTE I \emph{CHETNYM} NA OSTALXNYH [SM.~(1)]. \ex[m35] pUSTX~$T_n(x)=\sum_{k\ge0} T_{nk}x^k$, GDE $T_n(x)$---MNOGOCHLENY, OPREDELENNYE V~(16). (a)~pOKAZHITE, CHTO DLYA KAZHDOGO~$k$ SUSHCHESTVUET CHISLO~$n(k)$, TAKOE, CHTO~$T_{1k}\le T_{2k} \le \ldots \le T_{n(k)k} > T_{n(k)+1,k}\ge\ldots\,$.. (b)~pRI USLOVII CHTO~$T_{n'k'}$, TAKAYA, CHTO~$\sum_n(S) =\min_{j\ge 1} \sum_j (S)$ PRI~$M_n\le S < M_{n+1}$, NO~$\sum_n(S)>\min_{j\ge 1}\sum_j(S)$ PRI~$S\ge M_{n+1}$. [sM.~(19).] \ex[m43] vERNO LI, CHTO~$\sum_{n-1}(m) < \sum_n (m)$ VLECHET~$\sum_n(m)\le\sum_{n+1}(m)\le \sum_{n+2}(m) \le \ldots?$ (tAKOJ REZULXTAT SILXNO UPROSTIL BY VYCHISLENIE TABL.~2.) \ex[M43] oPREDELITE ASIMPTOTICHESKOE POVEDENIE MNOGOFAZNOGO SLIYANIYA S OPTIMALXNYM RASPREDELENIEM FIKTIVNYH OTREZKOV. \ex[32] vERNO LI, CHTO OTREZKI DLYA OPTIMALXNOGO MNOGOFAZNOGO RASPREDELENIYA MOZHNO RAZMESTITX TAKIM OBRAZOM, CHTO RASPREDELENIE $S+1$~NACHALXNYH OTREZKOV POLUCHAETSYA PUTEM DOBAVLENIYA ODNOGO OTREZKA (NA SOOTVETSTVUYUSHCHUYU LENTU) K RASPREDELENIYU $S$~NACHALXNYH OTREZKOV? \ex[30] vERNO LI, CHTO OPTIMALXNOE MNOGOFAZNOE RASPREDELENIE DAET NAILUCHSHUYU VOZMOZHNUYU SHEMU SLIYANIYA V TOM SMYSLE, CHTO SUMMARNOE KOLICHESTVO OBRABATYVAEMYH NACHALXNYH OTREZKOV MINIMALXNO, ESLI TREBUETSYA, CHTOBY NACHALXNYE OTREZKI RAZMESHCHALISX NE BOLEE, CHEM NA $T-1$~LENTAH? (vREMENEM PEREMOTKI PRENEBRECHX.) \ex[21] sOSTAVXTE TABLICU, ANALOGICHNUYU~(1), DLYA MNOGOFAZNOGO METODA SORTIROVKI k|JRONA DLYA SHESTI LENT. \ex[m24] kAKAYA PROIZVODYASHCHAYA FUNKCIYA DLYA K|JRONOVSKOJ MNOGOFAZNOJ SORTIROVKI NA SHESTI LENTAH SOOTVETSTVUET~(7) I~(16)? kAKIE SOOTNOSHENIYA, ANALOGICHNYE~(9) I~(27), OPREDELYAYUT STROKI CHISEL SLIYANIJ? \ex[11] chTO DOLZHNO POYAVITXSYA NA UROVNE~7 V~(26)? \ex[M21] kAZHDYJ CHLEN POSLEDOVATELXNOSTI~(24) PRIBLIZITELXNO RAVEN SUMME DVUH PREDYDUSHCHIH. nABLYUDAETSYA LI |TO YAVLENIE DLYA OSTALXNYH CHLENOV POSLEDOVATELXNOSTI? sFORMULIRUJTE I DOKAZHITE TEOREMU O~$t_n-t_{n-1}-t_{n-2}$. \rex[29] kAKIE IZMENENIYA NADO BYLO BY SDELATX V~(25), (27) I (28), ESLI BY (23)~ZAMENILOSX NA~$v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}$, $u_n=v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}$? %%342 \ex[vm41] vYCHISLITE ASIMPTOTICHESKOE POVEDENIE MNOGOFAZNOJ PROCEDURY S RASSHCHEPLENIEM LENT, ESLI |LEMENT~$v_{n+1}$ OPREDELEN KAK SUMMA PERVYH$q$ CHLENOV~$u_{n-1}+v_{n-1}+\cdots+u_{n-P}+v_{n-P}$ PRI RAZLICHNYH~$P=T-2$ I~$0\le q \le 2P$. (v TEKSTE RASSMATRIVAETSYA TOLXKO SLUCHAJ~$q=2\floor{P/2}$; SR.~S~UPR.~23.) \ex[19] pRODEMONSTRIRUJTE, KAK MNOGOFAZNOE SLIYANIE S RASSHCHEPLENIEM LENT, UPOMYANUTOE V KONCE |TOGO PUNKTA, SORTIROVALO BY 32~NACHALXNYH OTREZKA. (dAJTE ANALIZ FAZA ZA FAZOJ, KAK |TO SDELANO V TEKSTE V PRIMERE S 82~OTREZKAMI I 6~LENTAMI.) \ex[m21] pROANALIZIRUJTE POVEDENIE MNOGOFAZNOGO SLIYANIYA S RASSHCHEPLENIEM LENT NA CHETYREH LENTAH PRI~$S=2^n$ I PRI~$S=2^n+2^{n-1}$ (SM.~UPR.~25). \ex[23] eSLI NACHALXNYE OTREZKI RASPREDELENY NA LENTAH V SOOTVETSTVII S TOCHNYM RASPREDELENIEM, TO MNOGOFAZNAYA STRATEGIYA PREVRASHCHAETSYA PROSTO V "SLIVATX DO OPUSTOSHENIYA". mY SLIVAEM OTREZKI SO VSEH NEPUSTYH VHODNYH LENT, POKA ODNA IZ NIH NE STANET PUSTOJ, ZATEM MY ISPOLXZUEM |TU LENTU KAK SLEDUYUSHCHUYU VYVODNUYU, A PREDYDUSHCHUYU VYVODNUYU LENTU ISPOLXZUEM KAK VVODNUYU. vERNO LI, CHTO |TA STRATEGIYA "SLIVATX DO OPUSTOSHENIYA" VSEGDA VYPOLNYAET SORTIROVKU NEZAVISIMO OT TOGO, KAK RASPREDELENY NACHALXNYE OTREZKI, PRI USLOVII CHTO MY RASPREDELYAEM IH PO KRAJNEJ MERE NA DVE LENTY (ODNA LENTA, KONECHNO, BUDET OSTAVLENA PUSTOJ, CHTOBY ONA MOGLA SLUZHITX PERVOJ VYVODNOJ LENTOJ). \edef\exref{\the\excerno} \ex[m26] pREDYDUSHCHEE UPRAZHNENIE OPREDELYAET VESXMA BOLXSHOE SEMEJSTVA SHEM SLIYANIYA. pOKAZHITE, CHTO MNOGOFAZNAYA SHEMA \emph{NAILUCHSHAYA} IZ NIH V SLEDUYUSHCHEM SMYSLE: ESLI IMEETSYA SHESTX LENT I MY RASSMATRIVAEM KLASS VSEH NACHALXNYH RASPREDELENIJ~$(a, b, c, d, e)$, TAKIH, CHTO STRATEGIYA "SLIVATX DO OPUSTOSHENIYA" TREBUET~$n$ ILI MENXSHE FAZ DLYA SORTIROVKI, TO~$a+b+c+d+e\le t_n$, GDE~$t_n$---SOOTVETSTVUYUSHCHEE CHISLO DLYA MNOGOFAZNOJ SORTIROVKI~(1). \ex[m47] uPR.~\exref{} POKAZYVAET, CHTO MNOGOFAZNOE RASPREDELENIE OPTIMALXNO SREDI VSEH SHEM "SLIVATX DO OPUSTOSHENIYA" V SMYSLE MINIMALXNOSTI CHISLA FAZ. nO YAVLYAETSYA LI ONO OPTIMALXNYM TAKZHE V SMYSLE MINIMALXNOSTI CHISLA PROHODOV? pUSTX CHISLA~$a$ I~$b$ VZAIMNO PROSTYE, I PREDPOLOZHIM, CHTO $a+b$~ESTX CHISLO fIBONACHCHI~$F_n$. vERNO LI SLEDUYUSHCHEE PREDPOLOZHENIE, VYSKAZANNOE r.~m.~kARPOM: CHISLO NACHALXNYH OTREZKOV, OBRABATYVAEMYH SHEMOJ "SLIVATX DO OPUSTOSHENIYA", NACHINAYUSHCHEJSYA S RASPREDELENIYA~$(a, b)$, BOLXSHE ILI RAVNO~$((n-5)F_{n+1}+(2n+2)F_n)/5$? (uKAZANNOE ZNACHENIE DOSTIGAETSYA, KOGDA~$a=F_{n+1}$, $b=F_{n-2}$.) \ex[42] sOSTAVXTE TABLICU, ANALOGICHNUYU TABL.~2, DLYA MNOGOFAZNOGO SLIYANIYA S RASSHCHEPLENIEM LENT. \subsubchap{kASKADNOE SLIYANIE}%5.4.3 dRUGAYA OSNOVNAYA SHEMA, NAZYVAEMAYA "KASKADNYM SLIYANIEM", NA SAMOM DELE BYLA OTKRYTA RANXSHE MNOGOFAZNOJ [b.~k.~bETC I~u.~k.~kARTER, ACM Nat'1 Conference, {\bf 14} (1959), Paper~14]. nIZHE V TABLICE |TOT PODHOD ILLYUSTRIRUETSYA DLYA 6~LENT I~190~NACHALXNYH OTREZKOV S ISPOLXZOVANIEM OBOZNACHENIJ IZ P.~5.4.2: \ctable{ #\hfil\bskip&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil &\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil &\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil&#\hfil\cr & T1 & T2 & T3 & T4 & T5 & T6 & kOLICHESTVO OBRABOTANNYH NACHALXNYH OTREZKOV\cr pROHOD~1. & 1^{55} & 1^{50} & 1^{41} & 1^{29} & 1^{15} & - & 190 \cr pROHOD~2. & - & {1^5}_* & 2^9 & 3^{12} & 4^{14} & 5^{15}& 190 \cr pROHOD~3. & 15^5 & 14^4 & 12^3 & 9^2 & {5^1}_*& - & 190 \cr pROHOD~4. & - & {15^1}_*& 29^1 & 41^1 & 50^1 & 55^1 & 190 \cr pROHOD~5. & 190^1 & - & - & - & - & - & 190 \cr } %%343 \bye