\input style \chapno=5\subchno=4\subsubchno=3\chapnotrue kASKADNOE SLIYANIE, PODOBNO MNOGOFAZNOMU, NACHINAETSYA S "TOCHNOGO RASPREDELENIYA" OTREZKOV PO LENTAM, HOTYA PRAVILA TOCHNOGO RASPREDELENIYA OTLICHNY OT PRAVIL P.~5.4.2. kAZHDAYA STROKA TABLICY PREDSTAVLYAET POLNYJ PROHOD PO \emph{VSEM} DANNYM. pROHOD~2, NAPRIMER, POLUCHAETSYA POSREDSTVOM VYPOLNENIYA PYATIPUTEVOGO SLIYANIYA S~T1, T2, T3, T4, T5 NA~T6, POKA~T5 NE STANET PUSTOJ (PRI |TOM NA~T6 POMESHCHAYUTSYA 15~OTREZKOV OTNOSITELXNOJ DLINY~5), ZATEM CHETYREHPUTEVOGO SLIYANIYA S~T1, T2, T3, T4 NA~T5, ZATEM TREHPUTEVOGO SLIYANIYA NA~T4, DVUHPUTEVOGO SLIYANIYA NA~T3 I, NAKONEC, ODNOPUTEVOGO SLIYANIYA (OPERACII KOPIROVANIYA) S~T1 NA~T2. pROHOD~3 POLUCHAETSYA TAKIM ZHE OBRAZOM PUTEM VYPOLNENIYA SNACHALA PYATIPUTEVOGO SLIYANIYA, POKA ODNA LENTA NE STANET PUSTOJ, ZATEM CHETYREHPUTEVOGO I~T.~D. (pOHOZHE, CHTO |TOMU PUNKTU KNIGI SLEDOVALO BY PRISVOITX NOMER~5.4.3.2.1, A NE~5.4.3!) yaSNO, CHTO OPERACII KOPIROVANIYA IZLISHNI, I IH MOZHNO BYLO BY OPUSTITX. fAKTICHESKI, ODNAKO, V SLUCHAE SHESTI LENT |TO KOPIROVANIE ZANIMAET TOLXKO NEBOLXSHOJ PROCENT VSEGO VREMENI. eLEMENTY, KOTORYE POLUCHAYUTSYA PROSTYM KOPIROVANIEM, OTMECHENY V PRIVEDENNOJ TABLICE ZVEZDOCHKOJ. tOLXKO~25 IZ~950 OBRABATYVAEMYH OTREZKOV PRINADLEZHAT |TOMU KLASSU. bOLXSHAYA CHASTX VREMENI OTVODITSYA PYATIPUTEVOMU I CHETYREHPUTEVOMU SLIYANIYAM. nA PERVYJ VZGLYAD MOZHET POKAZATXSYA, CHTO KASKADNAYA SHEMA---DOVOLXNO PLOHOJ VARIANT V SRAVNENII S MNOGOFAZNOJ, TAK KAK STANDARTNAYA MNOGOFAZNAYA SHEMA ISPOLXZUET VSE VREMYA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, V TO VREMYA KAK KASKADNAYA ISPOLXZUET $(T-1)\hbox{-PUTEVOE}$, $(T-2)\hbox{-PUTEVOE}$, $(T-3)\hbox{-PUTEVOE}$ I~T.~D., NO V DEJSTVITELXNOSTI ONA ASIMPTOTICHESKI \emph{LUCHSHE,} CHEM MNOGOFAZNAYA, DLYA SHESTI I BOLEE LENT! kAK MY VIDELI V P.~5.4.2, VYSOKIJ PORYADOK SLIYANIYA NE YAVLYAETSYA GARANTIEJ |FFEKTIVNOSTI. v TABL.~1 POKAZANY HARAKTERISTIKI VYPOLNENIYA KASKADNOGO SLIYANIYA PO ANALOGII S PODOBNOJ TABLICEJ P.~5.4.2. nETRUDNO VYVESTI "TOCHNYE RASPREDELENIYA" DLYA KASKADNOGO SLIYANIYA. dLYA SHESTI LENT IMEEM $$ \matrix{ \hbox{uROVENX} & T1 & T2 & T3 & T4 & T5 \cr 0 & 1 & 0 & 0 & 0 & 0 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 5 & 4 & 3 & 2 & 1 \cr 3 & 15 & 14 & 12 & 9 & 6 \cr 4 & 55 & 50 & 41 & 29 & 15 \cr 5 & 190 & 175 & 146 & 105 & 55 \cr \multispan{6}\dotfill\cr n & a_n & b_n & c_n & d_n & e_n \cr n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr } \eqno(1) $$ %%344 \htable{tABLICA 1}% {hARAKTER POVEDENIYA KASKADNOGO SLIYANIYA}% {\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr lENTY & \hbox{pROHODY} & \hbox{pROHODY} & \hbox{oTNOSHENIE}\cr & \hbox{(S KOPIROVANIEM)} & \hbox{(BEZ KOPIROVANIYA)} &\hbox{ROSTA}\cr \noalign{\hrule} 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 & 1.6180340\cr 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 & 2.2469796\cr 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 & 2.8793852\cr 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 & 3.5133371\cr 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 & 4.1481149\cr 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 & 4.7833861\cr 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 & 5.4189757\cr 10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 & 6.0547828\cr 20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr \noalign{\hrule} } oTMETIM INTERESNOE SVOJSTVO |TIH CHISEL---IH OTNOSITELXNYE VELICHINY YAVLYAYUTSYA TAKZHE I DLINAMI DIAGONALEJ PRAVILXNOGO $(2T-1)\hbox{-UGOLXNIKA}$. nAPRIMER, PYATX DIAGONALEJ ODINNADCATIUGOLXNIKA NA RIS.~73 IMEYUT OTNOSITELXNYE DLINY, OCHENX BLIZKIE K~190, 175, 146, 105 I~55! mY DOKAZHEM |TOT ZAMECHATELXNYJ FAKT \picture{rIS.~73. gEOMETRICHESKAYA INTERPRETACIYA KASKADNYH CHISEL.} POZDNEE V |TOM PUNKTE, A TAKZHE UVIDIM, CHTO OTNOSITELXNYE VREMENA, ZATRACHIVAEMYE NA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, $(T-2)\hbox{-PUTEVOE}$ SLIYANIE,~\dots, ODNOPUTEVOE SLIYANIE, PRIBLIZITELXNO PROPORCIONALXNY \emph{KVADRATAM} DLIN |TIH DIAGONALEJ. \section *nACHALXNOE RASPREDELENIE OTREZKOV. eSLI CHISLO NACHALXNYH OTREZKOV V DEJSTVITELXNOSTI NE ESTX CHISLO fIBONACHCHI, MY MOZHEM, KAK OBYCHNO, VSTAVITX FIKTIVNYE OTREZKI. pOVERHNOSTNYJ ANALIZ SITUACII POKAZYVAET, CHTO METOD PRIPISYVANIYA FIKTIVNYH OTREZKOV NESUSHCHESTVEN, TAK KAK KASKADNOE SLIYANIE VSEGDA OSUSHCHESTVLYAET %%345 POLNYE PROHODY; ESLI IMEETSYA 190~NACHALXNYH OTREZKOV, TO KAZHDAYA ZAPISX OBRABATYVAETSYA PYATX RAZ, KAK V PRIVEDENNOM VYSHE PRIMERE, NO ESLI IMEETSYA 191~OTREZOK, TO, OCHEVIDNO, SLEDUET UVELICHITX UROVENX, I TEPERX KAZHDAYA ZAPISX BUDET OBRABATYVATXSYA SHESTX RAZ. k SCHASTXYU, V DEJSTVITELXNOSTI MOZHNO IZBEZHATX TAKOGO REZKOGO SKACHKA. d|VID~e.~fERGYUSON NASHEL SPOSOB TAK RASPREDELITX NACHALXNYE OTREZKI, CHTO MNOGIE OPERACII VO VREMYA PERVOJ \picture{ rIS.~74. eFFEKTIVNOSTX KASKADNOGO SLIYANIYA S RASPREDELENIEM PO ALGORITMU~D. } FAZY SLIYANIYA SVODYATSYA K KOPIROVANIYU SODERZHIMOGO LENTY. eSLI OBOJTI TAKIE KOPIROVANIYA (PROSTO IZMENIV "LOGICHESKIE" NOMERA LENTOCHNYH USTROJSTV PO OTNOSHENIYU K "FIZICHESKIM" NOMERAM, KAK V ALGORITME~5.4.2D), TO POLUCHIM OTNOSITELXNO PLAVNYJ PEREHOD S UROVNYA NA UROVENX, KAK IZOBRAZHENO NA RIS.~74. pREDPOLOZHIM, CHTO $(a, b, c, d, e)$, GDE~$a\ge b \ge c \ge d \ge e$---TOCHNOE RASPREDELENIE. pEREOPREDELIV SOOTVETSTVIE MEZHDU LOGICHESKIMI I FIZICHESKIMI LENTOCHNYMI USTROJSTVAMI, MY MOZHEM PREDSTAVITX, CHTO REALXNOE RASPREDELENIE---|TO~$(e, d, c, b, a)$, %%346 T.~E.~$a$~OTREZKOV NA~T5, $b$~NA~t4 I~T.~D. sLEDUYUSHCHEE TOCHNOE RASPREDELENIE---|TO $(a+b+c+d+e, a+b+c+d, a+b+c, a+b, a)$; I ESLI VVOD ISCHERPYVAETSYA PREZHDE, CHEM MY DOSTIGAEM |TOGO SLEDUYUSHCHEGO UROVNYA, TO BUDEM SCHITATX, CHTO LENTY SODERZHAT SOOTVETSTVENNO~$(D_1, D_2, D_3, D_4, D_5)$ FIKTIVNYH OTREZKOV, GDE $$ \displaynarrow{ D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr } \eqno(2) $$ mY VOLXNY PREDSTAVLYATX SEBE, CHTO |TI FIKTIVNYE OTREZKI POYAVLYAYUTSYA NA LENTAH V LYUBOM UDOBNOM MESTE. pREDPOLAGAETSYA, CHTO PERVYJ PROHOD SLIYANIYA DAST $a$~OTREZKOV POSREDSTVOM PYATIPUTEVOGO SLIYANIYA, ZATEM $b$~OTREZKOV POSREDSTVOM CHETYREHPUTEVOGO I~T.~D. nASHA CELX SOSTOIT V RASPOLOZHENII FIKTIVNYH OTREZKOV TAKIM OBRAZOM, CHTOBY ZAMENITX SLIYANIE KOPIROVANIEM. uDOBNO VYPOLNYATX PERVYJ PROHOD SLIYANIYA SLEDUYUSHCHIM OBRAZOM: 1.~eSLI~$D_4=a$, TO VYCHESTX~$a$ IZ VSEH~$D_1$, $D_2$, $D_3$, $D_4$ I ZAYAVITX, CHTO~T5---REZULXTAT SLIYANIYA. eSLI~$D_40$, VERNUTXSYA K SHAGU~\stp{5}. v PROTIVNOM SLUCHAE UMENXSHITX~$k$ NA~1; ESLI~$k>0$, USTANOVITX~$m\asg |A|[T-j-1]-|A|[T-j]$ I VERNUTXSYA K~\stp{5}, ESLI~$m>0$. v PROTIVNOM SLUCHAE UMENXSHITX~$j$ NA~1; ESLI~$j>0$, PEREJTI K SHAGU~\stp{4}. v PROTIVNOM SLUCHAE UVELICHITX~$i$ NA~1; ESLI~$i|M|[j]$, I POMESTITX VYVODNOJ OTREZOK NA~$|TAPE|[p+1]$. pRODOLZHATX RABOTU, POKA $|TAPE|[p]$ NE STANET PUSTOJ. zATEM PEREMOTATX~$|TAPE|[p]$ I~$|TAPE|[p+1]$. \st[oPUSTITXSYA NA ODIN UROVENX.] uMENXSHITX~$l$ NA~1, USTANOVITX~$|FIRST|\asg 0$, USTANOVITX $(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (k |TOMU MOMENTU VSE~|D| I~|M|---NULI I TAKOVYMI OSTANUTSYA.) vERNUTXSYA K~\stp{8}. \algend shAGI~C1--C6 |TOGO ALGORITMA VYPOLNYAYUT RASPREDELENIE, SHAGI~C7--C9 VYPOLNYAYUT SLIYANIE; |TI DVE CHASTI SOVERSHENNO NEZAVISIMY ODNA OT DRUGOJ, I MOZHNO BYLO BY HRANITX~$|M|[k]$ I~$|AA|[k+1]$ V ODNIH I TEH ZHE YACHEJKAH PAMYATI. \picture{rIS.~75. kASKADNOE SLIYANIE SO SPECIALXNYM RASPREDELENIEM.} \section *aNALIZ KASKADNOGO SLIYANIYA. kASKADNOE SLIYANIE PODDAETSYA ANALIZU S BOLXSHIM TRUDOM, CHEM MNOGOFAZNOE. nO |TOT ANALIZ OSOBENNO INTERESEN, POSKOLXKU SODERZHIT MNOGO ZAMECHATELXNYH FORMUL. nASTOYATELXNO REKOMENDUEM CHITATELYAM, INTERESUYUSHCHIMSYA DISKRETNOJ MATEMATIKOJ, SAMOSTOYATELXNO PROANALIZIROVATX KASKADNOE RASPREDELENIE, PREZHDE CHEM CHITATX DALXSHE, VEDX CHISLA %%350 IMEYUT TAK MNOGO NEOBYCHNYH SVOJSTV, OTKRYVATX KOTORYE---ODNO UDOVOLXSTVIE! mY OBSUDIM ZDESX LISHX ODIN IZ MNOGIH PODHODOV, OBRASHCHAYA OSOBOE VNIMANIE NA METODY POLUCHENIYA REZULXTATOV. dLYA UDOBSTVA RASSMOTRIM SLUCHAJ SHESTI LENT. pRI |TOM BUDEM STARATXSYA POLUCHITX FORMULY, KOTORYE OBOBSHCHAYUTSYA NA SLUCHAJ LYUBOGO~$T$. sOOTNOSHENIYA~(1) PRIVODYAT K PERVOJ OSNOVNOJ SISTEME: $$ \eqalignter{ a_n &= a_n &=\perm{0}{0}a_n,\cr b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr } \eqno(4) $$ oBOZNACHIM~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ I OPREDELIM MNOGOCHLENY $$ \eqalignno{ q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k} = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr } $$ rEZULXTAT~(4) KRATKO MOZHNO ISTOLKOVATX TAK, CHTO~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ SVODYATSYA K KONECHNYM SUMMAM, SOOTVETSTVUYUSHCHIM GRANICHNYM USLOVIYAM, A IMENNO ZNACHENIYAM~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots, KOTORYE POYAVLYAYUTSYA V~(4) (PRI NEBOLXSHIH~$n$), NO NE V~$A(z)$. chTOBY POLUCHITX PODHODYASHCHIE GRANICHNYE USLOVIYA, PRIMENIM REKURRENTNOE SOOTNOSHENIE V OBRATNUYU STORONU DLYA OTRICATELXNYH UROVNEJ DO UROVNYA~$-8$: \ctable{ \hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr \hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr 0 & 1 & 0 & 0 & 0 & 0\cr -1 & 0 & 0 & 0 & 0 & 1\cr -2 & 1 & -1 & 0 & 0 & 0\cr -3 & 0 & 0 & 0 & -1 & 2\cr -4 & 2 & -3 & 1 & 0 & 0\cr -5 & 0 & 0 & 1 & -4 & 5\cr -6 & 5 & -9 & 5 & -1 & 0\cr -7 & 0 & -1 & 6 & -14 & 14\cr -8 & 14 & -28 & 20 & -7 & 1\cr } (dLYA SEMI LENT TABLICA BYLA BY ANALOGICHNOJ, ODNAKO STROKI S NECHETNYMI~$n$ BYLI BY SDVINUTY VPRAVO NA ODIN |LEMENT.) tAJNA POSLEDOVATELXNOSTI~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$ MGNOVENNO RASKRYVAETSYA SPECIALISTOM PO INFORMATIKE, TAK KAK %%351 |TA POSLEDOVATELXNOSTX VSTRECHAETSYA V SVYAZI S OCHENX MNOGIMI REKURRENTNYMI ALGORITMAMI (NAPRIMER, V UPR.~2.2.1-4 I FORMULE~2.3.4.4-13)). iTAK, MY PREDPOLAGAEM, CHTO V SLUCHAE $T$~LENT $$ \eqalignrem{ a_{-2n}&=\perm{2n}{n}{1\over n+1} & PRI $0\le n \le T-2$; \cr a_{-2n-1}&=0 & PRI $0\le n \le T-3$.\cr } \eqno(6) $$ chTOBY PROVERITX PRAVILXNOSTX |TOGO PREDPOLOZHENIYA, DOSTATOCHNO POKAZATX, CHTO~(6) I~(4) PRIVODYAT K PRAVILXNYM REZULXTATAM DLYA UROVNEJ~0 I~1. dLYA UROVNYA~1 |TO OCHEVIDNO, A DLYA UROVNYA~0 NAM NADO PROVERITX, CHTO $$ \perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots =\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1} =\delta_{m0} \eqno(7) $$ DLYA~$0\le m \le T-2$. k SCHASTXYU, |TU SUMMU MOZHNO VYCHISLITX STANDARTNYMI METODAMI (|TO "ZADACHA~2", ODIN IZ OSNOVNYH PRIMEROV V TEKSTE P.~4.2.6). tEPERX MOZHNO VYCHISLITX KO|FFICIENTY~$B(z)-q_1(z)A(z)$ I~T.~D. rASSMOTRIM, NAPRIMER, KO|FFICIENT PRI~$z^{2m}$ V~$D(z)-q_3(z)A(z)$. oN RAVEN $$ \eqalign{ \sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k} &=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr &=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr &=(-1)^{m+1}\perm{2+m}{2m}\cr } $$ IZ REZULXTATA "ZADACHI~3" V~P.~1.2.6. tAKIM OBRAZOM, MY VYVELI FORMULY $$ \eqalign{ A(z) &=q_0(z)A(z);\cr B(z) &=q_1(z)A(z)-q_0(z);\cr C(z) &=q_2(z)A(z)-q_1(z);\cr D(z) &=q_3(z)A(z)-q_2(z);\cr E(z) &=q_4(z)A(z)-q_3(z).\cr } \eqno (8) $$ kROME TOGO, IMEEM~$e_{n+1}=a_n$; SLEDOVATELXNO, $zA(z)=E(z)$ I $$ A(z)=q_3(z)/(q_4(z)-z). \eqno (9) $$ pROIZVODYASHCHIE FUNKCII BYLI VYRAZHENY PRI POMOSHCHI $q\hbox{-MNOGOCHLENOV}$, PO|TOMU MY HOTIM LUCHSHE IZUCHITX~$q$. v |TOM OTNOSHENII POLEZNO UPR.~1.2.9-15, TAK KAK ONO DAET VYRAZHENIE V ZAMKNUTOM %%352 VIDE, KOTOROE MOZHET BYTX ZAPISANO KAK $$ q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1} \over \sqrt{4-z^2}} \eqno(10) $$ vSE UPROSHCHAETSYA, ESLI TEPERX POLOZHITX~$z=2 \sin\theta$: $$ \eqalignno{ q_m(2\sin\theta)=& {(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr &={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr } $$ (eTO SOVPADENIE ZASTAVLYAET DUMATX, CHTO MNOGOCHLENY~$q_m(z)$ HOROSHO IZVESTNY V MATEMATIKE; I DEJSTVITELXNO, VZGLYANUV V SOOTVETSTVUYUSHCHIE TABLICY, VIDIM, CHTO~$q_m(z)$, PO SUSHCHESTVU, MNOGOCHLEN chEBYSH¸VA VTOROGO RODA, A IMENNO~$(-1)^m U_{2m}(z/2)$ V OBYCHNYH OBOZNACHENIYAH.) tEPERX MOZHNO OPREDELITX KORNI ZNAMENATELYA V~(9): $q_4(2\sin\theta)=2\sin\theta$ SVODITSYA K $$ \cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta. $$ rESHENIYA |TOGO SOOTNOSHENIYA POLUCHAEM, ESLI TOLXKO~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; VSE TAKIE~$\theta$ DAYUT KORNI ZNAMENATELYA V~(9) PRI USLOVII, CHTO~$\cos\theta\ne 0$. (eSLI~$\cos\theta=0$, TO~$q_m(\pm2)=\pm(2m+1)$, NIKOGDA NE RAVNO~$\pm2$.) sLEDOVATELXNO, POLUCHAEM 8~RAZLICHNYH KORNEJ: $$ \displaylines{ q_4(z)-z=0 \qquad \hbox{ PRI } z=2\sin{-5\over 14}\pi,\quad 2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr 2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad 2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr } $$ tAK KAK~$q_4(z)$---MNOGOCHLEN STEPENI~8, MY UCHLI VSE KORNI. pERVYE TRI IZ |TIH ZNACHENIJ DAYUT~$q_3(z)=0$, TAK CHTO~$q_3(z)$ I~$q_4(z)-z$ IMEYUT OBSHCHIM DELITELEM MNOGOCHLEN TRETXEJ STEPENI. oSTALXNYE PYATX KORNEJ UPRAVLYAYUT ASIMPTOTICHESKIM POVEDENIEM KO|FFICIENTOV~$A(z)$, ESLI RAZLOZHITX~(9) V |LEMENTARNYE DROBI. pEREJDYA K RASSMOTRENIYU OBSHCHEGO SLUCHAYA $T$~LENT, POLOZHIM~$\theta_k=(4k+1)\pi/(4T-2)$. pROIZVODYASHCHAYA FUNKCIYA~$A(z)$ DLYA $T\hbox{-LENTOCHNYH}$ KASKADNYH CHISEL PRINIMAET VID $$ {4\over 2T-1}\sum_{-T/2j$ I ESLI $A$~ESTX IMYA LENTY, TO DEREVO NE SODERZHIT KONFIGURACII \picture{p.362} %%363 c)~ESLI~$i k \ge r$ I~$y^{(i)}_j=-1$, $y^{(k)}_j=+1$. cELX |TOGO UPRAZHNENIYA---DOKAZATX, CHTO \emph{KASKADNOE SLIYANIE MINIMIZIRUET CHISLO STADIJ} SREDI VSEH SHEM SLIYANIYA S TEM ZHE CHISLOM LENT I NACHALXNYH OTREZKOV. uDOBNO VVESTI NEKOTORYE OBOZNACHENIYA. bUDEM PISATX~$v\to w$, ESLI~$v$ I~$w$---TAKIE $T\hbox{-VEKTORY}$, CHTO SUSHCHESTVUET SHEMA SLIYANIYA, KOTORAYA V SVOEJ PERVOJ STADII PEREVODIT~$w$ V~$v$ (T.~E.\ SUSHCHESTVUET SHEMA SLIYANIYA~$y^{(m)}\ldots{}y^{(0)}$, TAKAYA, CHTO $y^{(m)}\ldots{}y^{(l+1)}$~YAVLYAETSYA STADIEJ, $w=y^{(m)}+\cdots+y^{(0)}$ I~$v=y^{(l)}+\cdots+y^{(0)}$). bUDEM PISATX~$v\preceq w$, ESLI~$v$ I~$w$---$T\hbox{-VEKTORY}$, TAKIE, CHTO SUMMA NAIBOLXSHIH $k$~|LEMENTOV VEKTORA~$v$ NE PREVYSHAET SUMMY NAIBOLXSHIH $k$~|LEMENTOV VEKTORA~$w$ PRI~$1\le k \le T$. tAK, NAPRIMER, $(2, 1, 2, 2, 2, 1) \preceq (1, 2, 3, 0, 3, 1)$, TAK KAK $2\le 3$, $2+2\le 3+3$,~\dots, $2+2+2+2+ 1+1\le 3+3+2+1+1 +0$. nAKONEC, ESLI~$v=(v_1,~\ldots, v_T)$, TO PUSTX~$C(v)=(s_T, s_{T-2}, s_{T-3},~\ldots, s_1, 0)$, GDE $s_k$~ESTX SUMMA NAIBOLXSHIH $k$~|LEMENTOV VEKTORA~$v$. %% !!! SSYLKA NA UPRAZHNENIE (a)~dOKAZHITE, CHTO~$v\to C(v)$. (b)~dOKAZHITE, CHTO~$v\preceq w$ VLECHET~$C(v)\preceq C(w)$. (c)~sCHITAYA IZVESTNYM REZULXTAT UPR.~24, DOKAZHITE, CHTO KASKADNOE SLIYANIE MINIMIZIRUET CHISLO STADIJ. %% !!! SSYLKA NA UPRAZHNENIE \ex[m35] iSPOLXZUYA OBOZNACHENIYA UPR.~23, DOKAZHITE, CHTO~$v\to w$ VLECHET~$w\preceq C(v)$. %% !!! SSYLKA NA UPRAZHNENIE \ex[m36] (r.~m.~kARP.) bUDEM GOVORITX, CHTO SEGMENT~$y^{(q)}\ldots{}y^{(r)}$ SHEMY SLIYANIYA YAVLYAETSYA \dfn{FAZOJ,} ESLI NI ODNA IZ LENT NE ISPOLXZUETSYA I DLYA VVODA, I DLYA VYVODA, T.~E.\ ESLI NE SUSHCHESTVUET~$i$, $j$, $k$, TAKIH, CHTO~$q\ge i$, $k\ge r$ I~$y^{(i)}_j=+1$, $y^{(k)}_j=-1$. cELX |TOGO UPRAZHNENIYA---ISSLEDOVATX SHEMU SLIYANIYA, KOTORAYA MINIMIZIRUET CHISLO FAZ. mY BUDEM PISATX~$v \To w$, ESLI~$w$ MOZHET BYTX PREOBRAZOVANO V~$v$ ZA ODNU FAZU (SR.~S~PODOBNYM OBOZNACHENIEM, VVEDENNYM V UPR.~23), I PUSTX~$D_k(v)=(s_k+t_{k+1}, s_k+t_{k+2},~\ldots, s_k+t_T, 0,~\ldots, 0)$, GDE~$t_j$ OBOZNACHAET~$j\hbox{-J}$ V PORYADKE UBYVANIYA |LEMENT~$v$ I~$s_k=t_1+\cdots+t_k$. (a)~dOKAZHITE, CHTO~$v\To D_k(v)$ PRI~$1\le k < T$. (b)~dOKAZHITE, CHTO IZ~$v\preceq w$ SLEDUET~$D_k(v)\preceq D_k(w)$ PRI~$1\le k < T$. (c)~dOKAZHITE, CHTO IZ~$v\To w$ SLEDUET~$w\preceq D_k(v)$ DLYA NEKOTOROGO~$k$, $1\le k < T$. (d)~sLEDOVATELXNO, SHEMA SLIYANIYA, SORTIRUYUSHCHAYA MAKSIMALXNOE CHISLO NACHALXNYH OTREZKOV NA $T$~LENTAH ZA $q$~FAZ, MOZHET BYTX IZOBRAZHENA POSLEDOVATELXNOSTXYU .CELYH CHISEL~$k_1 k_2~\ldots k_q$, TAKOJ, CHTO NACHALXNOE RASPREDELENIE ESTX~$D_{k_q}(\ldots D_{k_2}(D_{k_1}(u))\ldots)$, %!!! SSYLKA NA UPRAZHNENIE GDE~$u=(1, 0,~\ldots, 0)$. eTA STRATEGIYA MINIMUMA FAZ, IMEET SILXNOE $T\hbox{-fifo}$~PREDSTAVLENIE, I ONA TAKZHE VHODIT V KLASS SHEM UPR.~22. kOGDA~$T=3$, |TO \emph{MNOGOFAZNAYA} SHEMA, A PRI~$T=4$, 5, 6, 7 |TO VARIACIYA \emph{SBALANSIROVANNOJ} SHEMY. %!!! SSYLKA NA UPRAZHNENIE \ex[m46] (r.~m.~kARP). vERNO LI, CHTO OPTIMALXNAYA POSLEDOVATELXNOSTX~$k_1 k_2~\ldots k_q$, UPOMYANUTAYA V UPR.~25, VSEGDA RAVNA~$1\ceil{T/2}\floor{T/2}\ceil{T/2}\floor{T/2}~\ldots$ DLYA VSEH~$T\ge 4$ I VSEH DOSTATOCHNO BOLXSHIH~$q$? \subsubchap{oSCILLIRUYUSHCHAYA SORTIROVKA}%5.4.5 eSHCHE ODIN PODHOD K SORTIROVKE SLIYANIEM BYL PREDLOZHEN shELDONOM sOBELEM V [{\sl JACM,\/} {\bf 9} (1962), 372--375]. vMESTO TOGO CHTOBY NACHINATX S PROHODA RASPREDELENIYA, KOGDA VSE NACHALXNYE OTREZKI RASPREDELYAYUTSYA PO LENTAM, ON PREDLOZHIL ALGORITM, KOTORYJ PEREKLYUCHAETSYA TO NA RASPREDELENIE, TO NA SLIYANIE, TAK CHTO BOLXSHAYA CHASTX SORTIROVKI PROISHODIT ESHCHE DO TOGO, KAK VSYA ISHODNAYA INFORMACIYA BUDET POLNOSTXYU PROSMOTRENA. %%371 pREDPOLOZHIM, NAPRIMER, CHTO DLYA SLIYANIYA ISPOLXZUETSYA PYATX LENT. pO METODU sOBELYA 16~NACHALXNYH OTREZKOV BUDUT SORTIROVATXSYA SLEDUYUSHCHIM OBRAZOM: \ctable{ #\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &#\hfil\cr & \hfil oPERACIYA& T1 & T2 & T3 & T4 & T5 & \hbox{sTOIMOSTX} \cr fAZA~1.& rASPREDELENIE & A_1 & A_1 & A_1 & A_1 & - & 4\cr fAZA~2.& sLIYANIE & - & - & - & - & D_4 & 4\cr fAZA~3.& rASPREDELENIE & - & A_1 & A_1 & A_1 & D_4A_1& 4\cr fAZA~4.& sLIYANIE & D_4 & - & - & - & D_4 & 4\cr fAZA~5.& rASPREDELENIE & D_4A_1& - & A_1 & A_1 & D_4A_1& 4\cr fAZA~6.& sLIYANIE & D_4 & D_4 & - & - & D_4 & 4\cr fAZA~7.& rASPREDELENIE & D_4A_1& D_4A_1& - & A_1 & D_4A_1& 4\cr fAZA~8.& sLIYANIE & D_4 & D_4 & D_4 & - & D_4 & 4\cr fAZA~9.& sLIYANIE & - & - & - & A_{16} & - & 16\cr } zDESX, KAK I V P.~5.4.4, MY ISPOLXZUEM~$A_r$ I~$D_r$ DLYA OBOZNACHENIYA SOOTVETSTVENNO VOZRASTAYUSHCHIH I UBYVAYUSHCHIH OTREZKOV OTNOSITELXNOJ DLINY~$r$. rASSMATRIVAEMYJ METOD NACHINAET S ZAPISI PO ODNOMU NACHALXNOMU OTREZKU NA KAZHDUYU IZ CHETYREH LENT I SLIVAET IH (CHITAYA V OBRATNOM NAPRAVLENII) NA PYATUYU LENTU. oPYATX VOZOBNOVLYAETSYA RASPREDELENIE, NA |TOT RAZ CIKLICHESKI SDVINUTOE NA~1 VPRAVO PO OTNOSHENIYU K LENTAM, I VTOROE SLIYANIE DAET ESHCHE ODIN OTREZOK~$D_4$. kOGDA |TIM SPOSOBOM SFORMIROVANY CHETYRE OTREZKA~$D_4$, DOPOLNITELXNOE SLIYANIE SOZDAET~$A_{16}$. pROCESS MOZHNO PRODOLZHATX, SOZDAVAYA ESHCHE TRI~$A_{16}$, SLIVAYA IH V~$D_{64}$ I~T.~D.\ DO TEH POR, POKA NE ISCHERPAYUTSYA ISHODNYE DANNYE. nE NUZHNO ZNATX ZARANEE DLINU ISHODNYH DANNYH. eSLI CHISLO NACHALXNYH OTREZKOV~$S$ ESTX~$4^m$, TO NETRUDNO VIDETX, CHTO |TOT METOD OBRABATYVAET KAZHDUYU ZAPISX ROVNO $m+1$~RAZ (ODIN RAZ VO VREMYA RASPREDELENIYA I $m$~RAZ VO VREMYA SLIYANIYA). eSLI~$S$ LEZHIT MEZHDU~$4^{m-1}$ I~$4^m$, TO MOZHNO S POMOSHCHXYU FIKTIVNYH OTREZKOV UVELICHITX~$S$ DO~$4^m$; SLEDOVATELXNO, OBSHCHEE VREMYA SORTIROVKI BUDET OPREDELYATXSYA $\ceil{\log_4 S}+1$~PROHODAMI PO VSEM DANNYM. eTO KAK RAZ TO, CHTO DOSTIGAETSYA PRI SBALANSIROVANNOJ SORTIROVKE NA \emph{VOSXMI} LENTAH; V OBSHCHEM SLUCHAE OSCILLIRUYUSHCHAYA SORTIROVKA S $T$~RABOCHIMI LENTAMI |KVIVALENTNA SBALANSIROVANNOMU SLIYANIYU S $2(T-1)$~LENTAMI, TAK KAK ONA DELAET $\ceil{\log_{T-1} S}+1$~PROHODOV PO DANNYM. eSLI $S$~OKAZYVAETSYA STEPENXYU~$T-1$, TO |TO SAMOE LUCHSHEE, CHTO MOZHNO POLUCHITX PRI \emph{LYUBOM} METODE S $T$~LENTAMI, TAK KAK ZDESX DOSTIGAETSYA NIZHNYAYA OCENKA IZ SOOTNOSHENIYA~(5.4.4-9). s DRUGOJ STORONY, ESLI~$S$ RAVNO~$(T-1)^{m-1}+1$, T.~E.\ ROVNO NA EDINICU BOLXSHE STEPENI~$T-1$, TO |TOT METOD TERYAET POCHTI CELYJ PROHOD. v UPR.~2 POKAZANO, KAK USTRANITX CHASTX |TOJ LISHNEJ RABOTY, ISPOLXZUYA SPECIALXNUYU PROGRAMMU OKONCHANIYA. eSHCHE ODNO USOVERSHENSTVOVANIE BYLO PREDLOZHENO V 1966~G. dENISOM~l.~b|NCHEROM, %% 372 KOTORYJ NAZVAL SVOYU PROCEDURU PEREKRESTNYM SLIYANIEM. [sM.~H.~Wedekind, Datenorganisation (Berlin W. de Gruyter, 1970). 164--166, I~U.~S.~Patent~3540000 (10~NOYABRYA 1970).] oSNOVNAYA IDEYA SOSTOIT V TOM, CHTOBY OTLOZHITX SLIYANIE DO TEH POR, POKA NE BUDET NAKOPLENO BOLXSHE SVEDENIJ OB~$S$. mY OBSUDIM NESKOLXKO IZMENENNUYU FORMU PERVONACHALXNOJ SHEMY b|NCHERA. eTA ULUCHSHENNAYA OSCILLIRUYUSHCHAYA SORTIROVKA DEJSTVUET SLEDUYUSHCHIM OBRAZOM: \ctable{ #\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &#\hfil\cr & oPERACIYA & T1 & T2 & T3 & T4 & t5 & \hbox{sTOIMOSTX} \cr fAZA~1.& rASPREDELENIE& - & A_1 & A_1 & A_1 & A_1 & 4\cr fAZA~2.& rASPREDELENIE& - & A_1 & A_1A_1& A_1A_1& A_1A_1& 3\cr fAZA~3.& sLIYANIE & D_4 & - & A_1 & A_1 & A_1 & 4\cr fAZA~4.& rASPREDELENIE& D_4A_1& - & A_1 & A_1A_1& A_1A_1& 3\cr fAZA~5.& sLIYANIE & D_4 & D_4 & - & A_1 & A_1 & 4\cr fAZA~6.& rASPREDELENIE& D_4A_1& D_4A_1& - & A_1 & A_1A_1& 3\cr fAZA~7.& sLIYANIE & D_4 & D_4 & D_4 & - & A_1 & 4\cr fAZA~8.& rASPREDELENIE& D_4A_1& D_4A_1& D_4A_1& - & A_1 & 3\cr fAZA~9.& sLIYANIE & D_4 & D_4 & D_4 & D_4 & - & 4\cr \noalign{\smallskip \noindent v |TOT MOMENT MY NE SLIVAEM VSE~$D_4$ V~$A_{16}$, (ESLI TOLXKO NE OKAZHETSYA, CHTO ISHODNYE DANNYE ISCHERPANY); LISHX POSLE TOGO, KAK ZAKONCHITSYA \smallskip} fAZA~15.& sLIYANIE & D_4 D_4 & D_4 D_4 & D_4 D_4 & D_4 & - & 4 \cr \noalign {\smallskip \noindent BUDET POLUCHEN PERVYJ OTREZOK~$A_{16}$: \smallskip} fAZA~16. & sLIYANIE & D_4 & D_4 & D_4 - & A_{16} & 16 \cr \noalign{\smallskip \noindent vTOROJ OTREZOK~$A_{16}$ POYAVITSYA POSLE SOZDANIYA ESHCHE TREH~$D_4$: \smallskip} fAZA~22. & sLIYANIE & D_4 D_4 & D_4 D_4 & D_4 & - & A_{16}D_4 & 4\cr fAZA~23. & sLIYANIE & D_4 & D_4 & - & A_{16} & A_{16} & 16 \cr } I~T.~D.\ (SR.~S~FAZAMI~1--5). pREIMUSHCHESTVA SHEMY b|NCHERA MOZHNO VIDETX, ESLI IMEETSYA, NAPRIMER, TOLXKO PYATX NACHALXNYH OTREZKOV: OSCILLIRUYUSHCHAYA SORTIROVKA (EE MODIFIKACIYA IZ UPR.~2) VYPOLNYALA BY CHETYREHPUTEVOE SLIYANIE (NA FAZE~2), ZA KOTORYM SLEDOVALO BY DVUHPUTEVOE SLIYANIE S OBSHCHEJ STOIMOSTXYU~$4+4+4+1+5= 14$, TOGDA KAK SHEMA b|NCHERA VYPOLNYALA BY DVUHPUTEVOE SLIYANIE (NA FAZE~3), ZA KOTORYM SLEDOVALO BY CHETYREHPUTEVOE SLIYANIE S OBSHCHEJ STOIMOSTXYU~$4+1+2+5=12$. (oBA METODA TAKZHE TREBUYUT NEBOLXSHIH DOPOLNITELXNYH ZATRAT, IMENNO ODNOKRATNOJ PEREMOTKI PERED OKONCHATELXNYM SLIYANIEM.) %%373 tOCHNOE OPISANIE METODA b|NCHERA SODERZHITSYA NIZHE V ALGORITME~B. k SOZHALENIYU, SOOTVETSTVUYUSHCHUYU PROCEDURU, PO-VIDIMOMU, TRUDNEJ PONYATX, CHEM ZAPROGRAMMIROVATX; LEGCHE OB®YASNITX |TOT METOD evm, CHEM PROGRAMMISTU! chASTICHNO |TO PROISHODIT PO TOJ PRICHINE, CHTO REKURSIVNYJ METOD VYRAZHEN V ITERATIVNOM VIDE I ZATEM PODVERGNUT NEKOTOROJ OPTIMIZACII; CHITATELX, VOZMOZHNO, OBNARUZHIT, CHTO NEOBHODIMO NESKOLXKO RAZ PROSLEDITX ZA RABOTOJ ALGORITMA, CHTOBY DEJSTVITELXNO OSOZNATX, CHTO ZHE PROISHODIT. \alg B.(oSCILLIRUYUSHCHAYA SORTIROVKA S PEREKRESTNYM RASPREDELENIEM.) eTOT ALGORITM BERET PERVONACHALXNYE OTREZKI I RASPREDELYAET IH NO LENTAM, VREMYA OT VREMENI PRERYVAYA PROCESS RASPREDELENIYA, CHTOBY SLITX SODERZHIMOE NEKOTORYH LENT. \picture{rIS.~77. oSCILLIRUYUSHCHAYA SORTIROVKA S PEREKRESTNYM RASPREDELENIEM.} v ALGORITME ISPOLXZUETSYA $P\hbox{-PUTEVOE}$ SLIYANIE I PREDPOLAGAETSYA, CHTO ESTX $T=P+1\ge 3$~LENTOCHNYH USTROJSTV (NE SCHITAYA USTROJSTVA, KOTOROE MOZHET BYTX NEOBHODIMO DLYA HRANENIYA ISHODNYH DANNYH). lENTOCHNYE USTROJSTVA DOLZHNY DOPUSKATX CHTENIE KAK V PRYAMOM, TAK I V OBRATNOM NAPRAVLENII; ONI OBOZNACHENY CHISLAMI~0, 1,~\dots, $P$. iSPOLXZUYUTSYA SLEDUYUSHCHIE MASSIVY: {\medskip\narrower \item{$|D|[j]$,} $0\le j \le P$---CHISLO FIKTIVNYH OTREZKOV, NALICHIE KOTORYH PREDPOLAGAETSYA V KONCE LENTY~$j$. \item{$|A|[l, j]$,} $0\le l \le L$, $0\le j \le P$. zDESX~$L$---DOSTATOCHNO BOLXSHOE CHISLO, TAKOE, CHTO BUDET VVEDENO NE BOLEE~$P^{L+1}$ NACHALXNYH OTREZKOV. eSLI~$|A|[l, j]=k \ge 0$, TO NA LENTE~$j$ IMEETSYA OTREZOK NOMINALXNOJ DLINY~$P^k$, SOOTVETSTVUYUSHCHIJ "UROVNYU~$l$" RABOTY ALGORITMA. eTOT OTREZOK VOZRASTAYUSHCHIJ, ESLI $k$~CHETNO, I UBYVAYUSHCHIJ, ESLI $k$~NECHETNO. $|A|[l, j]=-1$~OZNACHAET, CHTO NA UROVNE~$l$ LENTA~$j$ NE ISPOLXZUETSYA. \medskip} \noindent iNSTRUKCIYA "ZAPISATX NACHALXNYJ OTREZOK NA LENTU~$j$" YAVLYAETSYA SOKRASHCHENNYM OBOZNACHENIEM SLEDUYUSHCHIH DEJSTVIJ: %%374 {\medskip\narrower \noindent uSTANOVITX~$|A|[l, j]\asg 0$. eSLI ISHODNYE DANNYE ISCHERPANY, TO UVELICHITX~$|D|[j]$ NA~1; V PROTIVNOM SLUCHAE ZAPISATX OTREZOK NA LENTU~$j$ (V VOZRASTAYUSHCHEM PORYADKE). \medskip} \noindent iNSTRUKCIYA "SLITX NA LENTU~$j$" ISPOLXZUETSYA KAK KRATKOE OBOZNACHENIE SLEDUYUSHCHIH DEJSTVIJ: {\medskip\narrower \noindent eSLI~$|D|[i]>0$ DLYA VSEH~$i\ne j$, TO UMENXSHITX~$|D|[i]$ NA~1 PRI VSEH~$i\ne j$ I UVELICHITX~$|D|[j]$ NA~1. v PROTIVNOM SLUCHAE SLITX ODIN OTREZOK NA LENTU~$j$ SO VSEH LENT~$i\ne j$, TAKIH, CHTO~$|D|[i]=0$, I UMENXSHITX~$|D|[i]$ NA~1 DLYA VSEH OSTALXNYH~$i\ne j$. \medskip} \st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$|D|[j]\asg 0$ PRI~$0\le j \le P$. zATEM ZAPISATX NACHALXNYJ OTREZOK NA LENTU~$j$ PRI~$1 \le j \le P$. uSTANOVITX~$|A|[0,0]\asg -1$, $l\asg 0$, $q\asg 0$. \st[vVOD ZAVERSHEN?] (v |TOT MOMENT LENTA~$q$ PUSTA I VSYAKAYA DRUGAYA LENTA SODERZHIT SAMOE BOLXSHEE ODIN OTREZOK.) eSLI ESHCHE ESTX ISHODNYE DANNYE, PEREJTI K SHAGU~\stp{3}. oDNAKO ESLI VVOD ISCHERPAN, TO PEREMOTATX VSE LENTY~$j\ne q$, TAKIE, CHTO $|A|[0, j]$~CHETNO; ZATEM SLITX NA LENTU~$q$, CHITAYA VSE TOLXKO CHTO PEREMOTANNYE LENTY V PRYAMOM NAPRAVLENII, A OSTALXNYE LENTY---V OBRATNOM. eTIM ZAVERSHAETSYA SORTIROVKA; REZULXTAT NAHODITSYA NA LENTE~$q$ V VOZRASTAYUSHCHEM PORYADKE. \st[nACHATX NOVYJ UROVENX.] uSTANOVITX~$l \asg l+1$, $r \asg q$, $s \asg 0$ I~$q\asg (q+1) \bmod T$. zAPISATX NACHALXNYJ OTREZOK NA LENTU~$(q+j) \bmod T$ PRI~$1 \le j \le T-2$. (tAKIM OBRAZOM, NACHALXNYE OTREZKI ZAPISYVAYUTSYA NA VSE LENTY, KROME LENT~$q$ I~$r$.) uSTANOVITX~$|A|[l, q]\asg -1$ I~$|A|[l, r] \asg -1$. \st[mOZHNO LI SLIVATX?] eSLI~$|A|[l-1, q]\ne s$, VERNUTXSYA K SHAGU~\stp{3}. \st[sLIYANIE.] (v |TOT MOMENT $|A|[l-1, q]=|A|[l, j]=s$ PRI VSEH~$j\ne q$, $j \ne r$.) sLITX NA LENTU~$r$. (sM.\ VYSHE OPREDELENIE |TOJ OPERACII.) zATEM USTANOVITX~$s \asg s+1$, $l \asg l-1$, $|A|[l, r]\asg s$ I~$|A|[l, q] \asg -1$. uSTANOVITX~$r \asg (2q-r)\bmod T$. (v OBSHCHEM SLUCHAE MY IMEEM~$r=(q-1)\bmod T$, ESLI $s$~CHETNO, I~$r=(q+1) \bmod T$, ESLI $s$~NECHETNO.) \st[zAKONCHEN LI UROVENX?] eSLI~$l=0$, PEREJTI K~\stp{2}. v PROTIVNOM SLUCHAE, ESLI~$|A|[l, j]=s$ DLYA VSEH~$j\ne q$ I~$j\ne r$, TO PEREJTI K~\stp{4}. v PROTIVNOM SLUCHAE VERNUTXSYA K~\stp{3}. \algend chTOBY POKAZATX PRAVILXNOSTX |TOGO ALGORITMA, MY MOZHEM ISPOLXZOVATX DOKAZATELXSTVO TIPA "REKURSIVNOJ INDUKCII", TAK ZHE KAK MY DELALI DLYA ALGORITMA~2.3.1T. pREDPOLOZHIM, CHTO MY NACHINAEM S SHAGA~B3 S~$l=l_0$, $q=q_0$, $s_+=|A|[l_0, (q_0+1)\bmod T]$ I~$s_-=|A|[l_0, (q_0-1)\bmod T]$, I DOPUSTIM, KROME TOGO, CHTO LIBO~$s_+=0$, LIBO~$s_-=1$, LIBO~$s_+=2$, LIBO~$s_-=3$, LIBO~$\ldots\,$. mOZHNO PROVERITX PO INDUKCII, CHTO ALGORITM V KONCE KONCOV PRIDET K SHAGU~B5, NE IZMENIV S NULEVOJ PO~$l\hbox{-YU}$ STROKI~|A| I SO ZNACHENIYAMI %%375 PEREMENNYH~$l=l_0+1$, $q=q_0\pm 1$, $r=q_0$ I~$s=s_+ \ror s_-$, PRICHEM MY VYBIRAEM ZNAK~$+$, ESLI~$s_+=0 \ror (s_+=2 \rand s_-\ne 1) \ror (s_+=4 \rand s_-\ne 1, 3) \ror \ldots$, I MY VYBIRAEM ZNAK~$-$, ESLI~$(s_-=1 \rand s_+=0) \ror (s_-=3 \rand s_+\ne 0, 2)\ror \ldots\,$. pRIVEDENNYJ ZDESX NABROSOK DOKAZATELXSTVA NE OCHENX |LEGANTEN, NO I SAM ALGORITM SFORMULIROVAN V VIDE, KOTORYJ BOLXSHE GODITSYA DLYA REALIZACII, CHEM DLYA PROVERKI PRAVILXNOSTI. \picture{rIS.~78 eFFEKTIVNOSTX OSCILLIRUYUSHCHEJ SORTIROVKI, ISPOLXZUYUSHCHEJ METOD ALGORITMA~B I~UPR.~3.} nA RIS.~78 POKAZANA |FFEKTIVNOSTX ALGORITMA~B, VYRAZHENNAYA SREDNIM CHISLOM SLIYANIJ KAZHDOJ ZAPISI V ZAVISIMOSTI OT~$S$---CHISLA NACHALXNYH OTREZKOV, PRICHEM PREDPOLAGAETSYA, CHTO NACHALXNYE OTREZKI PRIBLIZITELXNO RAVNY PO DLINE. (sOOTVETSTVUYUSHCHIE GRAFIKI DLYA MNOGOFAZNOJ I KASKADNOJ SORTIROVKI PRIVEDENY NA RIS.~70 I~74.) pRI PODGOTOVKE RIS.~78 UCHTENO NEBOLXSHOE USOVERSHENSTVOVANIE, UPOMYANUTOE V UPR.~3. %%376 \section pRYAMOE CHTENIE. sHEMA OSCILLIRUYUSHCHEJ SORTIROVKI, PO-VIDIMOMU, TREBUET VOZMOZHNOSTI OBRATNOGO CHTENIYA, POSKOLXKU PRIHODITSYA GDE-TO NAKAPLIVATX DLINNYE OTREZKI PO MERE TOGO, KAK MY SLIVAEM VNOVX VVEDENNYE KOROTKIE OTREZKI. tEM NE MENEE m.~a.~gOTC [Proc. AFIPS Spring Jt. sOTR. Conf.; {\bf 25} (1964), 599--607] NASHEL SPOSOB VYPOLNITX OSCILLIRUYUSHCHUYU SORTIROVKU, ISPOLXZUYA TOLXKO PRYAMOE CHTENIE I PROSTUYU PEREMOTKU. eGO METOD V KORNE OTLICHAETSYA OT OSTALXNYH SHEM, KOTORYE MY VIDELI V |TOJ GLAVE, POSKOLXKU a)~DANNYE INOGDA ZAPISYVAYUTSYA V NACHALO LENTY, PRICHEM PREDPOLAGAETSYA, CHTO DANNYE, NAHODYASHCHIESYA V \emph{SEREDINE} |TOJ LENTY, NE RAZRUSHAYUTSYA; b)~VSE NACHALXNYE STROKI IMEYUT FIKSIROVANNUYU MAKSIMALXNUYU DLINU. uSLOVIE~(a) NARUSHAET SVOJSTVO "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA", KOTOROE, KAK MY PREDPOLOZHILI, YAVLYAETSYA HARAKTERISTIKOJ PRYAMOGO CHTENIYA, ODNAKO ONO MOZHET BYTX NADEZHNO REALIZOVANO, ESLI MEZHDU OTREZKAMI OSTAVLYATX DOSTATOCHNOE KOLICHESTVO CHISTOJ LENTY I ESLI V NUZHNYE MOMENTY PRENEBRECHX "OSHIBKAMI CHETNOSTI". uSLOVIE~(b) OKAZYVAETSYA DO NEKOTOROJ STEPENI PROTIVORECHASHCHIM |FFEKTIVNOMU ISPOLXZOVANIYU VYBORA S ZAMESHCHENIEM. oSCILLIRUYUSHCHAYA SORTIROVKA gOTCA S PRYAMYM CHTENIEM IMEET ODNO TEMNOE PYATNO---|TO ODIN IZ PERVYH ALGORITMOV, KOTORYJ BYL ZAPATENTOVAN KAK ALGORITM, A NE KAK FIZICHESKOE USTROJSTVO [U.~S.~Patent~3380029 (23~APRELYA 1968)]. eSLI POLOZHENIE NE IZMENITSYA, TO |TO OZNACHAET, CHTO ALGORITM NELXZYA ISPOLXZOVATX V PROGRAMME BEZ RAZRESHENIYA VLADELXCA PATENTA. mETOD b|NCHERA (OSCILLIRUYUSHCHAYA SORTIROVKA S OBRATNYM CHTENIEM) BYL ZAPATENTOVAN IBM NESKOLXKIMI GODAMI POZZHE. [tAKIM OBRAZOM, NASTUPIL KONEC |RY, KOGDA UDOVOLXSTVIE OT OTKRYTIYA NOVOGO ALGORITMA SCHITALOSX DOSTATOCHNYM VOZNAGRAZHDENIEM! tAK KAK PROGRAMMIROVANIE NEOTDELIMO OT SOZDANIYA MASHINY, A PROGRAMMY DLYA evm TEPERX STOYAT DENEG, TO PATENTOVANIE ALGORITMOV YAVLYAETSYA NEIZBEZHNYM. kONECHNO, DEJSTVIYA NEDALXNOVIDNYH LYUDEJ, SOHRANYAYUSHCHIH NOVYE ALGORITMY V STROGOM SEKRETE, ZNACHITELXNO HUZHE, CHEM SHIROKAYA DOSTUPNOSTX ALGORITMOV, KOTORYE YAVLYAYUTSYA SOBSTVENNOSTXYU V TECHENIE LISHX OGRANICHENNOGO VREMENI.] cENTRALXNAYA IDEYA V METODE gOTCA SOSTOIT V TAKOM ISPOLXZOVANII LENT, CHTOBY KAZHDAYA LENTA NACHINALASX S OTREZKA OTNOSITELXNOJ DLINY~1, ZA KOTORYM SLEDOVAL BY OTREZOK OTNOSITELXNOJ DLINY~$P$, ZATEM~$P^2$ I~T.~D. nAPRIMER, ESLI~$T=5$, TO SORTIROVKA NACHINAETSYA SLEDUYUSHCHIM OBRAZOM ("."~UKAZYVAET TEKUSHCHEE POLOZHENIE GOLOVKI CHTENIYA-ZAPISI NA KAZHDOJ LENTE): %%377 \ctable{ #\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip &\hfil$#$\hfil\bskip&#\hfil\cr & oPERACIYA & T1 & T2 & T3 & T4 & T5 & \hbox{sTOIMOSTX} & pRIMECHANIYA \cr fAZA~1. & rASPREDELENIE& A_1 & .A_1 & .A_1 & .A_1 & A_1. & 5& [T5 NE PEREMATYVAETSYA]\cr fAZA~2. & sLIYANIE & A_1. & A_1. & A_1. & A_1. & A_1A_4. & 4& [pEREMOTKA VSEH LET]\cr fAZA~3. & rASPREDELENIE& A_1 & .A_1 & .A_1 & A_1. & .A_1A_4 & 4& [T4 NE PEREMATYVAETSYA]\cr fAZA~4. & sLIYANIE & A_1. & A_1. & A_1. & A_1A_4.& A_1.A_4 & 4& [pEREMOTKA VSEH LENT]\cr fV|A~5. & rASPREDELENIE& A_1 & .A_1 & A_1. & .A_1A_4& .A_1A_4 & 4& [T3 NE PEREMATYVAETSYA]\cr fAZA~6. & sLIYANIE & A_1. & A_1. & A_1A_4.& A_1.A_4& A_1.A_4 & 4& [pEREMOTKA VSEH LENT]\cr fAZA~7. & rASPREDELENIE& A_1 & A_1. & .A_1A_4& .A_1A_4& .A_1A_4 & 4& [T2 NE PEREMATYVAETSYA]\cr fAZA~8. & sLIYANIE & A_1. & A_1A_4. & A_1.A_4& A_1.A_4& A_1.A_4 & 4& [pEREMOTKA VSEH LENT]\cr FAZA~9. & rASPREDELENIE& A_1. & .A_1A_4 & .A_1A_4& .A_1A_4& .A_1A_4 & 4& [T1 NE PEREMATYVAETSYA]\cr fAZA~10.& sLIYANIE & A_1A_4. & A_1.A_4 & A_1.A_4& A_1.A_4& A_1.A_4 & 4& [nET PEREMOTKI]\cr fAZA~11.& sLIYANIE & A_1A_4A_{16}. & A_1A_4. & A_1A_4.& A_1A_4.& A_1A_4. & 16& [pEREMOTKA VSEH LENT]\cr } i TAK DALEE. vO VREMYA FAZY~1 LENTA~T1 PEREMATYVAETSYA I ODNOVREMENNO NA~T2 ZAPISYVAYUTSYA ISHODNYE DANNYE, ZATEM PEREMATYVAETSYA~T2 I ODNOVREMENNO NA~T3 ZAPISYVAYUTSYA ISHODNYE DANNYE I~T.~D. v KONCE KONCOV, KOGDA ISHODNYE DANNYE ISCHERPANY, NACHINAYUT POYAVLYATXSYA FIKTIVNYE OTREZKI, I INOGDA NEOBHODIMO VOOBRAZITX, CHTO ONI ZAPISANY YAVNO NA LENTE POLNOJ DLINY. nAPRIMER, ESLI~$S=18$, TO OTREZKI~$A_1$ NA~T4 I~T5 BUDUT FIKTIVNYMI VO VREMYA FAZY~9; NAM PRIDETSYA PRODVINUTXSYA VPERED PO~T4 I~T5 PRI SLIYANII S~T2 I~T3 NA~T1 VO VREMYA FAZY~10, TAK KAK NAM NADO DOBRATXSYA DO OTREZKOV~$A_4$ NA~T4 I~T5 DLYA PODGOTOVKI K FAZE~11. s DRUGOJ STORONY, FIKTIVNYJ OTREZOK~$A_1$ NA~T1 NE OBYAZATELXNO DOLZHEN SUSHCHESTVOVATX YAVNO. tAKIM OBRAZOM, "KONEC IGRY" NESKOLXKO ZAMYSLOVAT. eSHCHE S ODNIM PRIMEROM PRIMENENIYA |TOGO METODA MY VSTRETIMSYA V SLEDUYUSHCHEM PUNKTE. \excercises \ex[22] v TEKSTE IMEETSYA ILLYUSTRACIYA OSCILLIRUYUSHCHEJ SORTIROVKI sOBELYA V EE PERVOZDANNOM VIDE DLYA~$T=5$ I~$S=16$. dAJTE TOCHNOE OPREDELENIE ALGORITMA, V KOTOROM |TA PROCEDURA OBOBSHCHAETSYA I SORTIRUYUTSYA $S=P^L$~NACHALXNYH OTREZKOV NA $T=P+1\ge 3$~LENTAH. pOSTARAJTESX NAJTI ALGORITM, KOTORYJ MOZHET BYTX OCHENX PROSTO OPISAN. \ex[24] eSLI V IZNACHALXNOM METODE sOBELYA $S=6$, TO MY MOGLI BY ZAYAVITX, CHTO~$S=16$ I CHTO IMEETSYA 10~FIKTIVNYH OTREZKOV. tOGDA FAZA~3 V PRIMERE V TEKSTE POMESTILA BY FIKTIVNYE OTREZKI~$A_0$ NA~T4 I~T5; FAZA~4 SLILA BY OTREZKI~$A_1$ NA~T2 I~T3 V~$D_2$ NA~T1; FAZY~5--8 NE DELALI BY NICHEGO; FAZA~9 PORODILA BY~$A_6$ NA~T4. lUCHSHE BY PEREMOTATX~T2 I~T3 SRAZU POSLE FAZY~3 I ZATEM NEMEDLENNO POLUCHATX~$A_6$ NA~T4 S POMOSHCHXYU TREHPUTEVOGO SLIYANIYA. pOKAZHITE, KAK, OSNOVYVAYASX NA |TOJ IDEE, ULUCHSHITX OKONCHANIE ALGORITMA IZ UPR.~1, ESLI~$S$ NE YAVLYAETSYA TOCHNOJ STEPENXYU~$P$. \rex[24] sOSTAVXTE TABLICU, POKAZYVAYUSHCHUYU POVEDENIE ALGORITMA~B, ESLI~$T=3$, PREDPOLAGAYA, CHTO IMEETSYA 9~NACHALXNYH OTREZKOV. pOKAZHITE, CHTO |TA PROCEDURA OCHEVIDNO NE|FFEKTIVNA V ODNOM MESTE, I PREDLOZHITE IZMENENIYA V ALGORITME~B, KOTORYE ISPRAVLYAYUT POLOZHENIE. \ex[21] nA SHAGE~B3 IMEETSYA USTANOVKA KAK~$|A|[l, q]$, TAK I~$|A|[l, r]$ V~$-1$. pOKAZHITE, CHTO ODNA IZ |TIH OPERACIJ VSEGDA LISHNYAYA, TAK KAK SOOTVETSTVUYUSHCHIJ |LEMENT MASSIVA~|A| NIKOGDA NE RASSMATRIVAETSYA. \ex[m25] pUSTX~$S$---CHISLO NACHALXNYH OTREZKOV V IMEYUSHCHIHSYA ISHODNYH DANNYH DLYA ALGORITMA~B. pRI KAKIH ZNACHENIYAH~$S$ NE TREBUETSYA \emph{NI ODNOJ PEREMOTKI} NA SHAGE~B2? %%378 \bye\input style \chapno=5\subchno=4\subsubchno=3\chapnotrue kASKADNOE SLIYANIE, PODOBNO MNOGOFAZNOMU, NACHINAETSYA S "TOCHNOGO RASPREDELENIYA" OTREZKOV PO LENTAM, HOTYA PRAVILA TOCHNOGO RASPREDELENIYA OTLICHNY OT PRAVIL P.~5.4.2. kAZHDAYA STROKA TABLICY PREDSTAVLYAET POLNYJ PROHOD PO \emph{VSEM} DANNYM. pROHOD~2, NAPRIMER, POLUCHAETSYA POSREDSTVOM VYPOLNENIYA PYATIPUTEVOGO SLIYANIYA S~T1, T2, T3, T4, T5 NA~T6, POKA~T5 NE STANET PUSTOJ (PRI |TOM NA~T6 POMESHCHAYUTSYA 15~OTREZKOV OTNOSITELXNOJ DLINY~5), ZATEM CHETYREHPUTEVOGO SLIYANIYA S~T1, T2, T3, T4 NA~T5, ZATEM TREHPUTEVOGO SLIYANIYA NA~T4, DVUHPUTEVOGO SLIYANIYA NA~T3 I, NAKONEC, ODNOPUTEVOGO SLIYANIYA (OPERACII KOPIROVANIYA) S~T1 NA~T2. pROHOD~3 POLUCHAETSYA TAKIM ZHE OBRAZOM PUTEM VYPOLNENIYA SNACHALA PYATIPUTEVOGO SLIYANIYA, POKA ODNA LENTA NE STANET PUSTOJ, ZATEM CHETYREHPUTEVOGO I~T.~D. (pOHOZHE, CHTO |TOMU PUNKTU KNIGI SLEDOVALO BY PRISVOITX NOMER~5.4.3.2.1, A NE~5.4.3!) yaSNO, CHTO OPERACII KOPIROVANIYA IZLISHNI, I IH MOZHNO BYLO BY OPUSTITX. fAKTICHESKI, ODNAKO, V SLUCHAE SHESTI LENT |TO KOPIROVANIE ZANIMAET TOLXKO NEBOLXSHOJ PROCENT VSEGO VREMENI. eLEMENTY, KOTORYE POLUCHAYUTSYA PROSTYM KOPIROVANIEM, OTMECHENY V PRIVEDENNOJ TABLICE ZVEZDOCHKOJ. tOLXKO~25 IZ~950 OBRABATYVAEMYH OTREZKOV PRINADLEZHAT |TOMU KLASSU. bOLXSHAYA CHASTX VREMENI OTVODITSYA PYATIPUTEVOMU I CHETYREHPUTEVOMU SLIYANIYAM. nA PERVYJ VZGLYAD MOZHET POKAZATXSYA, CHTO KASKADNAYA SHEMA---DOVOLXNO PLOHOJ VARIANT V SRAVNENII S MNOGOFAZNOJ, TAK KAK STANDARTNAYA MNOGOFAZNAYA SHEMA ISPOLXZUET VSE VREMYA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, V TO VREMYA KAK KASKADNAYA ISPOLXZUET $(T-1)\hbox{-PUTEVOE}$, $(T-2)\hbox{-PUTEVOE}$, $(T-3)\hbox{-PUTEVOE}$ I~T.~D., NO V DEJSTVITELXNOSTI ONA ASIMPTOTICHESKI \emph{LUCHSHE,} CHEM MNOGOFAZNAYA, DLYA SHESTI I BOLEE LENT! kAK MY VIDELI V P.~5.4.2, VYSOKIJ PORYADOK SLIYANIYA NE YAVLYAETSYA GARANTIEJ |FFEKTIVNOSTI. v TABL.~1 POKAZANY HARAKTERISTIKI VYPOLNENIYA KASKADNOGO SLIYANIYA PO ANALOGII S PODOBNOJ TABLICEJ P.~5.4.2. nETRUDNO VYVESTI "TOCHNYE RASPREDELENIYA" DLYA KASKADNOGO SLIYANIYA. dLYA SHESTI LENT IMEEM $$ \matrix{ \hbox{uROVENX} & T1 & T2 & T3 & T4 & T5 \cr 0 & 1 & 0 & 0 & 0 & 0 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 5 & 4 & 3 & 2 & 1 \cr 3 & 15 & 14 & 12 & 9 & 6 \cr 4 & 55 & 50 & 41 & 29 & 15 \cr 5 & 190 & 175 & 146 & 105 & 55 \cr \multispan{6}\dotfill\cr n & a_n & b_n & c_n & d_n & e_n \cr n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr } \eqno(1) $$ %%344 \htable{tABLICA 1}% {hARAKTER POVEDENIYA KASKADNOGO SLIYANIYA}% {\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr lENTY & \hbox{pROHODY} & \hbox{pROHODY} & \hbox{oTNOSHENIE}\cr & \hbox{(S KOPIROVANIEM)} & \hbox{(BEZ KOPIROVANIYA)} &\hbox{ROSTA}\cr \noalign{\hrule} 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 & 1.6180340\cr 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 & 2.2469796\cr 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 & 2.8793852\cr 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 & 3.5133371\cr 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 & 4.1481149\cr 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 & 4.7833861\cr 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 & 5.4189757\cr 10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 & 6.0547828\cr 20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr \noalign{\hrule} } oTMETIM INTERESNOE SVOJSTVO |TIH CHISEL---IH OTNOSITELXNYE VELICHINY YAVLYAYUTSYA TAKZHE I DLINAMI DIAGONALEJ PRAVILXNOGO $(2T-1)\hbox{-UGOLXNIKA}$. nAPRIMER, PYATX DIAGONALEJ ODINNADCATIUGOLXNIKA NA RIS.~73 IMEYUT OTNOSITELXNYE DLINY, OCHENX BLIZKIE K~190, 175, 146, 105 I~55! mY DOKAZHEM |TOT ZAMECHATELXNYJ FAKT \picture{rIS.~73. gEOMETRICHESKAYA INTERPRETACIYA KASKADNYH CHISEL.} POZDNEE V |TOM PUNKTE, A TAKZHE UVIDIM, CHTO OTNOSITELXNYE VREMENA, ZATRACHIVAEMYE NA $(T-1)\hbox{-PUTEVOE}$ SLIYANIE, $(T-2)\hbox{-PUTEVOE}$ SLIYANIE,~\dots, ODNOPUTEVOE SLIYANIE, PRIBLIZITELXNO PROPORCIONALXNY \emph{KVADRATAM} DLIN |TIH DIAGONALEJ. \section *nACHALXNOE RASPREDELENIE OTREZKOV. eSLI CHISLO NACHALXNYH OTREZKOV V DEJSTVITELXNOSTI NE ESTX CHISLO fIBONACHCHI, MY MOZHEM, KAK OBYCHNO, VSTAVITX FIKTIVNYE OTREZKI. pOVERHNOSTNYJ ANALIZ SITUACII POKAZYVAET, CHTO METOD PRIPISYVANIYA FIKTIVNYH OTREZKOV NESUSHCHESTVEN, TAK KAK KASKADNOE SLIYANIE VSEGDA OSUSHCHESTVLYAET %%345 POLNYE PROHODY; ESLI IMEETSYA 190~NACHALXNYH OTREZKOV, TO KAZHDAYA ZAPISX OBRABATYVAETSYA PYATX RAZ, KAK V PRIVEDENNOM VYSHE PRIMERE, NO ESLI IMEETSYA 191~OTREZOK, TO, OCHEVIDNO, SLEDUET UVELICHITX UROVENX, I TEPERX KAZHDAYA ZAPISX BUDET OBRABATYVATXSYA SHESTX RAZ. k SCHASTXYU, V DEJSTVITELXNOSTI MOZHNO IZBEZHATX TAKOGO REZKOGO SKACHKA. d|VID~e.~fERGYUSON NASHEL SPOSOB TAK RASPREDELITX NACHALXNYE OTREZKI, CHTO MNOGIE OPERACII VO VREMYA PERVOJ \picture{ rIS.~74. eFFEKTIVNOSTX KASKADNOGO SLIYANIYA S RASPREDELENIEM PO ALGORITMU~D. } FAZY SLIYANIYA SVODYATSYA K KOPIROVANIYU SODERZHIMOGO LENTY. eSLI OBOJTI TAKIE KOPIROVANIYA (PROSTO IZMENIV "LOGICHESKIE" NOMERA LENTOCHNYH USTROJSTV PO OTNOSHENIYU K "FIZICHESKIM" NOMERAM, KAK V ALGORITME~5.4.2D), TO POLUCHIM OTNOSITELXNO PLAVNYJ PEREHOD S UROVNYA NA UROVENX, KAK IZOBRAZHENO NA RIS.~74. pREDPOLOZHIM, CHTO $(a, b, c, d, e)$, GDE~$a\ge b \ge c \ge d \ge e$---TOCHNOE RASPREDELENIE. pEREOPREDELIV SOOTVETSTVIE MEZHDU LOGICHESKIMI I FIZICHESKIMI LENTOCHNYMI USTROJSTVAMI, MY MOZHEM PREDSTAVITX, CHTO REALXNOE RASPREDELENIE---|TO~$(e, d, c, b, a)$, %%346 T.~E.~$a$~OTREZKOV NA~T5, $b$~NA~t4 I~T.~D. sLEDUYUSHCHEE TOCHNOE RASPREDELENIE---|TO $(a+b+c+d+e, a+b+c+d, a+b+c, a+b, a)$; I ESLI VVOD ISCHERPYVAETSYA PREZHDE, CHEM MY DOSTIGAEM |TOGO SLEDUYUSHCHEGO UROVNYA, TO BUDEM SCHITATX, CHTO LENTY SODERZHAT SOOTVETSTVENNO~$(D_1, D_2, D_3, D_4, D_5)$ FIKTIVNYH OTREZKOV, GDE $$ \displaynarrow{ D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr } \eqno(2) $$ mY VOLXNY PREDSTAVLYATX SEBE, CHTO |TI FIKTIVNYE OTREZKI POYAVLYAYUTSYA NA LENTAH V LYUBOM UDOBNOM MESTE. pREDPOLAGAETSYA, CHTO PERVYJ PROHOD SLIYANIYA DAST $a$~OTREZKOV POSREDSTVOM PYATIPUTEVOGO SLIYANIYA, ZATEM $b$~OTREZKOV POSREDSTVOM CHETYREHPUTEVOGO I~T.~D. nASHA CELX SOSTOIT V RASPOLOZHENII FIKTIVNYH OTREZKOV TAKIM OBRAZOM, CHTOBY ZAMENITX SLIYANIE KOPIROVANIEM. uDOBNO VYPOLNYATX PERVYJ PROHOD SLIYANIYA SLEDUYUSHCHIM OBRAZOM: 1.~eSLI~$D_4=a$, TO VYCHESTX~$a$ IZ VSEH~$D_1$, $D_2$, $D_3$, $D_4$ I ZAYAVITX, CHTO~T5---REZULXTAT SLIYANIYA. eSLI~$D_40$, VERNUTXSYA K SHAGU~\stp{5}. v PROTIVNOM SLUCHAE UMENXSHITX~$k$ NA~1; ESLI~$k>0$, USTANOVITX~$m\asg |A|[T-j-1]-|A|[T-j]$ I VERNUTXSYA K~\stp{5}, ESLI~$m>0$. v PROTIVNOM SLUCHAE UMENXSHITX~$j$ NA~1; ESLI~$j>0$, PEREJTI K SHAGU~\stp{4}. v PROTIVNOM SLUCHAE UVELICHITX~$i$ NA~1; ESLI~$i|M|[j]$, I POMESTITX VYVODNOJ OTREZOK NA~$|TAPE|[p+1]$. pRODOLZHATX RABOTU, POKA $|TAPE|[p]$ NE STANET PUSTOJ. zATEM PEREMOTATX~$|TAPE|[p]$ I~$|TAPE|[p+1]$. \st[oPUSTITXSYA NA ODIN UROVENX.] uMENXSHITX~$l$ NA~1, USTANOVITX~$|FIRST|\asg 0$, USTANOVITX $(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (k |TOMU MOMENTU VSE~|D| I~|M|---NULI I TAKOVYMI OSTANUTSYA.) vERNUTXSYA K~\stp{8}. \algend shAGI~C1--C6 |TOGO ALGORITMA VYPOLNYAYUT RASPREDELENIE, SHAGI~C7--C9 VYPOLNYAYUT SLIYANIE; |TI DVE CHASTI SOVERSHENNO NEZAVISIMY ODNA OT DRUGOJ, I MOZHNO BYLO BY HRANITX~$|M|[k]$ I~$|AA|[k+1]$ V ODNIH I TEH ZHE YACHEJKAH PAMYATI. \picture{rIS.~75. kASKADNOE SLIYANIE SO SPECIALXNYM RASPREDELENIEM.} \section *aNALIZ KASKADNOGO SLIYANIYA. kASKADNOE SLIYANIE PODDAETSYA ANALIZU S BOLXSHIM TRUDOM, CHEM MNOGOFAZNOE. nO |TOT ANALIZ OSOBENNO INTERESEN, POSKOLXKU SODERZHIT MNOGO ZAMECHATELXNYH FORMUL. nASTOYATELXNO REKOMENDUEM CHITATELYAM, INTERESUYUSHCHIMSYA DISKRETNOJ MATEMATIKOJ, SAMOSTOYATELXNO PROANALIZIROVATX KASKADNOE RASPREDELENIE, PREZHDE CHEM CHITATX DALXSHE, VEDX CHISLA %%350 IMEYUT TAK MNOGO NEOBYCHNYH SVOJSTV, OTKRYVATX KOTORYE---ODNO UDOVOLXSTVIE! mY OBSUDIM ZDESX LISHX ODIN IZ MNOGIH PODHODOV, OBRASHCHAYA OSOBOE VNIMANIE NA METODY POLUCHENIYA REZULXTATOV. dLYA UDOBSTVA RASSMOTRIM SLUCHAJ SHESTI LENT. pRI |TOM BUDEM STARATXSYA POLUCHITX FORMULY, KOTORYE OBOBSHCHAYUTSYA NA SLUCHAJ LYUBOGO~$T$. sOOTNOSHENIYA~(1) PRIVODYAT K PERVOJ OSNOVNOJ SISTEME: $$ \eqalignter{ a_n &= a_n &=\perm{0}{0}a_n,\cr b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr } \eqno(4) $$ oBOZNACHIM~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ I OPREDELIM MNOGOCHLENY $$ \eqalignno{ q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k} = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr } $$ rEZULXTAT~(4) KRATKO MOZHNO ISTOLKOVATX TAK, CHTO~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ SVODYATSYA K KONECHNYM SUMMAM, SOOTVETSTVUYUSHCHIM GRANICHNYM USLOVIYAM, A IMENNO ZNACHENIYAM~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots, KOTORYE POYAVLYAYUTSYA V~(4) (PRI NEBOLXSHIH~$n$), NO NE V~$A(z)$. chTOBY POLUCHITX PODHODYASHCHIE GRANICHNYE USLOVIYA, PRIMENIM REKURRENTNOE SOOTNOSHENIE V OBRATNUYU STORONU DLYA OTRICATELXNYH UROVNEJ DO UROVNYA~$-8$: \ctable{ \hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr \hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr 0 & 1 & 0 & 0 & 0 & 0\cr -1 & 0 & 0 & 0 & 0 & 1\cr -2 & 1 & -1 & 0 & 0 & 0\cr -3 & 0 & 0 & 0 & -1 & 2\cr -4 & 2 & -3 & 1 & 0 & 0\cr -5 & 0 & 0 & 1 & -4 & 5\cr -6 & 5 & -9 & 5 & -1 & 0\cr -7 & 0 & -1 & 6 & -14 & 14\cr -8 & 14 & -28 & 20 & -7 & 1\cr } (dLYA SEMI LENT TABLICA BYLA BY ANALOGICHNOJ, ODNAKO STROKI S NECHETNYMI~$n$ BYLI BY SDVINUTY VPRAVO NA ODIN |LEMENT.) tAJNA POSLEDOVATELXNOSTI~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$ MGNOVENNO RASKRYVAETSYA SPECIALISTOM PO INFORMATIKE, TAK KAK %%351 |TA POSLEDOVATELXNOSTX VSTRECHAETSYA V SVYAZI S OCHENX MNOGIMI REKURRENTNYMI ALGORITMAMI (NAPRIMER, V UPR.~2.2.1-4 I FORMULE~2.3.4.4-13)). iTAK, MY PREDPOLAGAEM, CHTO V SLUCHAE $T$~LENT $$ \eqalignrem{ a_{-2n}&=\perm{2n}{n}{1\over n+1} & PRI $0\le n \le T-2$; \cr a_{-2n-1}&=0 & PRI $0\le n \le T-3$.\cr } \eqno(6) $$ chTOBY PROVERITX PRAVILXNOSTX |TOGO PREDPOLOZHENIYA, DOSTATOCHNO POKAZATX, CHTO~(6) I~(4) PRIVODYAT K PRAVILXNYM REZULXTATAM DLYA UROVNEJ~0 I~1. dLYA UROVNYA~1 |TO OCHEVIDNO, A DLYA UROVNYA~0 NAM NADO PROVERITX, CHTO $$ \perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots =\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1} =\delta_{m0} \eqno(7) $$ DLYA~$0\le m \le T-2$. k SCHASTXYU, |TU SUMMU MOZHNO VYCHISLITX STANDARTNYMI METODAMI (|TO "ZADACHA~2", ODIN IZ OSNOVNYH PRIMEROV V TEKSTE P.~4.2.6). tEPERX MOZHNO VYCHISLITX KO|FFICIENTY~$B(z)-q_1(z)A(z)$ I~T.~D. rASSMOTRIM, NAPRIMER, KO|FFICIENT PRI~$z^{2m}$ V~$D(z)-q_3(z)A(z)$. oN RAVEN $$ \eqalign{ \sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k} &=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr &=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr &=(-1)^{m+1}\perm{2+m}{2m}\cr } $$ IZ REZULXTATA "ZADACHI~3" V~P.~1.2.6. tAKIM OBRAZOM, MY VYVELI FORMULY $$ \eqalign{ A(z) &=q_0(z)A(z);\cr B(z) &=q_1(z)A(z)-q_0(z);\cr C(z) &=q_2(z)A(z)-q_1(z);\cr D(z) &=q_3(z)A(z)-q_2(z);\cr E(z) &=q_4(z)A(z)-q_3(z).\cr } \eqno (8) $$ kROME TOGO, IMEEM~$e_{n+1}=a_n$; SLEDOVATELXNO, $zA(z)=E(z)$ I $$ A(z)=q_3(z)/(q_4(z)-z). \eqno (9) $$ pROIZVODYASHCHIE FUNKCII BYLI VYRAZHENY PRI POMOSHCHI $q\hbox{-MNOGOCHLENOV}$, PO|TOMU MY HOTIM LUCHSHE IZUCHITX~$q$. v |TOM OTNOSHENII POLEZNO UPR.~1.2.9-15, TAK KAK ONO DAET VYRAZHENIE V ZAMKNUTOM %%352 VIDE, KOTOROE MOZHET BYTX ZAPISANO KAK $$ q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1} \over \sqrt{4-z^2}} \eqno(10) $$ vSE UPROSHCHAETSYA, ESLI TEPERX POLOZHITX~$z=2 \sin\theta$: $$ \eqalignno{ q_m(2\sin\theta)=& {(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr &={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr } $$ (eTO SOVPADENIE ZASTAVLYAET DUMATX, CHTO MNOGOCHLENY~$q_m(z)$ HOROSHO IZVESTNY V MATEMATIKE; I DEJSTVITELXNO, VZGLYANUV V SOOTVETSTVUYUSHCHIE TABLICY, VIDIM, CHTO~$q_m(z)$, PO SUSHCHESTVU, MNOGOCHLEN chEBYSH¸VA VTOROGO RODA, A IMENNO~$(-1)^m U_{2m}(z/2)$ V OBYCHNYH OBOZNACHENIYAH.) tEPERX MOZHNO OPREDELITX KORNI ZNAMENATELYA V~(9): $q_4(2\sin\theta)=2\sin\theta$ SVODITSYA K $$ \cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta. $$ rESHENIYA |TOGO SOOTNOSHENIYA POLUCHAEM, ESLI TOLXKO~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; VSE TAKIE~$\theta$ DAYUT KORNI ZNAMENATELYA V~(9) PRI USLOVII, CHTO~$\cos\theta\ne 0$. (eSLI~$\cos\theta=0$, TO~$q_m(\pm2)=\pm(2m+1)$, NIKOGDA NE RAVNO~$\pm2$.) sLEDOVATELXNO, POLUCHAEM 8~RAZLICHNYH KORNEJ: $$ \displaylines{ q_4(z)-z=0 \qquad \hbox{ PRI } z=2\sin{-5\over 14}\pi,\quad 2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr 2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad 2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr } $$ tAK KAK~$q_4(z)$---MNOGOCHLEN STEPENI~8, MY UCHLI VSE KORNI. pERVYE TRI IZ |TIH ZNACHENIJ DAYUT~$q_3(z)=0$, TAK CHTO~$q_3(z)$ I~$q_4(z)-z$ IMEYUT OBSHCHIM DELITELEM MNOGOCHLEN TRETXEJ STEPENI. oSTALXNYE PYATX KORNEJ UPRAVLYAYUT ASIMPTOTICHESKIM POVEDENIEM KO|FFICIENTOV~$A(z)$, ESLI RAZLOZHITX~(9) V |LEMENTARNYE DROBI. pEREJDYA K RASSMOTRENIYU OBSHCHEGO SLUCHAYA $T$~LENT, POLOZHIM~$\theta_k=(4k+1)\pi/(4T-2)$. pROIZVODYASHCHAYA FUNKCIYA~$A(z)$ DLYA $T\hbox{-LENTOCHNYH}$ KASKADNYH CHISEL PRINIMAET VID $$ {4\over 2T-1}\sum_{-T/2