\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
$$
\<x_0, x_1, x_2, x_3, x_4, x_5, \ldots > = \<v_0, u_0, v_1, u_1, v_2, u_2, \ldots>
$$
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~$\<u_n>$, $\<v_n>$ 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'}<T_{nk'}$ I~$n'<n$,
 DOKAZHITE, CHTO~$T_{n'k}\le T_{nk}$ DLYA VSEH~$k\ge k'$. (c)~dOKAZHITE, CHTO
SUSHCHESTVUET NEUBYVAYUSHCHAYA POSLEDOVATELXNOSTX~$\< M_n >$, 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
