\input style
\chapno=5\subchno=3\chapnotrue
\def\tape#1{{\hbox{\sl ыЕНТА~#1\/}}\quad}
\subchap {тэх°э▀▀ ёюЁЄшЁютър} %5.4
яРИШЛО ВРЕМЯ ЗАНЯТЬСЯ ИНТЕРЕСНЫМИ ЗАДАЧАМИ, ВОЗНИКАЮЩИМИ В ТОМ СЛУЧАЕ,
КОГДА ЧИСЛО СОРТИРУЕМЫХ ЗАПИСЕЙ ПРЕВЫШАЕТ ОБоЕМ БЫСТРОДЕЙСТВУЮЩЕГО
ОПЕРАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА. тНЕШНЯЯ СОРТИРОВКА В КОРНЕ ОТЛИЧНА
ОТ ВНУТРЕННЕЙ (ХОТЯ В ОБОИХ СЛУЧАЯХ НЕОБХОДИМО РАСПОЛОЖИТЬ ЗАПИСИ
ДАННОГО ФАЙЛА В НЕУБЫВАЮЩЕМ ПОРЯДКЕ), И ОБоЯСНЯЕТСЯ ЭТО ТЕМ, ЧТО ВРЕМЯ
ДОСТУПА К ФАЙЛАМ НА ВНЕШНИХ НОСИТЕЛЯХ НАС ЖЕСТОЧАЙШИМ ОБРАЗОМ ЛИМИТИРУЕТ.
ёТРУКТУРА ДАННЫХ ДОЛЖНА БЫТЬ ТАКОЙ, ЧТОБЫ СРАВНИТЕЛЬНО МЕДЛЕННЫЕ
ПЕРИФЕРИЙНЫЕ ЗАПОМИНАЮЩИЕ УСТРОЙСТВА (ЛЕНТЫ, ДИСКИ, БАРАБАНЫ И Т.~Д.)
МОГЛИ СПРАВИТЬСЯ С ПОТРЕБНОСТЯМИ АЛГОРИТМА СОРТИРОВКИ. яОЭТОМУ
БОЛЬШИНСТВО ИЗУЧЕННЫХ ДО СИХ ПОР МЕТОДОВ ВНУТРЕННЕЙ СОРТИРОВКИ (ВСТАВКА,
 ОБМЕН, ВЫБОР) ФАКТИЧЕСКИ БЕСПОЛЕЗНО ДЛЯ ВНЕШНЕЙ СОРТИРОВКИ;
НЕОБХОДИМО РАССМОТРЕТЬ ВСЮ ПРОБЛЕМУ ЗАНОВО.

яРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ПРЕДНАЗНАЧЕННЫЙ ДЛЯ СОРТИРОВКИ ФАЙЛ СОСТОИТ
ИЗ 5000~ЗАПИСЕЙ $R_1$ $R_2$~\dots{} $R_{5000}$ ДЛИНОЙ ПО 20~СЛОВ (ХОТЯ
КЛЮЧИ~$K_i$ НЕ ОБЯЗАТЕЛЬНО ТАКОЙ ДЛИНЫ). ъАК БЫТЬ, ЕСЛИ ВО ВНУТРЕННЕЙ
ПАМЯТИ ДАННОЙ МАШИНЫ ПОМЕЩАЕТСЯ ОДНОВРЕМЕННО ТОЛЬКО~1000 ИЗ ЭТИХ ЗАПИСЕЙ?

ёРАЗУ НАПРАШИВАЕТСЯ ТАКОЕ РЕШЕНИЕ: НАЧАТЬ С СОРТИРОВКИ КАЖДОГО ИЗ ПЯТИ
ПОДФАЙЛОВ~$R_1$~\dots{} $R_{1000}$, $R_{1001}$~\dots{} $R_{2000}$,~\dots,
$R_{4001}$~\dots{} $R_{5000}$ ПО ОТДЕЛЬНОСТИ И ЗАТЕМ СЛИТЬ ПОЛУЧЕННЫЕ
ПОДФАЙЛЫ. ъ СЧАСТЬЮ, СЛИЯНИЕ ОПЕРИРУЕТ ТОЛЬКО ОЧЕНЬ ПРОСТЫМИ СТРУКТУРАМИ
ДАННЫХ, ИМЕННО ЛИНЕЙНЫМИ СПИСКАМИ, ПРОЙТИ КОТОРЫЕ МОЖНО ПОСЛЕДОВАТЕЛЬНЫМ
ОБРАЗОМ, КАК СТЕКИ ИЛИ ОЧЕРЕДИ. яОЭТОМУ ДЛЯ СЛИЯНИЯ ГОДЯТСЯ САМЫЕ ДЕШЕВЫЕ
ВНЕШНИЕ ЗАПОМИНАЮЩИЕ УСТРОЙСТВА.

ЄОЛЬКО ЧТО ОПИСАННЫЙ ПРОЦЕСС---ВНУТРЕННЯЯ СОРТИРОВКА С ПОСЛЕДУЮЩИМ
"ВНЕШНИМ СЛИЯНИЕМ"---ВЕСЬМА ПОПУЛЯРЕН, И НАШЕ ИЗУЧЕНИЕ ВНЕШНЕЙ СОРТИРОВКИ
СВЕДЕТСЯ В ОСНОВНОМ К ВАРИАЦИЯМ НА ЭТУ ТЕМУ.

тОЗРАСТАЮЩИЕ ПОСЛЕДОВАТЕЛЬНОСТИ ЗАПИСЕЙ, ПОЛУЧАЕМЫЕ НА НАЧАЛЬНОЙ ФАЗЕ
ВНУТРЕННЕЙ СОРТИРОВКИ, В ЛИТЕРАТУРЕ О СОРТИРОВКЕ ЧАСТО НАЗЫВАЮТСЯ
\emph{ЦЕПОЧКАМИ;} ЭТА ТЕРМИНОЛОГИЯ ДОВОЛЬНО ШИРОКО РАСПРОСТРАНЕНА, НО, К
СОЖАЛЕНИЮ, ОНА ПРОТИВОРЕЧИТ ЕЩЕ БОЛЕЕ РАСПРОСТРАНЕННОМУ ИСПОЛЬЗОВАНИЮ
ТЕРМИНА "ЦЕПОЧКА" В ДРУГИХ РАЗДЕЛАХ ВЫЧИСЛИТЕЛЬНОЙ НАУКИ, ГДЕ ОН ОЗНАЧАЕТ
\emph{ПРОИЗВОЛЬНУЮ} ПОСЛЕДОВАТЕЛЬНОСТЬ СИМВОЛОВ. яРИ ИЗУЧЕНИИ ПЕРЕСТА-
%%296
НОВОК УЖЕ БЫЛО ДАНО ВПОЛНЕ ПОДХОДЯЩЕЕ НАЗВАНИЕ ДЛЯ УПОРЯДОЧЕННЫХ
СЕГМЕНТОВ ФАЙЛА, КОТОРЫЕ МЫ ДОГОВОРИЛИСЬ НАЗЫВАТЬ ВОЗРАСТАЮЩИМИ ОТРЕЗКАМИ
ИЛИ ПРОСТО \emph{ОТРЕЗКАМИ.} т СООТВЕТСТВИИ С ЭТИМ БУДЕМ ИСПОЛЬЗОВАТЬ
СЛОВО "ОТРЕЗКИ" ДЛЯ ОБОЗНАЧЕНИЯ УПОРЯДОЧЕННЫХ ЧАСТЕЙ ФАЙЛА. ЄАКИМ ОБРАЗОМ,
ИСПОЛЬЗОВАНИЕ ПОНЯТИЙ "ЦЕПОЧКИ ОТРЕЗКОВ" И "ОТРЕЗКИ ЦЕПОЧЕК" НЕ
ПРИВЕДЕТ НИ К КАКИМ НЕДОРАЗУМЕНИЯМ.

ЁАССМОТРИМ СНАЧАЛА ПРОЦЕСС ВНЕШНЕЙ СОРТИРОВКИ, ИСПОЛЬЗУЮЩЕЙ В КАЧЕСТВЕ
ВСПОМОГАТЕЛЬНОЙ ПАМЯТИ \emph{МАГНИТНЫЕ ЛЕНТЫ.} тЕРОЯТНО, ПРОСТЕЙШИМ И
НАИБОЛЕЕ ПРИВЛЕКАТЕЛЬНЫМ СПОСОБОМ СЛИЯНИЯ С ПРИМЕНЕНИЕМ ЛЕНТ СЛУЖИТ
СБАЛАНСИРОВАННОЕ ДВУХПУТЕВОЕ СЛИЯНИЕ, В ОСНОВЕ КОТОРОГО ЛЕЖИТ ИДЕЯ,
ИСПОЛЬЗОВАВШАЯСЯ РАНЕЕ В АЛГОРИТМАХ~5.2.4N, S И~L. т ПРОЦЕССЕ СЛИЯНИЯ
НАМ ПОТРЕБУЮТСЯ ЧЕТЫРЕ "РАБОЧИЕ ЛЕНТЫ". эА ПРОТЯЖЕНИИ ПЕРВОЙ ФАЗЫ
ВОЗРАСТАЮЩИЕ ОТРЕЗКИ, ПОЛУЧАЕМЫЕ ПРИ ВНУТРЕННЕЙ СОРТИРОВКЕ, ПОМЕЩАЮТСЯ
ПООЧЕРЕДНО НА ЛЕНТЫ~1 И~2 ДО ТЕХ ПОР, ПОКА НЕ ИСЧЕРПАЮТСЯ ИСХОДНЫЕ ДАННЫЕ.
чАТЕМ ЛЕНТЫ~1 И~2 ПЕРЕМАТЫВАЕМ К НАЧАЛУ И СЛИВАЕМ ОТРЕЗКИ, НАХОДЯЩИЕСЯ
НА ЭТИХ ЛЕНТАХ, ПОЛУЧАЯ НОВЫЕ ОТРЕЗКИ, ВДВОЕ ДЛИННЕЕ ИСХОДНЫХ. ¤ТИ НОВЫЕ
ОТРЕЗКИ ЗАПИСЫВАЮТСЯ ПО МЕРЕ ИХ ФОРМИРОВАНИЯ ПОПЕРЕМЕННО НА ЛЕНТЫ~3 И~4.
(хСЛИ НА ЛЕНТЕ~1 НА ОДИН ОТРЕЗОК БОЛЬШЕ, ЧЕМ НА ЛЕНТЕ~2, ТО ПРЕДПОЛАГАЕТСЯ,
 ЧТО ЛЕНТА~2 СОДЕРЖИТ ДОПОЛНИТЕЛЬНЫЙ "ФИКТИВНЫЙ" ОТРЕЗОК ДЛИНЫ~0.) чАТЕМ
ВСЕ ЛЕНТЫ ПЕРЕМАТЫВАЮТСЯ К НАЧАЛУ И СОДЕРЖИМОЕ ЛЕНТ~3 И~4 СЛИВАЕТСЯ В
УДВОЕННЫЕ ПО ДЛИНЕ ОТРЕЗКИ, ЗАПИСЫВАЕМЫЕ ПООЧЕРЕДНО НА ЛЕНТЫ~1 И~2.
яРОЦЕСС ПРОДОЛЖАЕТСЯ (ПРИ ЭТОМ ДЛИНА ОТРЕЗКОВ КАЖДЫЙ РАЗ УДВАИВАЕТСЯ) ДО
ТЕХ ПОР, ПОКА НЕ ОСТАНЕТСЯ ОДИН ОТРЕЗОК (А ИМЕННО ВЕСЬ УПОРЯДОЧЕННЫЙ ФАЙЛ).
 хСЛИ ПОСЛЕ ВНУТРЕННЕЙ СОРТИРОВКИ БЫЛО ПОЛУЧЕНО $S$~ОТРЕЗКОВ,
ПРИЧЕМ~$2^{k-1}<S\le 2^k$, ТО ПРОЦЕДУРА СБАЛАНСИРОВАННОГО
ДВУХПУТЕВОГО СЛИЯНИЯ ПРОИЗВЕДЕТ РОВНО $k=\ceil{\log_2 S}$~ПРОХОДОВ ПО ВСЕМ
ДАННЫМ.

эАПРИМЕР, В РАССМОТРЕННОЙ ВЫШЕ СИТУАЦИИ, КОГДА ТРЕБУЕТСЯ УПОРЯДОЧИТЬ
5000~ЗАПИСЕЙ, А ОБоЕМ ВНУТРЕННЕЙ ПАМЯТИ СОСТАВЛЯЕТ 1000~ЗАПИСЕЙ, МЫ
ИМЕЕМ~$S=5$. эАЧАЛЬНАЯ РАСПРЕДЕЛИТЕЛЬНАЯ ФАЗА ПРОЦЕССА СОРТИРОВКИ
ПОМЕСТИТ ПЯТЬ ОТРЕЗКОВ НА ЛЕНТЫ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\eqalign{
\tape1 & R_1\ldots R_{1000}; R_{2001}\ldots R_{3000}; R_{4001}\ldots
R_{5000}. \cr
\tape2 & R_{1001}\ldots R_{2000};  R_{3001}\ldots R_{4000}.\cr
\tape3 & \hbox{(ПУСТАЯ)}\cr
\tape4 & \hbox{(ПУСТАЯ)}\cr
}
\eqno(1)
$$

яОСЛЕ ПЕРВОГО ПРОХОДА СЛИЯНИЯ НА ЛЕНТАХ~3 И~4 ПОЛУЧАТСЯ БОЛЕЕ ДЛИННЫЕ
ОТРЕЗКИ, ЧЕМ НА ЛЕНТАХ~1 И~2:
%%297
$$
\eqalign{
\tape3 & R_1 \ldots R_{2000}; R_{4001}\ldots R_{5000}.\cr
\tape4 & R_{2001} \ldots R_{4000}.\cr
}
\eqno(2)
$$

т КОНЕЦ ЛЕНТЫ~2 НЕЯВНО ДОБАВЛЯЕТСЯ ФИКТИВНЫЙ ОТРЕЗОК, ТАК ЧТО
ОТРЕЗОК~$R_{4001}\ldots{}R_{5000}$ ПРОСТО КОПИРУЕТСЯ НА ЛЕНТУ~3. яОСЛЕ
ПЕРЕМОТКИ ВСЕХ ЛЕНТ К НАЧАЛУ СЛЕДУЮЩИЙ ПРОХОД ПО ДАННЫМ ПРИВЕДЕТ К ТАКОМУ
РЕЗУЛЬТАТУ:
$$
\eqalign{
\tape1& R_1 \ldots R_{4000}.\cr
\tape2& R_{4001}\ldots R_{5000}.\cr
}
\eqno(3)
$$
(юТРЕЗОК~$R_{4001}\ldots{}R_{5000}$ СНОВА КОПИРУЕТСЯ, НО ЕСЛИ БЫ МЫ НАЧАЛИ
С 8000~ЗАПИСЕЙ, ТО В ЭТОТ МОМЕНТ ЛЕНТА~2 СОДЕРЖАЛА
БЫ~$R_{4001}\ldots{}R_{8000}$.) эАКОНЕЦ, ПОСЛЕ ЕЩЕ ОДНОЙ ПЕРЕМОТКИ НА
ЛЕНТЕ~3 ОКАЖЕТСЯ ОТРЕЗОК~$R_1\ldots{}R_{5000}$, И СОРТИРОВКА ЗАКОНЧИТСЯ.

ёБАЛАНСИРОВАННОЕ СЛИЯНИЕ ЛЕГКО ОБОБЩАЕТСЯ НА СЛУЧАЙ~$T$ ЛЕНТ ДЛЯ
ЛЮБОГО~$T\ge3$. тЫБЕРЕМ ПРОИЗВОЛЬНОЕ ЧИСЛО~$P$, ТАКОЕ, ЧТО~$1\le P < T$, И
РАЗДЕЛИМ $T$~ЛЕНТ НА ДВА "БАНКА": $P$~ЛЕНТ В ЛЕВОМ БАНКЕ И $T-P$~ЛЕНТ В
ПРАВОМ БАНКЕ. ЁАСПРЕДЕЛИМ ИСХОДНЫЕ ОТРЕЗКИ КАК МОЖНО РАВНОМЕРНЕЕ ПО
$P$~ЛЕНТАМ ЛЕВОГО "БАНКА", ЗАТЕМ ВЫПОЛНИМ $P\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ СЛЕВА
НАПРАВО, ПОСЛЕ ЭТОГО---$(T-P)\hbox{-ПУТЕВОЕ}$~СЛИЯНИЕ СПРАВА НАЛЕВО И~Т.~Д.,
 ПОКА СОРТИРОВКА НЕ ЗАВЕРШИТСЯ. юБЫЧНО ЗНАЧЕНИЕ~$P$ ЛУЧШЕ ВСЕГО ВЫБИРАТЬ
РАВНЫМ~$\ceil{T/2}$ (СМ.~УПР.~3, 4).

яРИ~$T=4$, $P=2$ ИМЕЕМ ЧАСТНЫЙ СЛУЧАЙ---СБАЛАНСИРОВАННОЕ ДВУХПУТЕВОЕ СЛИЯНИЕ.
 тНОВЬ РАССМОТРИМ ПРЕДЫДУЩИЙ ПРИМЕР, ИСПОЛЬЗУЯ БОЛЬШЕЕ КОЛИЧЕСТВО ЛЕНТ;
ПОЛОЖИМ~$T=6$ И~$P=3$. эАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ТЕПЕРЬ БУДЕТ ТАКИМ:
$$
\eqalign{
\tape1 & R_1\ldots R_{1000}; R_{3001}\ldots R_{4000}.\cr
\tape2 & R_{1001} \ldots R_{2000}; R_{4001}\ldots R_{5000}.\cr
\tape3 & R_{2001} \ldots R_{3000}.\cr
}
\eqno(4)
$$
яЕРВЫЙ ПРОХОД СЛИЯНИЯ ПРИВЕДЕТ К
$$
\eqalign{
\tape4 & R_1 \ldots R_{3000}.\cr
\tape5 & R_{3001}\ldots R_{5000}.\cr
\tape6 & \hbox{(ПУСТАЯ)}\cr
}
\eqno(5)
$$
(яРЕДПОЛАГАЕТСЯ, ЧТО НА ЛЕНТЕ~3 ПОМЕЩЕН ФИКТИВНЫЙ ОТРЕЗОК.) эА ВТОРОМ
ПРОХОДЕ СЛИЯНИЯ РАБОТА ЗАВЕРШАЕТСЯ И
ОТРЕЗКИ~$R_1\ldots R_{5000}$ ПОМЕЩАЮТСЯ НА ЛЕНТУ~1. ¤ТОТ ЧАСТНЫЙ
СЛУЧАЙ~$T=6$ ЭКВИВАЛЕНТЕН~$T=5$, ТАК КАК ШЕСТАЯ ЛЕНТА ИСПОЛЬЗУЕТСЯ ЛИШЬ
ПРИ~$S\ge7$.
%%298

ЄРЕХПУТЕВОЕ СЛИЯНИЕ ЗАТРАЧИВАЕТ ФАКТИЧЕСКИ НЕСКОЛЬКО БОЛЬШЕ ВРЕМЕНИ
ЦЕНТРАЛЬНОГО ПРОЦЕССОРА, ЧЕМ ДВУХПУТЕВОЕ, НО ОНО ОБЫЧНО ПРЕНЕБРЕЖИМО МАЛО
ПО СРАВНЕНИЮ С ВРЕМЕНЕМ, НЕОБХОДИМЫМ ДЛЯ ЧТЕНИЯ, ЗАПИСИ И ПЕРЕМОТКИ
ЛЕНТЫ; МЫ ДОВОЛЬНО ХОРОШО ОЦЕНИМ ВРЕМЯ ВЫПОЛНЕНИЯ СОРТИРОВКИ, ЕСЛИ ПРИМЕМ
ВО ВНИМАНИЕ ТОЛЬКО СУММАРНУЮ ВЕЛИЧИНУ ПЕРЕМЕЩЕНИЙ ЛЕНТ. т ПРЕДЫДУЩЕМ
ПРИМЕРЕ ((4) И~(5)) ТРЕБУЮТСЯ ТОЛЬКО ДВА ПРОХОДА ПО ДАННЫМ В СРАВНЕНИИ С
ТРЕМЯ ПРОХОДАМИ ПРИ~$T=4$. ЄАКИМ ОБРАЗОМ, СЛИЯНИЕ ПРИ~$T=6$ ЗАЙМЕТ ОКОЛО
ДВУХ ТРЕТЕЙ ВРЕМЕНИ ПО ОТНОШЕНИЮ К ПРЕДЫДУЩЕМУ СЛУЧАЮ.

ёБАЛАНСИРОВАННОЕ СЛИЯНИЕ КАЖЕТСЯ ОЧЕНЬ ПРОСТЫМ И ЕСТЕСТВЕННЫМ. эО ЕСЛИ
ПРИГЛЯДЕТЬСЯ ВНИМАТЕЛЬНЕЕ, ТО СРАЗУ ВИДНО, ЧТО ЭТО НЕ НАИЛУЧШИЙ СПОСОБ В
РАЗОБРАННЫХ ВЫШЕ ЧАСТНЫХ СЛУЧАЯХ. тМЕСТО ТОГО ЧТОБЫ ПЕРЕХОДИТЬ ОТ~(1)
К~(2) И ПЕРЕМАТЫВАТЬ ВСЕ ЛЕНТЫ, НАМ СЛЕДОВАЛО ОСТАНОВИТЬ ПЕРВОЕ СЛИЯНИЕ,
 КОГДА ЛЕНТЫ~3 И~4 СОДЕРЖАЛИ СООТВЕТСТВЕННО~$R_1$~\dots $R_{2000}$ И
 $R_{2001}$~\dots $R_{4000}$, А ЛЕНТА~1 БЫЛА ГОТОВА К
СЧИТЫВАНИЮ~$R_{4001}$~\dots $R_{5000}$. чАТЕМ ЛЕНТЫ~2, 3, 4 МОГЛИ БЫТЬ
ПЕРЕМОТАНЫ К НАЧАЛУ, И СОРТИРОВКА ЗАВЕРШИЛАСЬ БЫ ТРЕХПУТЕВЫМ СЛИЯНИЕМ НА
ЛЕНТУ~2. юБЩЕЕ ЧИСЛО ЗАПИСЕЙ, ПРОЧИТАННЫХ С ЛЕНТЫ В ХОДЕ ЭТОЙ ПРОЦЕДУРЫ,
 СОСТАВИЛО БЫ~$4000+5000=9000$ ПРОТИВ~$5000+5000+5000=15000$ В
СБАЛАНСИРОВАННОЙ СХЕМЕ. ёООБРАЗИТЕЛЬНАЯ МАШИНА МОГЛА БЫ ПОСТИЧЬ И ЭТО!

шМЕЯ ПЯТЬ ОТРЕЗКОВ И ЧЕТЫРЕ ЛЕНТЫ, МОЖНО ПОСТУПИТЬ ЕЩЕ ЛУЧШЕ, РАСПРЕДЕЛИВ
ОТРЕЗКИ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\eqalign{
\tape1 & R_1 \ldots R_{1000}; R_{3001} \ldots  R_{4000}.\cr
\tape2 & R_{1001} \ldots R_{2000};  R_{4001} \ldots R_{5000}.\cr
\tape3 & R_{2001} \ldots R_{3000}.\cr
\tape4 & \hbox{(ПУСТАЯ)}.\cr
}
$$

ЄЕПЕРЬ, ВЫПОЛНИВ ТРЕХПУТЕВОЕ СЛИЯНИЕ НА ЛЕНТУ~4, ЗАТЕМ ПЕРЕМОТКУ ЛЕНТ~3
И~4 С ПОСЛЕДУЮЩИМ ТРЕХПУТЕВЫМ СЛИЯНИЕМ НА ЛЕНТУ~3, МОЖНО БЫЛО БЫ ЗАВЕРШИТЬ
СОРТИРОВКУ, ПРОЧИТАВ ВСЕГО $3000+5000=8000$~ЗАПИСЕЙ.

эАКОНЕЦ, ЕСЛИ БЫ МЫ ИМЕЛИ ШЕСТЬ ЛЕНТ, ТО МОГЛИ БЫ, КОНЕЧНО, ЗАПИСАТЬ
ИСХОДНЫЕ ОТРЕЗКИ НА ЛЕНТЫ~1--5 И ЗАКОНЧИТЬ СОРТИРОВКУ ЗА ОДИН ПРОХОД,
ВЫПОЛНИВ ПЯТИПУТЕВОЕ СЛИЯНИЕ НА ЛЕНТУ~6. ЁАССМОТРЕНИЕ ЭТИХ СЛУЧАЕВ
ПОКАЗЫВАЕТ, ЧТО ПРОСТОЕ СБАЛАНСИРОВАННОЕ СЛИЯНИЕ НЕ ЯВЛЯЕТСЯ НАИЛУЧШИМ, И
БЫЛО БЫ ИНТЕРЕСНО ПОИСКАТЬ УЛУЧШЕННЫЕ СХЕМЫ СЛИЯНИЯ.

т ПОСЛЕДУЮЩИХ ПУНКТАХ ЭТОЙ ГЛАВЫ ВНЕШНЯЯ СОРТИРОВКА ИССЛЕДУЕТСЯ БОЛЕЕ
ГЛУБОКО. т П.~5.4.1 РАССМАТРИВАЕТСЯ ФАЗА ВНУТРЕННЕЙ СОРТИРОВКИ,
ПОРОЖДАЮЩАЯ НАЧАЛЬНЫЕ ОТРЕЗКИ; ОСОБЫЙ ИНТЕРЕС ПРЕДСТАВЛЯЕТ ТЕХНИКА "ВЫБОРА
С ЗАМЕЩЕНИЕМ", КОТОРАЯ ИСПОЛЬЗУЕТ ПОРЯДОК, ПРИСУТСТВУЮЩИЙ В БОЛЬШИНСТВЕ
ДАННЫХ,
%%299
ЧТОБЫ ПОРОДИТЬ ДЛИННЫЕ ОТРЕЗКИ, ЗНАЧИТЕЛЬНО ПРЕВОСХОДЯЩИЕ ЕМКОСТЬ
ВНУТРЕННЕЙ ПАМЯТИ. т П.~5.4.1 ОБСУЖДАЮТСЯ ТАКЖЕ, СТРУКТУРЫ ДАННЫХ, УДОБНЫЕ
ДЛЯ ЦЕЛЕЙ МНОГОПУТЕВОГО СЛИЯНИЯ.

тАЖНЕЙШИЕ СХЕМЫ СЛИЯНИЯ ОБСУЖДАЮТСЯ В П.~5.4.2---5.4.5. яОКА МЫ НЕ ВСТУПИМ В
ЕДИНОБОРСТВО С ГРУБОЙ ДЕЙСТВИТЕЛЬНОСТЬЮ НАСТОЯЩИХ ЛЕНТ И РЕАЛЬНЫХ
СОРТИРУЕМЫХ ДАННЫХ, ДЛЯ НАС ЛУЧШЕ, ИЗУЧАЯ ХАРАКТЕРИСТИКИ ЭТИХ СХЕМ, ИМЕТЬ
ВЕСЬМА НАИВНОЕ ПРЕДСТАВЛЕНИЕ О ЛЕНТОЧНОЙ СОРТИРОВКЕ. эАПРИМЕР, МОЖНО С
ЛЕГКОЙ ДУШОЙ ПОЛАГАТЬ (КАК МЫ ДЕЛАЛИ ДО СИХ ПОР), ЧТО ПЕРВОНАЧАЛЬНЫЕ
ИСХОДНЫЕ ЗАПИСИ ПОЯВЛЯЮТСЯ ВОЛШЕБНЫМ ОБРАЗОМ В ТЕЧЕНИЕ ПЕРВОЙ
РАСПРЕДЕЛИТЕЛЬНОЙ ФАЗЫ; НА САМОМ ДЕЛЕ ОНИ ВЕРОЯТНО, БУДУТ ЗАНИМАТЬ ОДНУ
ИЗ НАШИХ ЛЕНТ И, БЫТЬ МОЖЕТ, ДАЖЕ ЦЕЛИКОМ ЗАПОЛНЯТ НЕСКОЛЬКО БОБИН, ТАК
КАК ЛЕНТА НЕ БЕСКОНЕЧНА! ыУЧШЕ ВСЕГО ПРЕНЕБРЕЧЬ ПОДОБНЫМИ ТЕХНИЧЕСКИМИ
ДЕТАЛЯМИ ДО ТЕХ ПОР, ПОКА НЕ БУДЕТ ДОСТИГНУТО "АКАДЕМИЧЕСКОЕ"
ПОНИМАНИЕ КЛАССИЧЕСКИХ СХЕМ СЛИЯНИЯ. чАТЕМ В П.~5.4.6 МЫ "ВЕРНЕМСЯ
НА ЗЕМЛЮ", РАССМОТРЕВ ПРАКТИЧЕСКИЕ ОГРАНИЧЕНИЯ, КОТОРЫЕ СИЛЬНО  ВЛИЯЮТ НА
ВЫБОР СХЕМЫ СЛИЯНИЯ. т П.~5.4.6 СРАВНИВАЮТСЯ ОСНОВНЫЕ СХЕМЫ СЛИЯНИЯ ИЗ
П.~5.4.2---5.4.5 С ИСПОЛЬЗОВАНИЕМ МНОЖЕСТВА РАЗНООБРАЗНЫХ ПРЕДПОЛОЖЕНИЙ,
КОТОРЫЕ ВСТРЕЧАЮТСЯ НА ПРАКТИКЕ.

шНЫЕ ПОДХОДЫ К ПРОБЛЕМЕ ВНЕШНЕЙ СОРТИРОВКИ, НЕ ОСНОВАННЫЕ НА СЛИЯНИИ,
ОБСУЖДАЮТСЯ В П.~5.4.7 И~5.4.8. эАШ ОБЗОР ВНЕШНЕЙ СОРТИРОВКИ ЗАКАНЧИВАЕТСЯ
В П.~5.4.9, ГДЕ РАССМАТРИВАЕТСЯ ВАЖНАЯ ПРОБЛЕМА СОРТИРОВКИ НА ТАКОЙ
ПАМЯТИ, КАК ДИСКИ И БАРАБАНЫ.

\excercises
\ex[15] т ТЕКСТЕ ВНЕШНЯЯ СОРТИРОВКА РАССМАТРИВАЕТСЯ ПОСЛЕ
ВНУТРЕННЕЙ. яОЧЕМУ НЕЛЬЗЯ ВООБЩЕ ПОКОНЧИТЬ С ФАЗОЙ ВНУТРЕННЕЙ СОРТИРОВКИ,
ПРОСТО СЛИВАЯ ЗАПИСИ ВО ВСЕ БОЛЕЕ И БОЛЕЕ ДЛИННЫЕ ОТРЕЗКИ ПРЯМО С САМОГО
НАЧАЛА?

\ex[10] ъАКИМ БУДЕТ СОДЕРЖИМОЕ ЛЕНТ (АНАЛОГИЧНОЕ~(1)--(3)), ЕСЛИ
ЗАПИСИ~$R_1$~\dots{} $R_{5000}$ СОРТИРУЮТСЯ С ПОМОЩЬЮ 3-ЛЕНТОЧНОГО
СБАЛАНСИРОВАННОГО МЕТОДА. ПРИ~$P=2$? ёРАВНИТЕ ЭТОТ СЛУЧАЙ СО СЛИЯНИЕМ НА
4~ЛЕНТАХ; СКОЛЬКО ПРОХОДОВ ПО ВСЕМ ДАННЫМ БУДЕТ СДЕЛАНО ПОСЛЕ
ПЕРВОНАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ ОТРЕЗКОВ?

\ex[20] яОКАЖИТЕ, ЧТО СБАЛАНСИРОВАННОЕ $(P, T-P)\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ,
ПРИМЕНЕННОЕ К $S$~НАЧАЛЬНЫМ ОТРЕЗКАМ, ПРОИЗВОДИТ $2k$~ПРОХОДОВ,
ЕСЛИ~$P^k(T-P)^{k-1}<S\le  P^k(T-P)^k$,   И  ПРОИЗВОДИТ  $2k+l$~ ПРОХОДОВ,
ЕСЛИ~$P^k(T-P)^k< S\le P^{k+1}(T-P)^k$.

фАЙТЕ ПРОСТЫЕ ФОРМУЛЫ ДЛЯ ВЫЧИСЛЕНИЯ (a)~ТОЧНОГО ЧИСЛА ПРОХОДОВ
КАК ФУНКЦИИ ОТ~$S$ ПРИ~$T=2P$, (b)~ПРИБЛИЖЕННОГО ЧИСЛА ПРОХОДОВ
ПРИ~$S\to\infty$ ДЛЯ ЛЮБЫХ~$P$ И~$T$.

\ex[BM15] яРИ КАКОМ ЗНАЧЕНИИ~$P$, $1\le P < T$, ЗНАЧЕНИЕ~$P(T-P)$ МАКСИМАЛЬНО?

%%300
\subsubchap{ьНОГОПУТЕВОЕ СЛИЯНИЕ И ВЫБОР С ЗАМЕЩЕНИЕМ} % 5.4.1

т~П.~5.2.4 МЫ ИЗУЧАЛИ МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ, ОСНОВАННЫЕ НА
ДВУХПУТЕВОМ СЛИЯНИИ---ПРОЦЕССЕ ОБоЕДИНЕНИЯ ДВУХ
УПОРЯДОЧЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ОДНУ. эЕТРУДНО РАСШИРИТЬ ЭТО ДО
ПОНЯТИЯ $P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ, КОГДА $P$~ВХОДНЫХ
ОТРЕЗКОВ ОБоЕДИНЯЮТСЯ В ОДИН ВЫХОДНОЙ.

яУСТЬ ИМЕЕТСЯ $P$~ВОЗРАСТАЮЩИХ ОТРЕЗКОВ, Т.~Е.~ПОСЛЕДОВАТЕЛЬНОСТЕЙ
ЗАПИСЕЙ, КЛЮЧИ КОТОРЫХ РАСПОЛОЖЕНЫ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ. юЧЕВИДНЫМ
СПОСОБОМ ИХ СЛИЯНИЯ БУДЕТ СЛЕДУЮЩИЙ:
ПОСМОТРЕТЬ НА ПЕРВЫЕ ЗАПИСИ КАЖДОГО ОТРЕЗКА И ВЫБРАТЬ ИЗ НИХ ТУ, КОТОРОЙ
СООТВЕТСТВУЕТ МИНИМАЛЬНЫЙ КЛЮЧ; ЭТА ЗАПИСЬ ПЕРЕДАЕТСЯ НА ВЫХОД И
ИСКЛЮЧАЕТСЯ ИЗ ВХОДНЫХ ДАННЫХ, ЗАТЕМ ПРОЦЕСС ПОВТОРЯЕТСЯ.

яОКА~$P$ НЕ СЛИШКОМ ВЕЛИКО, ЭТОТ ВЫБОР УДОБНО ОСУЩЕСТВЛЯТЬ,         
ПРОСТО ВЫПОЛНЯЯ $P-1$~СРАВНЕНИЙ ДЛЯ НАХОЖДЕНИЯ НАИМЕНЬШЕГО ИЗ ТЕКУЩИХ
КЛЮЧЕЙ. эО ЕСЛИ, СКАЖЕМ, $P\ge8$, ТО МОЖНО СОКРАТИТЬ РАБОТУ, ИСПОЛЬЗУЯ
\emph{ДЕРЕВО ВЫБОРА,} КАК ОПИСАНО В П.~5.2.3;
ТОГДА КАЖДЫЙ РАЗ ТРЕБУЕТСЯ ТОЛЬКО $\approx \log_2 P$~СРАВНЕНИЙ
(ПОСЛЕ НАЧАЛЬНОГО ФОРМИРОВАНИЯ ДЕРЕВА). ЁАССМОТРИМ, НАПРИМЕР,
ЧЕТЫРЕХПУТЕВОЕ СЛИЯНИЕ С ДВУХУРОВНЕВЫМ ДЕРЕВОМ ВЫБОРА:
{\def\tree#1#2#3#4#5#6{
\left\{ \matrix{
#1\left\{\matrix{#3\ \infty\hfill\cr #4\ \infty\hfill\cr}\right.\hfill\cr
#2\left\{\matrix{#5\ \infty\hfill\cr #6\ \infty\hfill\cr}\right.\hfill\cr
}\right.
}
$$
\matrix{
{\sl °АГ~1.}&                             \hfill 087 &\tree{087}{154}{087\ 503} {170\ 908}{154\ 426\ 653}{612}\hfill\cr
{\sl °АГ~2.}&                        \hfill 087\ 154 &\tree{170}{154}{503}{170\ 908}{154\ 426\ 653}{612}\hfill\cr
{\sl °АГ~3.}&                   \hfill 087\ 154\ 170 &\tree{170}{426}{503}{170\ 908}{426\ 653}{612}\hfill\cr
\vdots\hfill    \cr
{\sl °АГ~9.}& 087\ 154\ 170\ 426\ 503\ 612\ 653\ 908 &\tree{\infty}{\infty}{}{}{}{}\hfill\cr
}
$$}%
%%301
т ЭТОМ ПРИМЕРЕ В КОНЦЕ КАЖДОГО ОТРЕЗКА ПОМЕЩЕН ДОБАВОЧНЫЙ КЛЮЧ~$\infty$,
ЧТОБЫ СЛИЯНИЕ ЗАКАНЧИВАЛОСЬ ЕСТЕСТВЕННО. ЄАК КАК ВНЕШНЕЕ СЛИЯНИЕ ОБЫЧНО
ИМЕЕТ ДЕЛО С ОЧЕНЬ ДЛИННЫМИ ОТРЕЗКАМИ, ТО ЭТА ДОБАВОЧНАЯ ЗАПИСЬ С КЛЮЧОМ~$\infty$
НЕ УВЕЛИЧИТ СУЩЕСТВЕННО ДЛИНУ ДАННЫХ ИЛИ ОБоЕМ РАБОТЫ ПРИ СЛИЯНИИ;
КРОМЕ ТОГО; ТАКАЯ "КОНЦЕВАЯ" ЗАПИСЬ ЧАСТО СЛУЖИТ УДОБНЫМ СПОСОБОМ
РАЗДЕЛЕНИЯ ЗАПИСЕЙ ФАЙЛА.

т РАССМАТРИВАЕМОМ ПРОЦЕССЕ КАЖДЫЙ ШАГ, КРОМЕ ПЕРВОГО, СОСТОИТ ИЗ ЗАМЕЩЕНИЯ
НАИМЕНЬШЕГО ЭЛЕМЕНТА СЛЕДУЮЩИМ ЭЛЕМЕНТОМ ИЗ ЭТОГО ЖЕ ОТРЕЗКА И ИЗМЕНЕНИЯ
СООТВЕТСТВУЮЩЕГО ПУТИ В ДЕРЕВЕ ВЫБОРА. ЄАК, НА ШАГЕ~2 ИЗМЕНЯЕТСЯ 3~УЗЛА,
КОТОРЫЕ СОДЕРЖАЛИ~$087$ НА ШАГЕ~1; НА ШАГЕ~3 ИЗМЕНЯЕТСЯ 3~УЗЛА,
СОДЕРЖАВШИЕ~$154$ НА ШАГЕ~2, И Т.~Д. яРОЦЕСС ЗАМЕЩЕНИЯ В ДЕРЕВЕ ВЫБОРА
ОДНОГО КЛЮЧА ДРУГИМ НАЗЫВАЕТСЯ \emph{ВЫБОРОМ С ЗАМЕЩЕНИЕМ.}

ьЫ МОЖЕМ ПО-РАЗНОМУ РАССМАТРИВАТЬ ПРИВЕДЕННОЕ ЧЕТЫРЕХПУТЕВОЕ СЛИЯНИЕ. ё
ОДНОЙ ТОЧКИ ЗРЕНИЯ ОНО ЭКВИВАЛЕНТНО ТРЕМ ДВУХПУТЕВЫМ СЛИЯНИЯМ, ВЫПОЛНЯЕМЫМ
СОВМЕСТНО, КАК СОПРОГРАММЫ; КАЖДЫЙ УЗЕЛ ДЕРЕВА ВЫБОРА ИЗОБРАЖАЕТ ОДНУ ИЗ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ИСПОЛЬЗУЕМЫХ В ПРОЦЕССАХ СЛИЯНИЯ. фЕРЕВО ВЫБОРА, ПО
СУЩЕСТВУ, ИСПОЛЬЗУЕТСЯ КАК ПРИОРИТЕТНАЯ ОЧЕРЕДЬ С ДИСЦИПЛИНОЙ "НАИМЕНЬШИЙ
ИЗ ВКЛЮЧЕННЫХ ПЕРВЫМ ИСКЛЮЧАЕТСЯ".
\picture{ЁИС.~62. ЄУРНИР, ПРИ КОТОРОМ ВЫБИРАЕТСЯ НАИМЕНЬШИЙ КЛЮЧ;
ИСПОЛЬЗУЕТСЯ ПОЛНОЕ БИНАРНОЕ ДЕРЕВО, УЗЛЫ КОТОРОГО ЗАНУМЕРОВАНЫ НОМЕРАМИ
ОТ~1 ДО~23.}

ЄАК ЖЕ КАК В П.~5.2.3, МЫ МОГЛИ БЫ ДЛЯ РЕАЛИЗАЦИИ ПРИОРИТЕТНОЙ ОЧЕРЕДИ
ИСПОЛЬЗОВАТЬ НЕ ДЕРЕВО ВЫБОРА, А ПИРАМИДУ. (яИРАМИДУ, КОНЕЧНО, НАДО БЫЛО
БЫ ОРГАНИЗОВАТЬ ТАКИМ ОБРАЗОМ, ЧТОБЫ НА ВЕРШИНЕ ПОЯВЛЯЛСЯ
\emph{НАИМЕНЬШИЙ} ЭЛЕМЕНТ, А НЕ НАИБОЛЬШИЙ,
%%302
ОБРАТИВ ДЛЯ ЭТОГО ПОРЯДОК СООТНОШЕНИЯ~(5.2.3-3).) ЄАК КАК ПИРАМИДА
ИМЕЕТ ПЕРЕМЕННЫЙ РАЗМЕР, МОЖНО ИЗБЕЖАТЬ ИСПОЛЬЗОВАНИЯ КЛЮЧА~$\infty$;
СЛИЯНИЕ ЗАКАНЧИВАЕТСЯ, КОГДА ПИРАМИДА СТАНОВИТСЯ ПУСТОЙ. ё ДРУГОЙ СТОРОНЫ,
ПРИЛОЖЕНИЯ ВНЕШНЕЙ СОРТИРОВКИ ОБЫЧНО ИМЕЮТ ДЕЛО СО СРАВНИТЕЛЬНО ДЛИННЫМИ
ЗАПИСЯМИ И КЛЮЧАМИ, ТАК ЧТО В ПИРАМИДУ БУДУТ ЗАПИСАНЫ ВМЕСТО САМИХ
КЛЮЧЕЙ УКАЗАТЕЛИ НА НИХ; МЫ УВИДИМ НИЖЕ, ЧТО ДЕРЕВЬЯ ВЫБОРА МОГУТ
НАСТОЛЬКО УДОБНО ИЗОБРАЖАТЬСЯ С ПОМОЩЬЮ УКАЗАТЕЛЕЙ, ЧТО ОНИ, ВЕРОЯТНО, В
ДАННОЙ СИТУАЦИИ ЛУЧШЕ ПИРАМИД.

\section фЕРЕВО "ПРОИГРАВШИХ". эА РИС.~62 ИЗОБРАЖЕНО ПОЛНОЕ
БИНАРНОЕ ДЕРЕВО С 12~ВНЕШНИМИ (КВАДРАТНЫМИ) УЗЛАМИ И
11~ВНУТРЕННИМИ (КРУГЛЫМИ); ВО ВНЕШНИХ УЗЛАХ ЗАПИСАНЫ КЛЮЧИ, ВО
ВНУТРЕННИХ--- "ПОБЕДИТЕЛИ", ЕСЛИ ДЕРЕВО РАССМАТРИВАТЬ КАК ТУРНИР ДЛЯ ВЫБОРА
\picture{ЁИС.~63.               ЄОТ ЖЕ ТУРНИР, ЧТО И НА РИС.~62, НО
ПОКАЗАНЫ ПРОИГРАВШИЕ, А НЕ ПОБЕДИТЕЛИ; ЧЕМПИОН НАХОДИТСЯ НА САМОМ ВЕРХУ.}
НАИМЕНЬШЕГО КЛЮЧА. ўИСЛА МЕНЬШЕГО РАЗМЕРА НАД КАЖДЫМ УЗЛОМ ПОКАЗЫВАЮТ
ТРАДИЦИОННЫЙ СПОСОБ РАСПРЕДЕЛЕНИЯ ПОСЛЕДОВАТЕЛЬНЫХ ПОЗИЦИЙ ПАМЯТИ ДЛЯ
ПОЛНОГО БИНАРНОГО ДЕРЕВА.

ўТОБЫ ОПРЕДЕЛИТЬ НОВОЕ СОСТОЯНИЕ ДЕРЕВА ВЫБОРА, ИЗОБРАЖЕННОГО НА РИС.~62,
 КОГДА НАИМЕНЬШИЙ КЛЮЧ~$061$ БУДЕТ ЗАМЕНЕН ДРУГИМ КЛЮЧОМ, НУЖНО
РАССМОТРЕТЬ ТОЛЬКО КЛЮЧИ~$512$, $087$ И~$154$ И НИКАКИЕ ДРУГИЕ. хСЛИ
ИНТЕРПРЕТИРОВАТЬ ДЕРЕВО КАК ТУРНИР, ПОСЛЕДНИЕ ТРИ КЛЮЧА ПРЕДСТАВЛЯЮТ
СОБОЙ ПРОИГРАВШИХ В МАТЧАХ С ИГРОКОМ~$061$. ¤ТО НАВОДИТ НА МЫСЛЬ, ЧТО МЫ В
ДЕЙСТВИТЕЛЬНОСТИ ДОЛЖНЫ ЗАПИСАТЬ ВО ВНУТРЕННИЕ УЗЛЫ \emph{ПРОИГРАВШЕГО}
%%303
В КАЖДОМ МАТЧЕ, А НЕ ПОБЕДИТЕЛЯ, ТОГДА ИНФОРМАЦИЯ, НЕОБХОДИМАЯ ДЛЯ
ИЗМЕНЕНИЯ ДЕРЕВА, БУДЕТ ЛЕГКОДОСТУПНОЙ.

эА РИС.~63 ИЗОБРАЖЕНО ТО ЖЕ ДЕРЕВО, ЧТО И НА РИС.~62, НО ВМЕСТО
ПОБЕДИТЕЛЕЙ В НЕМ ПРЕДСТАВЛЕНЫ ПРОИГРАВШИЕ. фОПОЛНИТЕЛЬНЫЙ УЗЕЛ С
НОМЕРОМ~"0" ДОБАВЛЕН НА ВЕРШИНЕ ДЕРЕВА ДЛЯ УКАЗАНИЯ ЧЕМПИОНА ТУРНИРА.
чАМЕТИМ, ЧТО КАЖДЫЙ КЛЮЧ, КРОМЕ ЧЕМПИОНА, ЯВЛЯЕТСЯ ПРОИГРАВШИМ РОВНО ОДИН
РАЗ (СМ.~П.~5.3.3);
ТАКИМ ОБРАЗОМ, КАЖДЫЙ КЛЮЧ ПОЯВЛЯЕТСЯ ОДИН РАЗ ВО ВНЕШНЕМ УЗЛЕ И ОДИН РАЗ
ВО ВНУТРЕННЕМ.

эА ПРАКТИКЕ ВНЕШНИМ УЗЛАМ В НИЖНЕЙ ЧАСТИ РИС.~63 БУДУТ СООТВЕТСТВОВАТЬ
ВЕСЬМА ДЛИННЫЕ ЗАПИСИ, РАСПОЛОЖЕННЫЕ В ПАМЯТИ ¤ть, А ВНУТРЕННИМ
УЗЛАМ---УКАЗАТЕЛИ НА ЭТИ ЗАПИСИ. чАМЕТИМ, ЧТО $P\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ
ТРЕБУЕТ РОВНО $P$~ВНЕШНИХ И $P$~ВНУТРЕННИХ УЗЛОВ ПО ОДНОМУ В СОСЕДНИХ
ГРУППАХ, ЧТО НАВОДИТ НА МЫСЛЬ О РЯДЕ ЭФФЕКТИВНЫХ МЕТОДОВ РАСПРЕДЕЛЕНИЯ
ПАМЯТИ. эЕТРУДНО ВИДЕТЬ, КАКИМ ОБРАЗОМ МОЖНО ИСПОЛЬЗОВАТЬ ДЕРЕВО
ПРОИГРАВШИХ ДЛЯ ВЫБОРА С ЗАМЕЩЕНИЕМ. сОЛЕЕ ДЕТАЛЬНО МЫ ОБСУДИМ
ЭТОТ АЛГОРИТМ В НАСТОЯЩЕМ ПУНКТЕ ЧУТЬ ПОЗЖЕ.

\section яОЛУЧЕНИЕ НАЧАЛЬНЫХ ОТРЕЗКОВ ПОСРЕДСТВОМ ВЫБОРА С ЗАМЕЩЕНИЕМ.
ЄЕХНИКА ВЫБОРА С ЗАМЕЩЕНИЕМ МОЖЕТ ИСПОЛЬЗОВАТЬСЯ ТАКЖЕ НА ПЕРВОЙ ФАЗЕ
ВНЕШНЕЙ СОРТИРОВКИ, ЕСЛИ ФАКТИЧЕСКИ ВЫПОЛНИТЬ $P\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ
ВХОДНЫХ ДАННЫХ С САМИМИ СОБОЙ. т ЭТОМ СЛУЧАЕ $P$~ВЫБИРАЕТСЯ ДОСТАТОЧНО
БОЛЬШИМ, ЧТОБЫ ЗАПОЛНИТЬ, ПО СУЩЕСТВУ, ВСЮ ВНУТРЕННЮЮ ПАМЯТЬ. ъАЖДАЯ
ЗАПИСЬ ПРИ ВЫВОДЕ ЗАМЕЩАЕТСЯ ОЧЕРЕДНОЙ ЗАПИСЬЮ ИЗ ИСХОДНЫХ ДАННЫХ. хСЛИ У
ЭТОЙ НОВОЙ ЗАПИСИ КЛЮЧ МЕНЬШЕ, ЧЕМ У ВЫВЕДЕННОЙ ЗАПИСИ, ТО МЫ НЕ ВКЛЮЧАЕМ
ЕЕ В ТЕКУЩИЙ ОТРЕЗОК; В ПРОТИВНОМ СЛУЧАЕ МЫ ОБЫЧНЫМ ОБРАЗОМ ВКЛЮЧАЕМ ЕЕ В
ДЕРЕВО ВЫБОРА, ТАК ЧТО ОНА ОБРАЗУЕТ ЧАСТЬ ОТРЕЗКА, ПОРОЖДАЕМОГО В ДАННЫЙ
МОМЕНТ. ЄАКИМ ОБРАЗОМ, КАЖДЫЙ ОТРЕЗОК МОЖЕТ СОДЕРЖАТЬ БОЛЬШЕ $P$~ЗАПИСЕЙ,
ХОТЯ В ЛЮБОЙ МОМЕНТ В ДЕРЕВЕ ВЫБОРА НАХОДИТСЯ НЕ БОЛЕЕ
$P$~ЗАПИСЕЙ. ЄАБЛИЦА~1 ИЛЛЮСТРИРУЕТ ЭТОТ ПРОЦЕСС ДЛЯ~$P=4$ (ЧИСЛА,
ЗАКЛЮЧЕННЫЕ В СКОБКИ, ОЖИДАЮТ ВКЛЮЧЕНИЯ В СЛЕДУЮЩИЙ ОТРЕЗОК).

¤ТОТ ВАЖНЫЙ МЕТОД ФОРМИРОВАНИЯ НАЧАЛЬНЫХ ОТРЕЗКОВ БЫЛ ВПЕРВЫЕ ОПИСАН
уАРОЛЬДОМ ъ.~ёЬЮВОРДОМ [Master's Thesis, Digital Computer Laboratory
Report R-232 (Mass.~Inst.~of~Technology, 1954), 29--30], КОТОРЫЙ ПРИВЕЛ
СООБРАЖЕНИЯ В ПОЛЬЗУ ТОГО, ЧТО ПРИ ПРИМЕНЕНИИ К СЛУЧАЙНЫМ ДАННЫМ ОТРЕЗКИ,
ВИДИМО, БУДУТ СОДЕРЖАТЬ БОЛЕЕ $1.5P$~ЗАПИСЕЙ. ЄУ ЖЕ ИДЕЮ ПРЕДЛОЖИЛ
ПРИМЕРНО В 1950~Г.\ р.~ш.~фУМИ В СВЯЗИ СО СПЕЦИАЛЬНЫМ УСТРОЙСТВОМ
ДЛЯ СОРТИРОВКИ, РАЗРАБАТЫВАЕМЫМ Engineering Research Associates, НО НЕ
ОПУБЛИКОВАЛ ЕЕ. ёАМО НАЗВАНИЕ "ВЫБОР С ЗАМЕЩЕНИЕМ" (replacement
selecting) БЫЛО ПРИДУМАНО ¤.~X.~ЇРЭНДОМ
[{\sl JACM,\/} {\bf 3} (1956), 154], КОТОРЫЙ ЗАМЕТИЛ, ЧТО "ОЖИДАЕМАЯ ДЛИНА
ПОРОЖДАЕМОЙ ПОСЛЕДОВАТЕЛЬНОСТИ НЕ ПОДДАЕТСЯ ТОЧНОЙ ФОРМУЛИРОВКЕ, НО
%%304
\htable{ЄАБЛИЦА~1}%
{яРИМЕР ЧЕТЫРЕХПУТЕВОГО ВЫБОРА С ЗАМЕЩЕНИЕМ}%
{
\strut\hfill$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\hfill\bskip$#$\bskip\hfill&\bskip$#$\bskip\hfill\cr
\multispan{4}\hfill ёОДЕРЖИМОЕ ПАМЯТИ \hfill &  \hbox{тЫВОД}\cr
\noalign{\hrule}
 503 & 087 & 512 & 061 & 061\cr
 603 & 087 & 512 & 908 & 087\cr
 503 & 170 & 512 & 908 & 170\cr
 503 & 897 & 512 & 908 & 503\cr
(275)& 897 & 512 & 908 & 512\cr
(275)& 897 & 653 & 908 & 653\cr
(275)& 897 &(426)& 908 & 897\cr
(275)&(154)&(426)& 908 & 908\cr
(275)&(154)&(426)&(509)& (\hbox{КОНЕЦ ОТРЕЗКА})\cr
 275 & 154 & 426 & 509 & 154\cr
 275 & 612 & 426 & 509 & 275\cr
\multispan{5}\hfill\hbox{И Т.Д.}\hfill\cr
\noalign{\hrule}
}
ЭКСПЕРИМЕНТЫ ПОЗВОЛЯЮТ ПРЕДПОЛОЖИТЬ, ЧТО РАЗУМНОЙ ОЦЕНКОЙ БУДЕТ~$2P$".

¤.~Ї.~ьУР ПРЕДЛОЖИЛ ИЗЯЩНЫЙ СПОСОБ ДОКАЗАТЕЛЬСТВА ТОГО, ЧТО ОЖИДАЕМАЯ
ДЛИНА ОТРЕЗКА РАВНА~$2P$, ПРОВЕДЯ АНАЛОГИЮ СО
\picture{ЁИС.~64. тЕЧНЫЙ СНЕГООЧИСТИТЕЛЬ В СВОЕМ НЕСКОНЧАЕМОМ ЦИКЛЕ.}
СНЕГООЧИСТИТЕЛЕМ, ДВИЖУЩИМСЯ ПО КРУГУ [U.~S.~Patent~2983904 (1961),
cols.~3--4]. ЁАССМОТРИМ СИТУАЦИЮ, ИЗОБРАЖЕННУЮ НА РИС.~64: НА КОЛЬЦЕВУЮ
ДОРОГУ РАВНОМЕРНО ПАДАЮТ СНЕЖИНКИ, А ОДИН СНЕГООЧИСТИТЕЛЬ НЕПРЕРЫВНО
УБИРАЕТ СНЕГ. ёНЕГ ИСЧЕЗАЕТ ИЗ СИСТЕМЫ,
%%304
КАК ТОЛЬКО ОН СБРАСЫВАЕТСЯ ЗА ПРЕДЕЛЫ ДОРОГИ. ЄОЧКИ ДОРОГИ
ОБОЗНАЧАЮТСЯ ВЕЩЕСТВЕННЫМИ ЧИСЛАМИ~$x$, $0\le x < 1$; СНЕЖИНКА, ПАДАЮЩАЯ
В ТОЧКУ~$x$, СООТВЕТСТВУЕТ ВХОДНОЙ ЗАПИСИ С КЛЮЧОМ~$x$, А СНЕГООЧИСТИТЕЛЬ
ПРЕДСТАВЛЯЕТ СОБОЙ ВЫВОД ПРОЦЕССА ВЫБОРА С ЗАМЕЩЕНИЕМ.

ёКОРОСТЬ СНЕГООЧИСТИТЕЛЯ ОБРАТНО ПРОПОРЦИОНАЛЬНА ВЕСУ СНЕГА, КОТОРЫЙ
ВСТРЕЧАЕТСЯ НА ЕГО ПУТИ, И СИТУАЦИЯ ВПОЛНЕ УРАВНОВЕШЕНА, ТАК ЧТО ОБЩЕЕ
КОЛИЧЕСТВО СНЕЖИНОК НА ДОРОГЕ В ТОЧНОСТИ РАВНО~$P$. ъАЖДЫЙ РАЗ, КОГДА
СНЕГООЧИСТИТЕЛЬ ПРОХОДИТ ТОЧКУ~0, НА ВЫХОДЕ ФОРМИРУЕТСЯ НОВЫЙ ОТРЕЗОК.
\picture{ЁИС.~65. яОПЕРЕЧНОЕ СЕЧЕНИЕ, ПОКАЗЫВАЮЩЕЕ ПЕРЕМЕННЫЙ ВЕС СНЕГА
ПЕРЕД СНЕГООЧИСТИТЕЛЕМ, КОГДА СИСТЕМА НАХОДИТСЯ В УСТАНОВИВШЕМСЯ РЕЖИМЕ.}

шНТУИТИВНО ЯСНО, ЧТО СИСТЕМА, ПОРАБОТАВ НЕКОТОРОЕ ВРЕМЯ, ВЫЙДЕТ НА
УСТАНОВИВШИЙСЯ РЕЖИМ, ПРИ КОТОРОМ СНЕГООЧИСТИТЕЛЬ БУДЕТ ДВИГАТЬСЯ С
ПОСТОЯННОЙ СКОРОСТЬЮ (В СИЛУ КРУГОВОЙ СИММЕТРИИ ДОРОГИ). ¤ТО ОЗНАЧАЕТ,
ЧТО В ТОЧКЕ, ГДЕ НАХОДИТСЯ СНЕГООЧИСТИТЕЛЬ, СНЕГ ИМЕЕТ ПОСТОЯННЫЙ ВЕС, А
ВПЕРЕДИ СНЕГООЧИСТИТЕЛЯ ЭТОТ ВЕС ЛИНЕЙНО УМЕНЬШАЕТСЯ, КАК ПОКАЗАНО НА
РИС.~65. юТСЮДА СЛЕДУЕТ, ЧТО КОЛИЧЕСТВО СНЕГА, УДАЛЯЕМОГО ЗА ОДИН
ОБОРОТ (А ИМЕННО ДЛИНА ОТРЕЗКА), ВДВОЕ ПРЕВОСХОДИТ КОЛИЧЕСТВО СНЕГА~$P$,
 ПРИСУТСТВУЮЩЕГО В ЛЮБОЙ МОМЕНТ.

тО МНОГИХ КОММЕРЧЕСКИХ ПРИЛОЖЕНИЯХ ВХОДНЫЕ ДАННЫЕ \emph{НЕЛЬЗЯ} СЧИТАТЬ
ПОЛНОСТЬЮ СЛУЧАЙНЫМИ---В НИХ УЖЕ СУЩЕСТВУЕТ ОПРЕДЕЛЕННЫЙ ПОРЯДОК;
СЛЕДОВАТЕЛЬНО, ОТРЕЗКИ, ПОРОЖДАЕМЫЕ ВЫБОРОМ С ЗАМЕЩЕНИЕМ, ИМЕЮТ ТЕНДЕНЦИЮ
СОДЕРЖАТЬ ДАЖЕ БОЛЬШЕ, ЧЕМ $2P$~ЗАПИСЕЙ. т ДАЛЬНЕЙШЕМ МЫ УВИДИМ, ЧТО ВРЕМЯ,
 НУЖНОЕ ДЛЯ ВНЕШНЕЙ СОРТИРОВКИ СЛИЯНИЕМ, В ЗНАЧИТЕЛЬНОЙ СТЕПЕНИ ЗАВИСИТ ОТ
КОЛИЧЕСТВА ОТРЕЗКОВ, ПОРОЖДАЕМЫХ НАЧАЛЬНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ФАЗОЙ, ТАК
ЧТО ВЫБОР С ЗАМЕЩЕНИЕМ СТАНОВИТСЯ ОСОБЕННО ПРИВЛЕКАТЕЛЬНЫМ; ДРУГИЕ СПОСОБЫ
ВНУТРЕННЕЙ СОРТИРОВКИ ПОРОЖДАЛИ БЫ ПРИМЕРНО ВДВОЕ БОЛЬШЕ НАЧАЛЬНЫХ
ОТРЕЗКОВ, ПОСКОЛЬКУ РАЗМЕРЫ ПАМЯТИ ОГРАНИЧЕНЫ.

ЄЕПЕРЬ ДЕТАЛЬНО РАССМОТРИМ ПРОЦЕСС СОЗДАНИЯ НАЧАЛЬНЫХ ОТРЕЗКОВ ВЫБОРОМ С
ЗАМЕЩЕНИЕМ. ёЛЕДУЮЩИЙ АЛГОРИТМ ПРИНАДЛЕЖИТ фЖОНУ~Ё.~єОЛТЕРСУ, фЖЕЙМСУ
яЭЙНТЕРУ И~ьАРТИНУ чАЛКУ, КОТОРЫЕ ИСПОЛЬЗОВАЛИ ЕГО В ПРОГРАММЕ
СОРТИРОВКИ ПОСРЕДСТВОМ СЛИЯНИЯ, ДЛЯ ¤ть Philco~2000 В~1958~Г. юН ВКЛЮЧАЕТ
В СЕБЯ
%%306
ПРЕКРАСНЫЙ СПОСОБ НАЧАЛЬНОГО ФОРМИРОВАНИЯ ДЕРЕВА ВЫБОРА И РАЗДЕЛЕНИЯ
ЗАПИСЕЙ, ПРИНАДЛЕЖАЩИХ РАЗНЫМ ОТРЕЗКАМ, А ТАКЖЕ ВЫВОДА ПОСЛЕДНЕГО ОТРЕЗКА
ПО ЕДИНООБРАЗНОЙ, СРАВНИТЕЛЬНО ПРОСТОЙ ЛОГИКЕ. (эАДЛЕЖАЩАЯ ОБРАБОТКА
ПОСЛЕДНЕГО ОТРЕЗКА, ПОРОЖДЕННОГО ВЫБОРОМ С ЗАМЕЩЕНИЕМ, ОКАЗЫВАЕТСЯ
ДОВОЛЬНО СЛОЖНОЙ;
БЛОК, ОСУЩЕСТВЛЯЮЩИЙ ЭТУ ОБРАБОТКУ, ЧАСТО БЫВАЕТ КАМНЕМ ПРЕТКНОВЕНИЯ ДЛЯ
ПРОГРАММИСТА.) юСНОВНАЯ ИДЕЯ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТОБЫ РАССМАТРИВАТЬ КАЖДЫЙ
КЛЮЧ КАК ПАРУ~$(S, K)$, ГДЕ $K$---ПЕРВОНАЧАЛЬНЫЙ КЛЮЧ, А $S$---НОМЕР ОТРЕЗКА,
КОТОРОМУ ПРИНАДЛЕЖИТ ДАННАЯ ЗАПИСЬ. ьЫ ПОЛУЧИМ ВЫХОДНУЮ
ПОСЛЕДОВАТЕЛЬНОСТЬ, ПОРОЖДЕННУЮ ВЫБОРОМ С ЗАМЕЩЕНИЕМ, ЕСЛИ
ЛЕКСИКОГРАФИЧЕСКИ УПОРЯДОЧИМ ЭТИ РАСШИРЕННЫЕ КЛЮЧИ ($S$ СЧИТАЕТСЯ СТАРШЕ~$K$).

яРИВОДИМЫЙ НИЖЕ АЛГОРИТМ ИСПОЛЬЗУЕТ ДЛЯ ПРЕДСТАВЛЕНИЯ ДЕРЕВА ВЫБОРА
СТРУКТУРУ ДАННЫХ, СОСТОЯЩУЮ ИЗ $P$~УЗЛОВ; ПРЕДПОЛАГАЕТСЯ, ЧТО
$j\hbox{-Й}$~УЗЕЛ~$X[j]$ СОДЕРЖИТ $c$~СЛОВ,
НАЧИНАЮЩИХСЯ С~$|LOC|(X[j]])=L_0+cj$ ПРИ~$0\le j < P$, ОН ПРЕДСТАВЛЯЕТ КАК
ВНУТРЕННИЙ УЗЕЛ С НОМЕРОМ~$j$, ТАК И ВНЕШНИЙ УЗЕЛ С
НОМЕРОМ~$P+j$ (РИС.~63). т КАЖДОМ УЗЛЕ ИМЕЕТСЯ НЕСКОЛЬКО ПОЛЕЙ:

% !!! яРИ СМЕНЕ СТИЛЯ ИЛИ ШРИФТА ПОПЛЫВЕТ
{\medskip\narrower
\item{|KEY|} = КЛЮЧ, НАХОДЯЩИЙСЯ В ДАННОМ ВНЕШНЕМ УЗЛЕ;

\item{|RECORD|} = ЗАПИСЬ, НАХОДЯЩАЯСЯ В ДАННОМ ВНЕШНЕМ УЗЛЕ
(ВКЛЮЧАЯ |KEY| КАК ПОДПОЛЕ);

\item{|LOSER|} = УКАЗАТЕЛЬ НА "ПРОИГРАВШЕГО" В ДАННОМ ВНУТРЕННЕМ УЗЛЕ;

\item{|RN|} = НОМЕР ОТРЕЗКА, КУДА ВКЛЮЧЕНА ЗАПИСЬ, НА КОТОРУЮ УКАЗЫВАЕТ~|LOSER|;

\item{|FE|} = УКАЗАТЕЛЬ НА ВНУТРЕННИЙ УЗЕЛ, РАСПОЛОЖЕННЫЙ В ДЕРЕВЕ ВЫБОРА ВЫШЕ
ДАННОГО ВНЕШНЕГО УЗЛА;

\item{|FI|} = УКАЗАТЕЛЬ НА ВНУТРЕННИЙ УЗЕЛ, РАСПОЛОЖЕННЫЙ В ДЕРЕВЕ ВЫБОРА ВЫШЕ
ДАННОГО ВНУТРЕННЕГО УЗЛА.
\medskip}

эАПРИМЕР, ПРИ~$P=12$ ВНУТРЕННИЙ УЗЕЛ С НОМЕРОМ~5 И ВНЕШНИЙ УЗЕЛ С
НОМЕРОМ~17 НА РИС.~63 ОБА БУДУТ ПРЕДСТАВЛЕНЫ УЗЛОМ~$X[5]$ С
ПОЛЯМИ~$|KEY|=170$, $|LOSER|=L_0+9c$ (АДРЕС ВНЕШНЕГО УЗЛА С НОМЕРОМ~21),
$|FE|=L_0+8c$, $|FI|=L_0+2c$.

чНАЧЕНИЯ В ПОЛЯХ~|FE| И~|FI| ЯВЛЯЮТСЯ КОНСТАНТАМИ; ТАКИМ ОБРАЗОМ, СТРОГО
ГОВОРЯ, НЕТ НЕОБХОДИМОСТИ ХРАНИТЬ ИХ В ЯВНОМ ВИДЕ. юДНАКО ИНОГДА НА
НАЧАЛЬНОЙ ФАЗЕ ВНЕШНЕЙ СОРТИРОВКИ ДЛЯ БЫСТРОЙ РАБОТЫ С УСТРОЙСТВАМИ
ВВОДА/ВЫВОДА ВЫГОДНЕЕ ХРАНИТЬ ЭТУ ИЗБЫТОЧНУЮ ИНФОРМАЦИЮ, ЧЕМ ВЫЧИСЛЯТЬ
ЕЕ КАЖДЫЙ РАЗ ЗАНОВО.

\alg R.(тЫБОР С ЗАМЕЩЕНИЕМ.) ¤ТОТ АЛГОРИТМ ЧИТАЕТ ЗАПИСИ ПОСЛЕДОВАТЕЛЬНО
ИЗ ВХОДНОГО ФАЙЛА И ЗАПИСЫВАЕТ ИХ ПОСЛЕДОВАТЕЛЬНО В ВЫХОДНОЙ ФАЙЛ,
ПРОИЗВОДЯ |RMAX|~ОТРЕЗКОВ ДЛИНЫ~$P$ ИЛИ БОЛЬШЕ (ЗА ИСКЛЮЧЕНИЕМ ПОСЛЕДНЕГО
ОТРЕЗКА). шМЕЕТСЯ $P\ge 2$~УЗЛОВ $X[0],~\ldots, X[P-1]$ С ПОЛЯМИ, ОПИСАННЫМИ
ВЫШЕ.

%%307
\picture{ЁИС.~66. яОЛУЧЕНИЕ НАЧАЛЬНЫХ ОТРЕЗКОВ ПОСРЕДСТВОМ ВЫБОРА С ЗАМЕЩЕНИЕМ.}
\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ~$|RMAX|\asg0$, $|RC|\asg0$,
 $|LASTKEY|\asg\infty$, $|Q|\asg|LOC|(X[0])$ И~$|RQ|\asg0$. (|RC|---НОМЕР
ТЕКУЩЕГО ОТРЕЗКА, a |LASTKEY|---КЛЮЧ ПОСЛЕДНЕЙ ВЫВЕДЕННОЙ ЗАПИСИ.
эАЧАЛЬНОЕ ЗНАЧЕНИЕ~|LASTKEY| ДОЛЖНО БЫТЬ БОЛЬШЕ ЛЮБОГО ВОЗМОЖНОГО КЛЮЧА;
СР.~С~УПР.~8.) фЛЯ~$0\le j < P$ НАЧАЛЬНОЕ СОДЕРЖИМОЕ~$X[j]$ УСТАНОВИТЬ
СЛЕДУЮЩИМ ОБРАЗОМ (ГДЕ~$|J|=|LOC|(X[j]))$:
$$
\displaylines{
|LOSER|(|J|)\asg J; |RN|(|J|)\asg0; \cr
|FE|(|J|)\asg|LOC|(X[\floor{(P+j)/2}]);   |FI|(|J|)\asg|LOC|(X[ \floor{j/2}]).\cr
}
$$
(єСТАНОВКА~$|LOSER|(|J|)$ И~$|RN|(|J|)$ ЕСТЬ ИСКУССТВЕННЫЙ
СПОСОБ ОБРАЗОВАТЬ НАЧАЛЬНОЕ ДЕРЕВО, РАССМАТРИВАЯ ФИКТИВНЫЙ ОТРЕЗОК С
НОМЕРОМ~0, КОТОРЫЙ НИКОГДА НЕ ВЫВОДИТСЯ. ¤ТО--- НЕКИЙ ТРЮК; СМ.~УПР.~10.)

\st[ъОНЕЦ ОТРЕЗКА?] хСЛИ~$|RQ|=|RC|$, ТО ПЕРЕЙТИ К ШАГУ~\stp{3}. (т
ПРОТИВНОМ СЛУЧАЕ~$|RQ|=|RC|+1$, И МЫ ТОЛЬКО ЧТО ЗАКОНЧИЛИ ОТРЕЗОК С
НОМЕРОМ~$|RC|$; В ЭТОМ МЕСТЕ СЛЕДУЕТ ВЫПОЛНИТЬ ТЕ СПЕЦИАЛЬНЫЕ ДЕЙСТВИЯ,
КОТОРЫЕ НУЖНЫ В СООТВЕТСТВИИ СО СХЕМОЙ СЛИЯНИЯ ДЛЯ ПОСЛЕДУЮЩИХ ЭТАПОВ
СОРТИРОВКИ.) хСЛИ~$|RQ|>|RMAX|$, ТО АЛГОРИТМ ЗАВЕРШЕН; В ПРОТИВНОМ СЛУЧАЕ
УСТАНОВИТЬ~$|RC|\asg|RQ|$.

\st[тЫВОД ВЕРШИНЫ ДЕРЕВА.] (ёЕЙЧАС |Q|~УКАЗЫВАЕТ НА "ЧЕМПИОНА",
 И~|RQ|---НОМЕР ЕГО ОТРЕЗКА.) хСЛИ~$|RQ|\ne 0$, ТО ВЫВЕСТИ~$|RECORD|(|Q|)$ И
УСТАНОВИТЬ~$|LASTKEY|\asg|KEY|(|Q|)$.

\st[тВОД НОВОЙ ЗАПИСИ.] хСЛИ ВХОДНОЙ ФАЙЛ ИСЧЕРПАН,
УСТАНОВИТЬ~$|RQ|\asg|RMAX|+1$ И ПЕРЕЙТИ К ШАГУ~\stp{5}. т ПРОТИВНОМ СЛУЧАЕ
ПОМЕСТИТЬ НОВУЮ ЗАПИСЬ ИЗ ВХОДНОГО ФАЙЛА
В~$|RECORD|(|Q|)$. хСЛИ~$|KEY|(|Q|)<|LASTKEY|$ (Т.~Е.~ЭТА ЗАПИСЬ НЕ
ПРИНАДЛЕЖИТ ТЕКУЩЕМУ ОТРЕЗКУ), ТО~$|RQ|\asg|RQ|+1$, И ТЕПЕРЬ,
ЕСЛИ~$|RQ|>|RMAX|$, УСТАНОВИТЬ~$|RMAX|\asg|RQ|$.

%%308

\st[яОДГОТОВКА К ИЗМЕНЕНИЮ.] (ёЕЙЧАС~|Q| УКАЗЫВАЕТ НА НОВУЮ ЗАПИСЬ С
НОМЕРОМ ОТРЕЗКА~|RQ|.) єСТАНОВИТЬ~$|T|\asg|FE|(|Q|)$. (|T|---ПЕРЕМЕННЫЙ
УКАЗАТЕЛЬ, КОТОРЫЙ БУДЕТ ДВИГАТЬСЯ ПО ДЕРЕВУ.)

\st[єСТАНОВКА НОВОГО ПРОИГРАВШЕГО.] хСЛИ~$|RN|(|T|)<|RQ|$
ИЛИ ЕСЛИ~$|RN|(|T|)=|RQ|$ И~$|KEY|(|LOSER|(|T|))<|KEY|(|Q|)$. ТО
ПОМЕНЯТЬ МЕСТАМИ $|LOSER|(|T|)\xchg |Q|$, $|RN|(|T|)\xchg |RQ|$. (т
ПЕРЕМЕННЫХ~|Q| И~|RQ| ЗАПОМИНАЕТСЯ ТЕКУЩИЙ ПОБЕДИТЕЛЬ И НОМЕР ЕГО ОТРЕЗКА.)

\st[ёДВИГ ВВЕРХ.] хСЛИ~$|T|=|LOC|(X[1])$, ТО ВЕРНУТЬСЯ К ШАГУ~\stp{2}, В
ПРОТИВНОМ СЛУЧАЕ~$|T|\asg|FI|(|T|)$ И ВЕРНУТЬСЯ К~\stp{6}.
\algend

т АЛГОРИТМЕ~R ГОВОРИТСЯ О ВВОДЕ И ВЫВОДЕ ЗАПИСЕЙ ПО ОДНОЙ, ТОГДА КАК
ПРАКТИЧЕСКИ ОКАЗЫВАЕТСЯ ЛУЧШЕ ЧИТАТЬ И ЗАПИСЫВАТЬ ОТНОСИТЕЛЬНО БОЛЬШИЕ
БЛОКИ ЗАПИСЕЙ. ёЛЕДОВАТЕЛЬНО, НА САМОМ ДЕЛЕ ЗА КУЛИСАМИ ПРЯЧУТСЯ БУФЕРЫ
ВВОДА И ВЫВОДА; ИХ ПРИСУТСТВИЕ В ПАМЯТИ ПРИВОДИТ К УМЕНЬШЕНИЮ
ЗНАЧЕНИЯ~$P$. ¤ТО БУДЕТ ПОЯСНЕНО В П.~5.4.6.

¤.~X.~ЇРЭНД [{\sl JACM,\/} {bf 3} (1956), 154] ПРЕДЛОЖИЛ
СЛЕДУЮЩЕЕ ОБОБЩЕНИЕ МЕТОДА ВЫБОРА С ЗАМЕЩЕНИЕМ. т ТЕХ СЛУЧАЯХ,
КОГДА ВВОДИМЫЙ КЛЮЧ МЕНЬШЕ, ЧЕМ~|LASTKEY| (ТАК ЧТО ОН НЕ ПОПАДЕТ В ТЕКУЩИЙ
ОТРЕЗОК), НО БОЛЬШЕ ИЛИ РАВЕН ПОСЛЕДНЕМУ КЛЮЧУ, ДЕЙСТВИТЕЛЬНО
ЗАПИСАННОМУ НА ЛЕНТУ (ТАК ЧТО ЕГО ФАКТИЧЕСКИ МОЖНО БЫЛО БЫ ПОМЕСТИТЬ В
ТЕКУЩИЙ ОТРЕЗОК), ВСТАВЛЯТЬ ЭТОТ КЛЮЧ ВНУТРЬ БУФЕРА ВЫВОДА. ъРОМЕ ТОГО,
НЕКОТОРЫЕ ¤ть УМЕЮТ ВЫПОЛНЯТЬ "ЧТЕНИЕ ВРАЗБРОС" И "ЗАПИСЬ СО СБОРКОЙ",
Т.~Е.~ВВОДИТЬ ИНФОРМАЦИЮ ВО ВНУТРЕННЮЮ ПАМЯТЬ НЕ ОБЯЗАТЕЛЬНО В
ПОСЛЕДОВАТЕЛЬНЫЕ ЯЧЕЙКИ, А "ВРАЗБРОС" И ВЫВОДИТЬ ЕЕ, СОБИРАЯ ИЗ
РАЗНЫХ МЕСТ. ¤ТО ПОЗВОЛЯЕТ СОВМЕЩАТЬ ПАМЯТЬ ДЛЯ БУФЕРОВ С ПАМЯТЬЮ ДЛЯ
ДЕРЕВА ВЫБОРА.

\section *яРЕОБРАЗОВАНИЕ ОТРЕЗКОВ С ЗАДЕРЖКОЙ. Ё.~фЖ.~фИНСМОР
[{\sl CACM,\/} {\bf 8} (1965), 48] ПРЕДЛОЖИЛ ИНТЕРЕСНОЕ УСОВЕРШЕНСТВОВАНИЕ
ВЫБОРА С ЗАМЕЩЕНИЕМ, ИСПОЛЬЗУЮЩЕЕ ПОНЯТИЕ, КОТОРОЕ БУДЕМ
НАЗЫВАТЬ \dfn{СТЕПЕНЬЮ СВОБОДЫ.} ъАК МЫ ВИДЕЛИ, КАЖДЫЙ БЛОК ЗАПИСЕЙ,
НАХОДЯЩИЙСЯ НА ЛЕНТЕ В СОСТАВЕ ОТРЕЗКА, СОДЕРЖИТ ЗАПИСИ В НЕУБЫВАЮЩЕМ
ПОРЯДКЕ, ТАК ЧТО ПЕРВЫЙ ЭЛЕМЕНТ НАИМЕНЬШИЙ, А ПОСЛЕДНИЙ НАИБОЛЬШИЙ. т
ОБЫЧНОМ ПРОЦЕССЕ ВЫБОРА С ЗАМЕЩЕНИЕМ НАИМЕНЬШИЙ ЭЛЕМЕНТ КАЖДОГО БЛОКА В
НЕКОТОРОМ ОТРЕЗКЕ ВСЕГДА НЕ МЕНЬШЕ, ЧЕМ НАИБОЛЬШИЙ ЭЛЕМЕНТ В ПРЕДЫДУЩЕМ
БЛОКЕ ЭТОГО ОТРЕЗКА; ЭТО СООТВЕТСТВУЕТ "1~СТЕПЕНИ СВОБОДЫ". фИНСМОР
ПРЕДЛОЖИЛ ОСЛАБИТЬ ЭТО УСЛОВИЕ ДО "$m$~СТЕПЕНЕЙ СВОБОДЫ"; НОВОЕ УСЛОВИЕ
НЕ ТРЕБУЕТ, ЧТОБЫ НАИМЕНЬШИЙ ЭЛЕМЕНТ КАЖДОГО БЛОКА БЫЛ НЕ МЕНЬШЕ, ЧЕМ
НАИБОЛЬШИЙ ЭЛЕМЕНТ ПРЕДЫДУЩЕГО БЛОКА, НО ОН \emph{НЕ ДОЛЖЕН БЫТЬ МЕНЬШЕ,
ЧЕМ НАИБОЛЬШИЕ ЭЛЕМЕНТЫ КАКИХ-ТО $m$~ПРЕДЫДУЩИХ БЛОКОВ ТОГО ЖЕ ОТРЕЗКА.}
чАПИСИ В ОТДЕЛЬНОМ БЛОКЕ УПОРЯДОЧЕНЫ, КАК И РАНЕЕ, НО СОСЕДНИЕ БЛОКИ НЕ
ОБЯЗАНЫ БЫТЬ ВЗАИМНО УПОРЯДОЧЕННЫМИ.

%%309

яРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО БЛОКИ СОДЕРЖАТ ТОЛЬКО ПО ДВЕ ЗАПИСИ; СЛЕДУЮЩАЯ
ПОСЛЕДОВАТЕЛЬНОСТЬ БЛОКОВ ЯВЛЯЕТСЯ ОТРЕЗКОМ С ТРЕМЯ СТЕПЕНЯМИ СВОБОДЫ:
$$
\vert 08\ 50 \vert 06\ 90 \vert 17\ 27 \vert 42\ 67 \vert 51\ 89 \vert
\eqno (1)
$$

ёЛЕДУЮЩИЙ БЛОК, КОТОРЫЙ МОЖЕТ БЫТЬ ЧАСТЬЮ ЭТОГО ОТРЕЗКА, ДОЛЖЕН НАЧИНАТЬСЯ
С ЭЛЕМЕНТА, НЕ МЕНЬШЕГО, ЧЕМ ТРЕТИЙ ПО ПОРЯДКУ ЭЛЕМЕНТ
МНОЖЕСТВА~$\set{50, 90, 27, 67, 89}$, СЧИТАЯ ОТ НАИБОЛЬШЕГО, Т.~Е.\ НЕ
МЕНЬШЕ~67. яОСЛЕДОВАТЕЛЬНОСТЬ~(1) НЕ ЯВЛЯЕТСЯ ОТРЕЗКОМ С ДВУМЯ СТЕПЕНЯМИ
СВОБОДЫ, ТАК КАК 17~МЕНЬШЕ, ЧЕМ~50 И~90.

юТРЕЗОК С $m$~СТЕПЕНЯМИ СВОБОДЫ В ПРОЦЕССЕ ЧТЕНИЯ В СЛЕДУЮЩЕЙ ФАЗЕ
СОРТИРОВКИ МОЖЕТ БЫТЬ ПРЕОБРАЗОВАН ТАКИМ ОБРАЗОМ, ЧТО ДЛЯ ВСЕХ
ПРАКТИЧЕСКИХ ЦЕЛЕЙ ОН БУДЕТ ОТРЕЗКОМ В ОБЫЧНОМ СМЫСЛЕ. эАЧНЕМ С ЧТЕНИЯ
ПЕРВЫХ $m$~БЛОКОВ В $m$~БУФЕРОВ И БУДЕМ ПРОИЗВОДИТЬ $m\hbox{-ПУТЕВОЕ}$
СЛИЯНИЕ ИХ; КОГДА ОДИН ИЗ БУФЕРОВ ИСЧЕРПАЕТСЯ, ПОМЕСТИМ В НЕГО
$(m+1)\hbox{-Й}$~БЛОК И~Т.~Д. ЄАКИМ ОБРАЗОМ, МЫ МОЖЕМ ВОССТАНОВИТЬ
ОТРЕЗОК В ВИДЕ ОДНОЙ УПОРЯДОЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, ТАК КАК ПЕРВОЕ
СЛОВО КАЖДОГО ВНОВЬ СЧИТЫВАЕМОГО БЛОКА ДОЛЖНО БЫТЬ БОЛЬШЕ ИЛИ РАВНО
ПОСЛЕДНЕМУ СЛОВУ ТОЛЬКО ЧТО ИСЧЕРПАННОГО БЛОКА (ЕСЛИ ОНО НЕ БЫЛО МЕНЬШЕ,
ЧЕМ НАИБОЛЬШИЕ ЭЛЕМЕНТЫ КАКИХ-ЛИБО $m$~БЛОКОВ, ПРЕДШЕСТВУЮЩИХ ЕМУ). ¤ТОТ
МЕТОД ПРЕОБРАЗОВАНИЯ ОТРЕЗКА, В СУЩНОСТИ, ЯВЛЯЕТСЯ $m\hbox{-ПУТЕВЫМ}$
СЛИЯНИЕМ, ИСПОЛЬЗУЮЩИМ ТОЛЬКО ОДНО ЛЕНТОЧНОЕ УСТРОЙСТВО ДЛЯ ВСЕХ ВХОДНЫХ
БЛОКОВ!

яРОЦЕДУРА ПРЕОБРАЗОВАНИЯ ДЕЙСТВУЕТ КАК СОПРОГРАММА, К КОТОРОЙ ОБРАЩАЮТСЯ
КАЖДЫЙ РАЗ, КОГДА НУЖНО ПОЛУЧИТЬ ОДНУ ОЧЕРЕДНУЮ ЗАПИСЬ ОТРЕЗКА. ьЫ МОЖЕМ
ПРЕОБРАЗОВЫВАТЬ РАЗЛИЧНЫЕ ОТРЕЗКИ С РАЗЛИЧНЫХ ЛЕНТОЧНЫХ УСТРОЙСТВ И С
РАЗЛИЧНЫМИ СТЕПЕНЯМИ СВОБОДЫ И СЛИВАТЬ ПОЛУЧАЮЩИЕСЯ ОТРЕЗКИ---ВСЕ В ОДНО И
ТО ЖЕ ВРЕМЯ. ¤ТО, ПО СУЩЕСТВУ, ПОДОБНО ТОМУ, КАК ЕСЛИ БЫ МЫ ЧЕТЫРЕХПУТЕВОЕ
СЛИЯНИЕ, РАССМОТРЕННОЕ В НАЧАЛЕ ЭТОГО ПУНКТА, ПРЕДСТАВИЛИ СЕБЕ КАК
НЕСКОЛЬКО ДВУХПУТЕВЫХ СЛИЯНИЙ, ПРОИСХОДЯЩИХ ОДНОВРЕМЕННО.

¤ТА ОСТРОУМНАЯ ИДЕЯ ДО СИХ ПОР НЕ ПРОАНАЛИЗИРОВАНА ДО КОНЦА. шМЕЮТСЯ
НЕКОТОРЫЕ ПРЕДВАРИТЕЛЬНЫЕ РЕЗУЛЬТАТЫ, ПОКАЗЫВАЮЩИЕ, ЧТО, КОГДА
$P$~ВЕЛИКО ПО СРАВНЕНИЮ С РАЗМЕРОМ БЛОКА, ДЛИНА ОТРЕЗКА ПРИ~$m=2$
ПРИБЛИЗИТЕЛЬНО РАВНА~$2.1P$, ОНА РАВНА~$2.3P$ ПРИ~$m=4$ И~$2.5P$ ПРИ~$m=8$.
ЄАКОЕ УВЕЛИЧЕНИЕ, БЫТЬ МОЖЕТ, НЕДОСТАТОЧНО, ЧТОБЫ ОПРАВДАТЬ УСЛОЖНЕНИЕ
АЛГОРИТМА. ё ДРУГОЙ СТОРОНЫ, МЕТОД МОЖЕТ ОКАЗАТЬСЯ ВЫГОДНЫМ, ЕСЛИ НА.
ПРОТЯЖЕНИИ ВТОРОГО ЭТАПА СОРТИРОВКИ ЕСТЬ МЕСТО ДЛЯ ДОВОЛЬНО БОЛЬШОГО ЧИСЛА
БУФЕРОВ.

%%310

\section *эАТУРАЛЬНЫЙ ВЫБОР. фРУГОЙ ПУТЬ УВЕЛИЧЕНИЯ ДЛИНЫ ОТРЕЗКОВ,
 ПОРОЖДАЕМЫХ ВЫБОРОМ С ЗАМЕЩЕНИЕМ, БЫЛ ИССЛЕДОВАН є.~ф.~ЇРЭЙЗЕРОМ
И~ў.~ъ.~єОНОМ. шХ ИДЕЯ СОСТОИТ В ТОМ, ЧТОБЫ СЛЕДОВАТЬ АЛГОРИТМУ~R, НО,
КОГДА НА ШАГЕ~R4 $|KEY|(|Q|)<|LASTKEY|$, НОВАЯ ЗАПИСЬ~$|RECORD|(|Q|)$ НЕ
ОСТАЕТСЯ В ДЕРЕВЕ,, А ВЫВОДИТСЯ В НЕКОТОРЫЙ ВНЕШНИЙ \emph{РЕЗЕРВУАР} И
ЧИТАЕТСЯ НОВАЯ ЗАПИСЬ. ¤ТОТ ПРОЦЕСС ПРОДОЛЖАЕТСЯ ДО ТЕХ ПОР, ПОКА В
РЕЗЕРВУАРЕ НЕ ОКАЖЕТСЯ ОПРЕДЕЛЕННОЕ КОЛИЧЕСТВО ЗАПИСЕЙ~$P'$; ТОГДА
ОСТАТОК ТЕКУЩЕГО ОТРЕЗКА ВЫВОДИТСЯ ИЗ ДЕРЕВА, И ЭЛЕМЕНТЫ РЕЗЕРВУАРА
ИСПОЛЬЗУЮТСЯ В КАЧЕСТВЕ ИСХОДНЫХ ДАННЫХ ДЛЯ СЛЕДУЮЩЕГО ОТРЕЗКА.

¤ТОТ МЕТОД ДОЛЖЕН ПОРОЖДАТЬ БОЛЕЕ ДЛИННЫЕ ОТРЕЗКИ, ЧЕМ ВЫБОР С ЗАМЕЩЕНИЕМ,
ПОСКОЛЬКУ ОН "ОБХОДИТ" ВНОВЬ ПОСТУПАЮЩИЕ "МЕРТВЫЕ" ЗАПИСИ, ВМЕСТО ТОГО
ЧТОБЫ ПОЗВОЛЯТЬ ИМ ЗАПОЛНЯТЬ ДЕРЕВО; НО ЕМУ ТРЕБУЕТСЯ ДОПОЛНИТЕЛЬНОЕ ВРЕМЯ
НА ОБМЕН С РЕЗЕРВУАРОМ. ъОГДА~$P'>P$, НЕКОТОРЫЕ ЗАПИСИ МОГУТ
ОКАЗЫВАТЬСЯ В РЕЗЕРВУАРЕ ДВАЖДЫ, НО ПРИ~$P'\le P$ ТАКОГО СЛУЧИТЬСЯ НЕ МОЖЕТ.

ЇРЭЙЗЕР И~єОН, ПРОВЕДЯ ОБШИРНЫЕ ЭМПИРИЧЕСКИЕ ИСПЫТАНИЯ СВОЕГО МЕТОДА,
ЗАМЕТИЛИ, ЧТО, КОГДА~$P$ ДОСТАТОЧНО ВЕЛИКО (СКАЖЕМ, $P\ge 32$) И~$P'=P$,
СРЕДНЯЯ ДЛИНА ОТРЕЗКА ДЛЯ СЛУЧАЙНЫХ ДАННЫХ ОКАЗЫВАЕТСЯ РАВНОЙ~$eP$,
ГДЕ~$e\approx 2.718$---ОСНОВАНИЕ НАТУРАЛЬНЫХ ЛОГАРИФМОВ. ¤ТО ЯВЛЕНИЕ, А
ТАКЖЕ ТОТ ФАКТ, ЧТО МЕТОД БЫЛ ПОЛУЧЕН КАК ЭВОЛЮЦИОННОЕ РАЗВИТИЕ ПРОСТОГО
ВЫБОРА С ЗАМЕЩЕНИЕМ, ПОСЛУЖИЛИ ДЛЯ НИХ НЕПОСРЕДСТВЕННЫМ
ОСНОВАНИЕМ НАЗВАТЬ СВОЙ МЕТОД \dfn{НАТУРАЛЬНЫМ ВЫБОРОМ.}

ьОЖНО ДОКАЗАТЬ "НАТУРАЛЬНЫЙ" ЗАКОН ДЛЯ ДЛИНЫ ОТРЕЗКА, ВНОВЬ
ВОСПОЛЬЗОВАВШИСЬ АНАЛОГИЕЙ СО СНЕГООЧИСТИТЕЛЕМ НА РИС.~64 И ПРИМЕНИВ
ЭЛЕМЕНТАРНЫЙ МАТЕМАТИЧЕСКИЙ АНАЛИЗ. яУСТЬ~$L$ ОБОЗНАЧАЕТ ДЛИНУ ПУТИ,
a~$x(t)$---ПОЛОЖЕНИЕ СНЕГООЧИСТИТЕЛЯ В МОМЕНТ~$t$ ПРИ~$0 \le t \le T$.
яРЕДПОЛОЖИМ, ЧТО В МОМЕНТ~$T$ РЕЗЕРВУАР ЗАПОЛНЯЕТСЯ; В ЭТОТ МОМЕНТ ПАДЕНИЕ
СНЕГА ВРЕМЕННО ПРЕКРАЩАЕТСЯ, ПОКА СНЕГООЧИСТИТЕЛЬ ВОЗВРАЩАЕТСЯ В ИСХОДНОЕ
ПОЛОЖЕНИЕ (СЧИЩАЯ $P$~СНЕЖИНОК, ОСТАВШИХСЯ НА ЕГО ПУТИ). ёИТУАЦИЯ ТАКАЯ
ЖЕ, КАК И РАНЕЕ, ТОЛЬКО "УСЛОВИЯ РАВНОВЕСИЯ" ДРУГИЕ---ВМЕСТО $P$~СНЕЖИНОК НА
ВСЕЙ ДОРОГЕ В ЛЮБОЙ МОМЕНТ ВРЕМЕНИ МЫ ИМЕЕМ $P$~СНЕЖИНОК ПЕРЕД
СНЕГООЧИСТИТЕЛЕМ И РЕЗЕРВУАР (ЗА СНЕГООЧИСТИТЕЛЕМ), ЗАПОЛНЯЮЩИЙСЯ ДО
УРОВНЯ В $P$~СНЕЖИНОК. т ТЕЧЕНИЕ ИНТЕРВАЛА ВРЕМЕНИ~$dt$ СНЕГООЧИСТИТЕЛЬ
ПРОДВИГАЕТСЯ НА~$dx$, ЕСЛИ ВЫВОДЯТСЯ $h(x, t)dx$~ЗАПИСЕЙ, ГДЕ~$h(x,
t)$---ТОЛЩИНА СЛОЯ СНЕГА В МОМЕНТ ВРЕМЕНИ~$t$ В ТОЧКЕ~$x=x(t)$, ИЗМЕРЯЕМАЯ В
СООТВЕТСТВУЮЩИХ ЕДИНИЦАХ; СЛЕДОВАТЕЛЬНО, $h(x, t)=h(x, 0)+Kt$ ДЛЯ ВСЕХ~$x$.
 ЄАК КАК ЧИСЛО ЗАПИСЕЙ В ПАМЯТИ ОСТАЕТСЯ ПОСТОЯННЫМ, ТО $h(x, t)dx$~ЕСТЬ
ТАКЖЕ ЧИСЛО ЗАПИСЕЙ, ВВОДИМЫХ \emph{ПЕРЕД} СНЕГООЧИСТИТЕЛЕМ, А
ИМЕННО~$Kdt(L-x)$, ГДЕ~$K$---СКОРОСТЬ ПАДЕНИЯ СНЕГА (РИС.~67). ЄАКИМ ОБРАЗОМ,
$$
{dx\over dt}={K(L-x)\over h(x,t)}.
\eqno(2)
$$
%%311

ъ СЧАСТЬЮ, ОКАЗЫВАЕТСЯ, ЧТО~$h(x,t)$---КОНСТАНТА, И ОНА РАВНА~$KT$ ПРИ
ВСЕХ~$x=x(t)$ И~$0\le t \le T$, ТАК КАК СНЕГ ПАДАЕТ РАВНОМЕРНО В
ТОЧКУ~$x(t)$ В ТЕЧЕНИЕ $T-t$~ЕДИНИЦ ВРЕМЕНИ ПОСЛЕ ТОГО, КАК
СНЕГООЧИСТИТЕЛЬ ПРОХОДИТ ЭТУ ТОЧКУ, ПЛЮС $t$~ЕДИНИЦ ВРЕМЕНИ ПЕРЕД ТЕМ, КАК
ОН ВЕРНЕТСЯ. шНЫМИ СЛОВАМИ, СНЕГООЧИСТИТЕЛЬ ВИДИТ ПЕРЕД СОБОЙ ВСЕ ВРЕМЯ
ОДИНАКОВЫЙ СЛОЙ СНЕГА НА ПРОТЯЖЕНИИ ВСЕГО ПУТИ, ЕСЛИ ДОПУСТИТЬ, ЧТО
ДОСТИГНУТ УСТАНОВИВШИЙСЯ РЕЖИМ, КОГДА ЭТОТ ПУТЬ ВСЕ ВРЕМЯ ОДИН И ТОТ ЖЕ.
ёЛЕДОВАТЕЛЬНО, ОБЩЕЕ КОЛИЧЕСТВО СЧИЩАЕМОГО СНЕГА (ДЛИНА ОТРЕЗКА)
ЕСТЬ~$KTL$,
\picture{ЁИС.~67. тВОДИТСЯ И ВЫВОДИТСЯ РАВНОЕ КОЛИЧЕСТВО СНЕГА; ЗА
ВРЕМЯ~$dt$ СНЕГООЧИСТИТЕЛЬ ПЕРЕМЕЩАЕТСЯ НА~$dx$.}
А КОЛИЧЕСТВО СНЕГА В ПАМЯТИ ЕСТЬ КОЛИЧЕСТВО СНЕГА, СЧИЩАЕМОГО ПОСЛЕ
МОМЕНТА~$T$, А ИМЕННО~$KT(L-x(T))$.

ЁЕШЕНИЕМ УРАВНЕНИЯ~(2) ПРИ УСЛОВИИ, ЧТО~$x(0)=0$, БУДЕТ
$$
x(t)=L(1-e^{-t/T}).
\eqno(3)
$$
ёЛЕДОВАТЕЛЬНО, $P=KTLe^{-1}=\hbox{(ДЛИНА ОТРЕЗКА)}/e$---ЭТО КАК РАЗ ТО, ЧТО
МЫ И ХОТЕЛИ ДОКАЗАТЬ.

т УПР.~21--23 ПОКАЗАНО, ЧТО ЭТОТ АНАЛИЗ МОЖНО РАСПРОСТРАНИТЬ НА СЛУЧАЙ
ПРОИЗВОЛЬНОГО~$P'$; НАПРИМЕР, КОГДА~$P'=2P$, СРЕДНЯЯ ДЛИНА ОТРЕЗКА
ОКАЗЫВАЕТСЯ РАВНОЙ~$e^\theta(e-\theta)P$,
ГДЕ~$\theta={1\over2}(e-\sqrt{e^2-4})$,---РЕЗУЛЬТАТ, КОТОРЫЙ ВРЯД ЛИ МОЖНО БЫЛО
ПРЕДПОЛОЖИТЬ ЗАРАНЕЕ! т ТАБЛ.~2 ПРИВОДИТСЯ ЗАВИСИМОСТЬ МЕЖДУ ДЛИНОЙ
ОТРЕЗКА И РАЗМЕРОМ РЕЗЕРВУАРА; С ПОМОЩЬЮ ЭТОЙ ТАБЛИЦЫ МОЖНО ОЦЕНИТЬ
ПОЛЕЗНОСТЬ НАТУРАЛЬНОГО ВЫБОРА ДЛЯ КОНКРЕТНОЙ МАШИНЫ В ТОЙ ИЛИ ИНОЙ СИТУАЦИИ.

\section *рНАЛИЗ ВЫБОРА С ЗАМЕЩЕНИЕМ. тЕРНЕМСЯ ТЕПЕРЬ К СЛУЧАЮ ВЫБОРА С
ЗАМЕЩЕНИЕМ БЕЗ ВСПОМОГАТЕЛЬНОГО РЕЗЕРВУАРА. рНАЛОГИЯ СО СНЕГООЧИСТИТЕЛЕМ
ДАЕТ ДОВОЛЬНО ХОРОШУЮ ОЦЕНКУ СРЕДНЕЙ ДЛИНЫ ОТРЕЗКОВ, ПОЛУЧАЕМЫХ ПРИ ВЫБОРЕ
С ЗАМЕЩЕНИЕМ "В ПРЕДЕЛЕ", ТЕМ НЕ МЕНЕЕ МОЖНО ПОЛУЧИТЬ ЗНАЧИТЕЛЬНО БОЛЕЕ
ТОЧНУЮ ИНФОРМАЦИЮ ОБ АЛГОРИТМЕ~R, ПРИМЕНЯЯ ФАКТЫ ОБ ОТРЕЗКАХ В
ПЕРЕСТАНОВКАХ, ИЗУЧЕННЫХ НАМИ В П.~5.1.3. фЛЯ УДОБСТВА БУДЕМ СЧИТАТЬ, ЧТО
ВХОДНОЙ ФАЙЛ ЯВЛЯЕТСЯ ПОСЛЕДОВАТЕЛЬНОСТЬЮ  (ПРОИЗВОЛЬНОЙ ДЛИНЫ)
НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ, РАСПОЛОЖЕННЫХ МЕЖДУ~0 И~1.

%%312
\htable{ЄАБЛИЦА 2}%
{фЛИНА ОТРЕЗКОВ ПРИ НАТУРАЛЬНОМ ВЫБОРЕ}%
{\strut\hfill$#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\bskip&
 \hfill$\qquad#$\bskip&\bskip\hfill$#$\bskip&\bskip\hfill$#$\cr
\omit\hfill ЁАЗМЕР \hfill & \omit\hfill фЛИНА\hfill & & \omit\hfill ЁАЗМЕР
\hfill & фЛИНА \hfill\cr
\omit\hfill РЕЗЕРВУАРА \hfill  & \omit\hfill ОТРЕЗКА\hfill &\omit\hfill
яАРАМЕТР\hfill &\omit\hfill РЕЗЕРВУАРА \hfill & \omit\hfill ОТРЕЗКА\hfill
& \omit\hfill яАРАМЕТР\hfill \cr
\noalign{\hrule}
1.00000P & 2.71828P & 1.00000 &  0.38629P &  2.00000P & 0.69315\cr
2.00000P & 3.53487P & 1.43867 &  1.30432P &  3.юююююP & 1.15881\cr
3.00000P & 4.16220P & 1.74773 &  2.72294P &  4.00000P & 1.66862\cr
4.00000P & 4.69445P & 2.01212 &  4.63853P &  5.00000P & 2.16714\cr
5.00000P & 5.16369P & 2.24038 & 21.72222P & 10.00000P & 4.66667\cr
10.00000P& 7.00877P & 3.17122 &  5.29143P &  5.29143P & 2.31329\cr
\noalign{\hrule}
\noalign{\hbox{\strut "яАРАМЕТР"~$k+\theta$ ОПРЕДЕЛЕН В УПР.~22}}
}

яУСТЬ
$$
g_P(z_1, z_2,~\ldots, z_k)=\sum_{l_1, l_2,~\ldots, l_k\ge 0}
a_P(l_1, l_2,~\ldots, l_k)z_1^{l_1} z_2^{l_2}\ldots z_k^{l_k}
$$
---ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ ДЛИНЫ ОТРЕЗКА, ПОЛУЧЕННОГО
ПРИ $P\hbox{-ПУТЕВОМ}$~ВЫБОРЕ С ЗАМЕЩЕНИЕМ, ПРИМЕНЕННОМ К. ТАКОМУ ФАЙЛУ,
 ГДЕ $a_P(l_1, l_2,~\ldots, l_k)$~ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО ПЕРВЫЙ
ОТРЕЗОК ИМЕЕТ ДЛИНУ~$l_1$, ВТОРОЙ---ДЛИНУ~$l_2$,~\dots, $k\hbox{-Й}$ ИМЕЕТ
ДЛИНУ~$l_k$. сУДЕМ ОСНОВЫВАТЬСЯ НА СЛЕДУЮЩЕЙ "ТЕОРЕМЕ НЕЗАВИСИМОСТИ", ЄАК
КАК ОНА СВОДИТ НАШ АНАЛИЗ К СЛУЧАЮ~$P=1$.

\proclaim ЄЕОРЕМА~K.
$g_P(z_1, z_2,~\ldots, z_k)=g_1(z_1, z_2,~\ldots, z_k)^P$.

\proof яУСТЬ ИСХОДНЫЕ КЛЮЧИ СУТЬ~$X_1$, $X_2$, $X_3$,~$\ldots\,
$. рЛГОРИТМ~R РАЗДЕЛЯЕТ ИХ НА $P$~ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ В СООТВЕТСТВИИ
С ТЕМ, В КАКОЙ ВНЕШНИЙ УЗЕЛ ДЕРЕВА ОНИ ПОПАДАЮТ;
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, СОДЕРЖАЩАЯ~$X_n$, ОПРЕДЕЛЯЕТСЯ ЗНАЧЕНИЯМИ~$X_1$,
~\dots, $X_{n-1}$. ЄАКИМ ОБРАЗОМ, ЭТИ ПОДПОСЛЕДОВАТЕЛЬНОСТИ  ЯВЛЯЮТСЯ
НЕЗАВИСИМЫМИ ПОСЛЕДОВАТЕЛЬНОСТЯМИ НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ЧИСЕЛ,
РАСПОЛОЖЕННЫХ МЕЖДУ~0 И~1. ъРОМЕ ТОГО, ВЫХОД ВЫБОРА С ЗАМЕЩЕНИЕМ В
ТОЧНОСТИ СОВПАДАЕТ С РЕЗУЛЬТАТОМ $P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ, ЕСЛИ ЕГО
ПРОИЗВЕСТИ НАД ЭТИМИ ПОДПОСЛЕДОВАТЕЛЬНОСТЯМИ; НЕКОТОРЫЙ ЭЛЕМЕНТ
ПРИНАДЛЕЖИТ $j\hbox{-МУ}$~ОТРЕЗКУ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ТОГДА И ТОЛЬКО
ТОГДА, КОГДА ОН ПРИНАДЛЕЖИТ $j\hbox{-МУ}$~ОТРЕЗКУ, ПОЛУЧЕННОМУ ПРИ
ВЫБОРЕ С ЗАМЕЩЕНИЕМ (ТАК КАК НА ШАГЕ~R4 КЛЮЧИ~|LASTKEY| И~$|KEY|(|Q|)$
ПРИНАДЛЕЖАТ ОДНОЙ ПОДПОСЛЕДОВАТЕЛЬНОСТИ).

шНАЧЕ ГОВОРЯ, МОЖНО СЧИТАТЬ, ЧТО АЛГОРИТМ~R ПРИМЕНЯЕТСЯ К $P$~СЛУЧАЙНЫМ
НЕЗАВИСИМЫМ ИСХОДНЫМ ФАЙЛАМ И ЧТО ШАГ~R4 ЧИТАЕТ СЛЕДУЮЩУЮ ЗАПИСЬ ИЗ
ФАЙЛА, СООТВЕТСТВУЮЩЕГО ВНЕШНЕМУ УЗЛУ~|Q|; В ЭТОМ СМЫСЛЕ РАССМАТРИВАЕМЫЙ
АЛГОРИТМ ЭКВИВАЛЕНТЕН  $P\hbox{-ПУТЕВОМУ}$ СЛИЯНИЮ, ГДЕ КОНЦЫ ОТРЕЗКОВ
ОТМЕЧАЮТСЯ УБЫВАНИЕМ ЭЛЕМЕНТОВ.

ЄАКИМ ОБРАЗОМ, НА ВЫХОДЕ БУДУТ ОТРЕЗКИ ДЛИН~$(l_1,~\ldots, l_k)$ ТОГДА И
ТОЛЬКО ТОГДА, КОГДА ПОДПОСЛЕДОВАТЕЛЬНОСТИ СОСТОЯТ ИЗ
%% 313
ОТРЕЗКОВ ДЛИН~$(l_{11},~\ldots, l_{1k})$,~\dots, $(l_{P1},~\ldots,
l_{Pk})$ СООТВЕТСТВЕННО; ГДЕ~$l_{ij}$---НЕКОТОРЫЕ НЕОТРИЦАТЕЛЬНЫЕ ЦЕЛЫЕ
ЧИСЛА, УДОВЛЕТВОРЯЮЩИЕ СООТНОШЕНИЮ~$\sum_{1\le i \le P} l_{ij}=l_j$
ПРИ~$1\le j \le k$. юТСЮДА СЛЕДУЕТ, ЧТО
$$
a_P(l_1,~\ldots, l_k)=\sum_{
{\scriptstyle l_{11}+\cdots+l_{P1}=l_1 \atop
\scriptstyle \vdots} \atop
\scriptstyle l_{1k}+\cdots+l_{Pk}=l_k
}a_1(l_{11},~\ldots, l_{1k})\ldots a_1(l_{P1},~\ldots, l_{Pk}),
$$
ЧТО ЭКВИВАЛЕНТНО ИСКОМОМУ РЕЗУЛЬТАТУ.
\proofend

т П.~5.1.3 МЫ ИЗУЧИЛИ СРЕДНЕЕ ЗНАЧЕНИЕ~$L_k$---ДЛИНЫ $k\hbox{-ГО}$~ОТРЕЗКА
ПРИ~$P=1$ (ЭТИ ЗНАЧЕНИЯ ПРИВЕДЕНЫ В ТАБЛ.~5.1.3-2). шЗ ТЕОРЕМЫ~K СЛЕДУЕТ,
ЧТО СРЕДНЯЯ ДЛИНА $k\hbox{-ГО}$~ОТРЕЗКА ПРИ ЛЮБОМ~$P$ В $P$~РАЗ БОЛЬШЕ
СРЕДНЕЙ ДЛИНЫ ПРИ~$P=1$, ОНА РАВНА~$L_kP$;
ДИСПЕРСИЯ ТАКЖЕ В $P$~РАЗ БОЛЬШЕ, ТАК ЧТО СТАНДАРТНОЕ ОТКЛОНЕНИЕ ДЛИНЫ
ОТРЕЗКА ПРОПОРЦИОНАЛЬНО~$\sqrt{P}$. ¤ТИ РЕЗУЛЬТАТЫ БЫЛИ ВПЕРВЫЕ ПОЛУЧЕНЫ
с.~фЖ.~уЭССНЕР ОКОЛО 1958~Г.

ЄАКИМ ОБРАЗОМ, ПЕРВЫЙ ОТРЕЗОК, ПОЛУЧЕННЫЙ ДЛЯ СЛУЧАЙНЫХ ДАННЫХ
АЛГОРИТМОМ~R, БУДЕТ ИМЕТЬ ДЛИНУ, ПРИБЛИЖЕННО РАВНУЮ
$(e-1)P\approx 1.718P$~ЗАПИСЕЙ,
ВТОРОЙ---ПРИБЛИЖЕННО~$(e^2-2e)P\approx 1.952P$, ТРЕТИЙ---$1.996P$; ДЛИНА
СЛЕДУЮЩИХ ОТРЕЗКОВ БУДЕТ ОЧЕНЬ БЛИЗКА К~$2P$, ПОКА МЫ НЕ ДОЙДЕМ ДО
ПОСЛЕДНИХ ДВУХ ОТРЕЗКОВ (СМ. УПР.~14). ёТАНДАРТНОЕ ОТКЛОНЕНИЕ ДЛИНЫ
БОЛЬШИНСТВА ЭТИХ ОТРЕЗКОВ ПРИБЛИЖЕННО
РАВНО~$\sqrt{(4e-10)P}\approx 0.934 \sqrt{P}$
[{\sl CACM,\/} {\bf 6} (1963), 685--687].

ъРОМЕ ЭТОГО, СОГЛАСНО УПР.~5.1.3-10, \emph{СУММАРНАЯ} ДЛИНА ПЕРВЫХ
$k$~ОТРЕЗКОВ БУДЕТ ДОВОЛЬНО БЛИЗКА К~$\left(2k-{1\over3}\right)P$ СО
СТАНДАРТНЫМ
ОТКЛОНЕНИЕМ~$\left(\left({2\over3}k+{2\over9}\right)P\right)^{1/2}$.
яРОИЗВОДЯЩИЕ ФУНКЦИИ~$g_1(z, z,~\ldots, z)$ И~$g_1(1,~\ldots, 1, z)$
ВЫВОДЯТСЯ В УПР.~5.1.3-9 И~11.

т ПРИВЕДЕННОМ ВЫШЕ АНАЛИЗЕ ПРЕДПОЛАГАЛОСЬ, ЧТО ИСХОДНЫЙ ФАЙЛ БЕСКОНЕЧНО
ДЛИННЫЙ, НО ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~K ПОКАЗЫВАЕТ, ЧТО ТОЧНО ТАКАЯ ЖЕ
ВЕРОЯТНОСТЬ~$a_P(l_1,~\ldots, l_k)$ ПОЛУЧИЛАСЬ БЫ В СЛУЧАЕ ЛЮБОЙ СЛУЧАЙНОЙ
ИСХОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, СОДЕРЖАЩЕЙ ПО КРАЙНЕЙ МЕРЕ
$l_1+\cdots+l_k+P$~ЭЛЕМЕНТОВ. ёЛЕДОВАТЕЛЬНО, ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ
ПРИМЕНИМЫ ДЛЯ ФАЙЛА РАЗМЕРА, СКАЖЕМ, $N > (2K+1)P$ В СИЛУ МАЛОЙ ВЕЛИЧИНЫ
СТАНДАРТНОГО ОТКЛОНЕНИЯ.

ьЫ ПОЗНАКОМИМСЯ С РЯДОМ ПРИМЕНЕНИЙ, В КОТОРЫХ СХЕМА СЛИЯНИЯ ТРЕБУЕТ,
ЧТОБЫ НЕКОТОРЫЕ ОТРЕЗКИ БЫЛИ ВОЗРАСТАЮЩИМИ, А НЕКОТОРЫЕ---УБЫВАЮЩИМИ.
яОСКОЛЬКУ ОСТАТОК, НАКАПЛИВАЮЩИЙСЯ В ПАМЯТИ У КОНЦА ВОЗРАСТАЮЩЕГО ОТРЕЗКА,
ИМЕЕТ ТЕНДЕНЦИЮ СОДЕРЖАТЬ ЧИСЛА, В СРЕДНЕМ МЕНЬШИЕ, ЧЕМ СЛУЧАЙНЫЕ ДАННЫЕ,
ТО ИЗМЕНЕНИЕ НАПРАВЛЕНИЯ УПОРЯДОЧЕНИЯ УМЕНЬШАЕТ СРЕДНЮЮ ДЛИНУ ОТРЕЗКОВ.
ЁАССМОТРИМ, НАПРИМЕР, СНЕГООЧИСТИТЕЛЬ, КОТОРЫЙ ДОЛЖЕН
%%314
ВЫПОЛНЯТЬ РАЗВОРОТ КАЖДЫЙ РАЗ, КАК ОН ДОСТИГАЕТ КОНЦА ПРЯМОЙ ДОРОГИ;
ОН БУДЕТ ОЧЕНЬ БЫСТРО ПЕРЕДВИГАТЬСЯ ПО ТОЛЬКО ЧТО ОЧИЩЕННОМУ УЧАСТКУ. т
СЛУЧАЕ ИЗМЕНЯЕМОГО НАПРАВЛЕНИЯ ДЛИНА ОТРЕЗКОВ ДЛЯ СЛУЧАЙНЫХ ДАННЫХ
ИЗМЕНЯЕТСЯ МЕЖДУ~$1.5P$ И~$2P$ (СМ.~УПР.~24).

\excercises
\ex[10] ъАКИМ БУДЕТ ШАГ 4 В ПРИМЕРЕ ЧЕТЫРЕХ ПУТЕВОГО СЛИЯНИЯ В НАЧАЛЕ
ЭТОГО ПУНКТА?

\ex[12] ъАКИЕ ИЗМЕНЕНИЯ ПРОИЗОШЛИ БЫ В ДЕРЕВЕ РИС.~63, ЕСЛИ БЫ КЛЮЧ~$061$
БЫЛ ЗАМЕНЕН КЛЮЧОМ~$612$?

\ex[16] (¤.~Ї.~ьУР.) ўТО ПОЛУЧИТСЯ В РЕЗУЛЬТАТЕ ПРИМЕНЕНИЯ
ЧЕТЫРЕХПУТЕВОГО ВЫБОРА С ЗАМЕЩЕНИЕМ К ПОСЛЕДОВАТЕЛЬНЫМ СЛОВАМ СЛЕДУЮЩЕГО
ПРЕДЛОЖЕНИЯ\note{1}%
{тОСЕМЬДЕСЯТ СЕМЬ ЛЕТ ТОМУ НАЗАД НАШИ ПРЕДКИ ОСНОВАЛИ НА ЭТОМ КОНТИНЕНТЕ
НОВУЮ НАЦИЮ, ПОСВЯТИВШУЮ СЕБЯ ДЕЛУ СВОБОДЫ И УБЕЖДЕННУЮ В ТОМ, ЧТО ВСЕ
ЛЮДИ СОЗДАНЫ РАВНЫМИ.---{\sl яРИМ. ПЕРЕВ.\/}}
{\medskip\narrower\tt\noindent
fourscore and seven years ago our fathers brought forth on this continent
a new nation conceived in liberty and dedicated to the proposition that
all men are created equal.
\medskip\noindent}
(шСПОЛЬЗУЙТЕ ОБЫЧНЫЙ АЛФАВИТНЫЙ ПОРЯДОК, РАССМАТРИВАЯ КАЖДОЕ СЛОВО
КАК ОДИН КЛЮЧ.)

\ex[16] яРИМЕНИТЕ ЧЕТЫРЕХПУТЕВОЙ \emph{НАТУРАЛЬНЫЙ} ВЫБОР К ПРЕДЛОЖЕНИЮ
ИЗ УПР.~3, ИСПОЛЬЗУЯ РЕЗЕРВУАР ЕМКОСТИ~4.

\ex[00] тЕРНО ЛИ, ЧТО ВЫБОР С ЗАМЕЩЕНИЕМ, ИСПОЛЬЗУЮЩИЙ ДЕРЕВО, РАБОТАЕТ,
ТОЛЬКО ЕСЛИ $P$~ЕСТЬ СТЕПЕНЬ ДВОЙКИ ИЛИ СУММА ДВУХ СТЕПЕНЕЙ ДВОЙКИ?

\ex[15] т АЛГОРИТМЕ~R УКАЗЫВАЕТСЯ, ЧТО $P$~ДОЛЖНО БЫТЬ~$\ge2$;
КАКИЕ ОТНОСИТЕЛЬНО НЕБОЛЬШИЕ ИЗМЕНЕНИЯ НАДО СДЕЛАТЬ В ЭТОМ АЛГОРИТМЕ,
ЧТОБЫ ОН ПРАВИЛЬНО РАБОТАЛ ДЛЯ ВСЕХ~$P\ge 1$?

\ex[17] ўТО ДЕЛАЕТ АЛГОРИТМ~R В СЛУЧАЕ ОТСУТСТВИЯ ИСХОДНОЙ ИНФОРМАЦИИ?

\ex[20] рЛГОРИТМ~R ИСПОЛЬЗУЕТ ИСКУССТВЕННЫЙ КЛЮЧ~"$\infty$", КОТОРЫЙ
ДОЛЖЕН БЫТЬ БОЛЬШЕ ЛЮБОГО ВОЗМОЖНОГО КЛЮЧА. яОКАЖИТЕ, ЧТО ЕСЛИ БЫ
КАКОЙ-НИБУДЬ РЕАЛЬНЫЙ КЛЮЧ ОКАЗАЛСЯ РАВНЫМ~$\infty$, ТО АЛГОРИТМ МОГ БЫ
ОШИБИТЬСЯ, И ОБоЯСНИТЕ, КАК ИЗМЕНИТЬ АЛГОРИТМ В СЛУЧАЕ, КОГДА РЕАЛИЗАЦИЯ
"НАСТОЯЩЕЙ" БЕСКОНЕЧНОСТИ НЕУДОБНА.

\rex[23] ъАК ВЫ ИЗМЕНИЛИ БЫ АЛГОРИТМ~R, ЧТОБЫ ОН ВЫВОДИЛ
НЕКОТОРЫЕ ЗАДАННЫЕ ОТРЕЗКИ (ОПРЕДЕЛЯЕМЫЕ~|RC|) В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ, А
ДРУГИЕ В УБЫВАЮЩЕМ?

\ex[26] эАЧАЛЬНАЯ УСТАНОВКА УКАЗАТЕЛЕЙ~|LOSER| НА ШАГЕ~R1 ОБЫЧНО
НЕ СООТВЕТСТВУЕТ НИКАКОМУ ДЕЙСТВИТЕЛЬНОМУ ТУРНИРУ, ТАК КАК ВНЕШНИЙ
УЗЕЛ~$P+j$ МОЖЕТ НЕ ЛЕЖАТЬ В ПОДДЕРЕВЕ С ВЕРШИНОЙ ВО ВНУТРЕННЕМ
УЗЛЕ~$j$. юБоЯСНИТЕ, ПОЧЕМУ АЛГОРИТМ~R ВСЕ РАВНО РАБОТАЕТ.
[\emph{єКАЗАНИЕ.} сУДЕТ ЛИ РАБОТАТЬ АЛГОРИТМ~R, ЕСЛИ
МНОЖЕСТВУ~$\set{|LOSER|(|LOC| (X[0])),~\ldots,
|LOSER|(|LOC| (X[P-1]))}$ ПРИСВАИВАЕТСЯ НА ШАГЕ~R1 \emph{ПРОИЗВОЛЬНАЯ}
ПЕРЕСТАНОВКА МНОЖЕСТВА~$\set{|LOC|(X[0]),~\ldots, |LOC|(X[P-1])}$?]

\ex[ь25] тЕРНО ЛИ, ЧТО ДЛЯ СЛУЧАЙНЫХ ИСХОДНЫХ ДАННЫХ ВЕРОЯТНОСТЬ ТОГО,
ЧТО~$|KEY|(|Q|)<|LASTKEY|$ НА ШАГЕ~R4, ПРИБЛИЖЕННО РАВНА~1/2?

\ex[M46] яРОВЕДИТЕ ДЕТАЛЬНОЕ ИССЛЕДОВАНИЕ ТОГО, СКОЛЬКО РАЗ ВЫПОЛНЯЕТСЯ
КАЖДАЯ ЧАСТЬ АЛГОРИТМА~R; НАПРИМЕР, КАК ЧАСТО ВЫПОЛНЯЕТСЯ ПЕРЕСТАНОВКА
НА ШАГЕ~R6?

%%315
\ex[13] яОЧЕМУ ВТОРОЙ ОТРЕЗОК, ПОЛУЧЕННЫЙ ПРИ ВЫБОРЕ С ЗАМЕЩЕНИЕМ, ОБЫЧНО
ДЛИННЕЕ ПЕРВОГО?

\rex[ть25] шСПОЛЬЗУЙТЕ АНАЛОГИЮ СО СНЕГООЧИСТИТЕЛЕМ, ЧТОБЫ ОЦЕНИТЬ СРЕДНЮЮ
ДЛИНУ ДВУХ \emph{ПОСЛЕДНИХ} ОТРЕЗКОВ, ПОЛУЧЕННЫХ ПРИ ВЫБОРЕ С ЗАМЕЩЕНИЕМ,
 ПРИМЕНЕННОМ К ДЛИННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ИСХОДНЫХ ДАННЫХ.

\ex[20] тЕРНО ЛИ, ЧТО ПОСЛЕДНИЙ ОТРЕЗОК, ПОЛУЧЕННЫЙ ПРИ ВЫБОРЕ С
ЗАМЕЩЕНИЕМ, НИКОГДА НЕ СОДЕРЖИТ БОЛЕЕ $P$~ЗАПИСЕЙ? юБСУДИТЕ ВАШ ОТВЕТ.

\ex[ь26] эАЙДИТЕ "ПРОСТОЕ" НЕОБХОДИМОЕ И ДОСТАТОЧНОЕ УСЛОВИЕ ТОГО, ЧТО
ФАЙЛ~$R_1$~$R_2$~\dots{} $R_N$ БУДЕТ ПОЛНОСТЬЮ УПОРЯДОЧЕН ЗА ОДИН ПРОХОД
$P\hbox{-ПУТЕВОГО}$ ВЫБОРА С ЗАМЕЩЕНИЕМ. ъАКОВА ВЕРОЯТНОСТЬ ЭТОГО СОБЫТИЯ
КАК ФУНКЦИЯ~$P$ И~$N$, ЕСЛИ ИСХОДНЫМИ ДАННЫМИ СЛУЖИТ СЛУЧАЙНАЯ
ПЕРЕСТАНОВКА МНОЖЕСТВА~$\set{1, 2,~\ldots, N}$?

\ex[20] ўТО ПОЛУЧАЕТСЯ В РЕЗУЛЬТАТЕ РАБОТЫ АЛГОРИТМА~R, КОГДА ИСХОДНЫЕ
КЛЮЧИ ПРЕДСТАВЛЯЮТ СОБОЙ НЕВОЗРАСТАЮЩУЮ
ПОСЛЕДОВАТЕЛЬНОСТЬ~$K_1\ge K_2\ge\ldots\ge K_N$?

\rex[22] ўТО ПРОИЗОЙДЕТ, ЕСЛИ ВНОВЬ ПРИМЕНИТЬ АЛГОРИТМ~R К ФАЙЛУ,
ПОЛУЧЕННОМУ В РЕЗУЛЬТАТЕ РАБОТЫ АЛГОРИТМА~R?

\ex[ть22] шСПОЛЬЗУЙТЕ АНАЛОГИЮ СО СНЕГООЧИСТИТЕЛЕМ, ЧТОБЫ ДОКАЗАТЬ, ЧТО
ПЕРВЫЙ ОТРЕЗОК, ПОЛУЧЕННЫЙ ПРИ ВЫБОРЕ С ЗАМЕЩЕНИЕМ, ИМЕЕТ ДЛИНУ ПРИМЕРНО
$(e-1)P$~ЗАПИСЕЙ.

\ex[ть24] ъАКУЮ ПРИМЕРНО ДЛИНУ ИМЕЕТ ПЕРВЫЙ ОТРЕЗОК, ПОЛУЧЕННЫЙ ПРИ
НАТУРАЛЬНОМ ВЫБОРЕ, КОГДА~$P=P'$?

\rex[ть23] юПРЕДЕЛИТЕ ПРИБЛИЗИТЕЛЬНУЮ ДЛИНУ ОТРЕЗКОВ,
ПОЛУЧЕННЫХ ПОСРЕДСТВОМ НАТУРАЛЬНОГО ВЫБОРА ПРИ~$P'<P$.

\ex[ть40] ЎЕЛЬЮ ЭТОГО УПРАЖНЕНИЯ ЯВЛЯЕТСЯ ОПРЕДЕЛЕНИЕ СРЕДНЕЙ ДЛИНЫ
ОТРЕЗКОВ, ПОЛУЧАЕМЫХ ПРИ НАТУРАЛЬНОМ ВЫБОРЕ ПРИ~$P'>P$.
яУСТЬ~$\kappa=k+\theta$---ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО~$\ge 1$,
ГДЕ~$k=\floor{\kappa}$, А~$\theta=\kappa \bmod 1$, И РАССМОТРИМ
ФУНКЦИЮ~$F(\kappa)=F_k(\theta)$, ГДЕ~$F_k(\theta)$---ПОЛИНОМЫ, ОПРЕДЕЛЯЕМЫЕ
ПРОИЗВОДЯЩЕЙ ФУНКЦИЕЙ
$$
\sum_{k\ge0} F_k(\theta)z^k=e^{-\theta z}/(1-z e^{1-z}).
$$
ЄАКИМ ОБРАЗОМ, $F_0(\theta)=1$, $F_1(\theta)=e-\theta$,
$F_2(\theta)=e^2-e-e\theta+{1\over2}\theta^2$ И~Т.~Д.

яРЕДПОЛОЖИМ, ЧТО В МОМЕНТ~$t=0$ СНЕГООЧИСТИТЕЛЬ НАЧИНАЕТ
МОДЕЛИРОВАТЬ ПРОЦЕСС НАТУРАЛЬНОГО ВЫБОРА, И ДОПУСТИМ, ЧТО ЗА $T$~ЕДИНИЦ
ВРЕМЕНИ ПОЗАДИ НЕГО УПАДУТ РОВНО $P$~СНЕЖИНОК. т ЭТОТ МОМЕНТ ВТОРОЙ
СНЕГООЧИСТИТЕЛЬ НАЧИНАЕТ ТОТ ЖЕ ПУТЬ, ЗАНИМАЯ В МОМЕНТ ВРЕМЕНИ~$t+T$ ТО
ЖЕ ПОЛОЖЕНИЕ, ЧТО ЗАНИМАЛ ПЕРВЫЙ СНЕГООЧИСТИТЕЛЬ В МОМЕНТ~$t$. т КОНЦЕ
КОНЦОВ, К МОМЕНТУ~$\kappa T$ ПОЗАДИ ПЕРВОГО СНЕГООЧИСТИТЕЛЯ УПАДУТ РОВНО
$P'$~СНЕЖИНОК; ОН МГНОВЕННО ОЧИЩАЕТ ОСТАТОК ДОРОГИ И ИСЧЕЗАЕТ.

шСПОЛЬЗУЯ ЭТУ МОДЕЛЬ ДЛЯ ИНТЕРПРЕТАЦИИ НАТУРАЛЬНОГО ВЫБОРА, ПОКАЖИТЕ, ЧТО
ДЛИНА ОТРЕЗКА~$e^\theta F(\kappa) P$ ПОЛУЧАЕТСЯ ПРИ
$$
P'/P=k+1+e^\theta\left(\kappa F(\kappa)-\sum_{0\le j \le \kappa}F(\kappa-j)\right).
$$

\ex[ть35] яРЕДЫДУЩЕЕ УПРАЖНЕНИЕ АНАЛИЗИРУЕТ НАТУРАЛЬНЫЙ ВЫБОР В ТОМ СЛУЧАЕ,
 КОГДА ЗАПИСИ ИЗ РЕЗЕРВУАРА ВСЕГДА ЧИТАЮТСЯ В ТОМ ЖЕ ПОРЯДКЕ, В КОТОРОМ
ОНИ ЗАПИСЫВАЛИСЬ: "ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ". юЦЕНИТЕ ДЛИНУ
ОТРЕЗКОВ, КОТОРАЯ ПОЛУЧИЛАСЬ БЫ, ЕСЛИ БЫ СОДЕРЖИМОЕ РЕЗЕРВУАРА, ОСТАВШЕЕСЯ
ОТ ПРЕДЫДУЩЕГО ОТРЕЗКА, ЧИТАЛОСЬ В СОВЕРШЕННО \emph{СЛУЧАЙНОМ} ПОРЯДКЕ,
КАК ЕСЛИ БЫ ЗАПИСИ В РЕЗЕРВУАРЕ ТЩАТЕЛЬНО ПЕРЕМЕШИВАЛИСЬ МЕЖДУ ОТРЕЗКАМИ.

\ex[ть39] ЎЕЛЬ ЭТОГО УПРАЖНЕНИЯ---АНАЛИЗ ПОСЛЕДСТВИЙ, ВЫЗВАННЫХ СЛУЧАЙНЫМ
ИЗМЕНЕНИЕМ НАПРАВЛЕНИЯ УПОРЯДОЧЕНИЯ ОТРЕЗКОВ В ВЫБОРЕ С ЗАМЕЩЕНИЕМ.
%%316
\medskip
\item{a)}~яУСТЬ~$g_P(z_1, z_2,~\ldots, z_k)$---ТА ЖЕ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ,
ЧТО И В ТЕОРЕМЕ~K, НО ДЛЯ КАЖДОГО ИЗ $k$~ОТРЕЗКОВ ОПРЕДЕЛЕНО, ЯВЛЯЕТСЯ ЛИ
ОН ВОЗРАСТАЮЩИМ ИЛИ УБЫВАЮЩИМ. эАПРИМЕР, МЫ МОЖЕМ СЧИТАТЬ, ЧТО ВСЕ
ОТРЕЗКИ С НЕЧЕТНЫМИ НОМЕРАМИ ВОЗРАСТАЮЩИЕ, А С ЧЕТНЫМИ УБЫВАЮЩИЕ яОКАЖИТЕ,
 ЧТО ТЕОРЕМА~K СПРАВЕДЛИВА ДЛЯ КАЖДОЙ ИЗ $2^k$~ПРОИЗВОДЯЩИХ ФУНКЦИЙ
ТАКОГО ВИДА.

\item{b)}~т СИЛУ~(a) МОЖНО СЧИТАТЬ~$P=1$. ьОЖНО ТАКЖЕ ПРЕДПОЛОЖИТЬ,
ЧТО ИСХОДНОЙ ЯВЛЯЕТСЯ РАВНОМЕРНО РАСПРЕДЕЛЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ
НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ВЕЛИЧИН, ЗАКЛЮЧЕННЫХ МЕЖДУ~0 И~1 яУСТЬ
$$
a(x,y)=\cases{
e^{1-x}-e^{y-x}, & ЕСЛИ~$x\le y$;\cr
e^{1-x},               & ЕСЛИ~$x>y$.\cr
}
$$
яУСТЬ~$f(x)\,dx$---ВЕРОЯТНОСТЬ ТОГО, ЧТО ОПРЕДЕЛЕННЫЙ ВОЗРАСТАЮЩИЙ ОТРЕЗОК
НАЧИНАЕТСЯ С~$x$. фОКАЖИТЕ, ЧТО~$\left(\int_0^1a(x,y) f(x)\,dx\right)\,dy$
ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО СЛЕДУЮЩИЙ ОТРЕЗОК НАЧИНАЕТСЯ С~$y$.
[\emph{єКАЗАНИЕ:} РАССМОТРИТЕ ДЛЯ КАЖДОГО~$n\ge0$ ВЕРОЯТНОСТЬ ТОГО,
ЧТО~$x\le X_1\le\ldots\le X_n >y$ ПРИ ДАННЫХ~$x$ И~$y$.]

\item{c)}~ЁАССМОТРИТЕ ОТРЕЗКИ, МЕНЯЮЩИЕ НАПРАВЛЕНИЕ УПОРЯДОЧЕНИЯ С
ВЕРОЯТНОСТЬЮ~$p$, ДРУГИМИ СЛОВАМИ, НАПРАВЛЕНИЕ КАЖДОГО ОТРЕЗКА, КРОМЕ
ПЕРВОГО, СОВПАДАЕТ С НАПРАВЛЕНИЕМ ПРЕДЫДУЩЕГО ОТРЕЗКА С
ВЕРОЯТНОСТЬЮ~$q=1-p$ И ПРОТИВОПОЛОЖНО ЕМУ С ВЕРОЯТНОСТЬЮ~$p$. (ЄАКИМ
ОБРАЗОМ, ЕСЛИ~$p=0$, ТО ВСЕ ОТРЕЗКИ ИМЕЮТ ОДИНАКОВОЕ НАПРАВЛЕНИЕ;
ЕСЛИ~$p=1$, НАПРАВЛЕНИЕ ОТРЕЗКОВ ЧЕРЕДУЕТСЯ, А ПРИ~$p=1/2$ ОТРЕЗКИ
СЛУЧАЙНЫЕ И НЕЗАВИСИМЫЕ) яУСТЬ
$$
f_1(x)=1,\quad
f_{n+1}(y)=p\int_0^1a(x,y)f_n(1-x)\,dx+q\int_0^1a(x,y)f_n(x)\,dx.
$$
яОКАЖИТЕ, ЧТО ВЕРОЯТНОСТЬ ТОГО, ЧТО $n\hbox{-Й}$~ОТРЕЗОК НАЧИНАЕТСЯ С~$x$,
ЕСТЬ~$f_n(x)\,dx$, ЕСЛИ $(n-1)\hbox{-Й}$~ОТРЕЗОК ВОЗРАСТАЮЩИЙ,
И~$f_n(1-x)\,dx$, ЕСЛИ $(n-1)\hbox{-Й}$~ОТРЕЗОК УБЫВАЮЩИЙ.

\item{d)}~эАЙДИТЕ РЕШЕНИЕ~$f$ ДЛЯ УРАВНЕНИЯ "УСТАНОВИВШЕГОСЯ РЕЖИМА"
$$
f(y)=p\int_0^1a(x,y)f(1-x)\,dx+q\int_0^1a(x,y)f(x)\,dx,\quad \int_0^1f(x)\,dx=1.
$$
[\emph{єКАЗАНИЕ:} ПОКАЖИТЕ, ЧТО~$f''(x)$ НЕ ЗАВИСИТ ОТ~$x$.]

\item{e)}~яОКАЖИТЕ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$f''(x)$ ЧАСТИ~(c) ВЕСЬМА
БЫСТРО СХОДИТСЯ К ФУНКЦИИ~$f(x)$ ЧАСТИ~(d).

\item{f)}~яОКАЖИТЕ, ЧТО СРЕДНЯЯ ДЛИНА ВОЗРАСТАЮЩЕГО ОТРЕЗКА,
НАЧИНАЮЩЕГОСЯ С~$x$, РАВНА~$e^{1-x}$.

\item{g)}~эАКОНЕЦ, ОБоЕДИНИТЕ ВСЕ ПРЕДЫДУЩИЕ РЕЗУЛЬТАТЫ И ДОКАЖИТЕ
СЛЕДУЮЩУЮ ТЕОРЕМУ. \dfn{хСЛИ НАПРАВЛЕНИЯ ПОСЛЕДОВАТЕЛЬНЫХ ОТРЕЗКОВ ПРИ
ВЫБОРЕ С ЗАМЕЩЕНИЕМ НЕЗАВИСИМО ИЗМЕНЯЮТСЯ НА ПРОТИВОПОЛОЖНЫЕ С
ВЕРОЯТНОСТЬЮ~$p$, ТО СРЕДНЯЯ ДЛИНА ОТРЕЗКА СТРЕМИТСЯ К~$(6/(3+p))P$.} (¤ТА
ТЕОРЕМА ПРИ~$p=1$  ВПЕРВЫЕ БЫЛА ДОКАЗАНА ъНУТОМ [{\sl CACM,\/} {\bf 6}
(1963), 685--688]; ПРИ~$p=1/2$ ЕЕ ДОКАЗАЛ ¤.~у.~ъОНХЕЙМ В~1978~Г.)

\ex[ть40]ЁАССМОТРИТЕ СЛЕДУЮЩУЮ ПРОЦЕДУРУ.
{\medskip\narrower
%!!! ОПРЕДЕЛИТЬ СТИЛЬ, СВЯЗАННЫЙ С АЛГОРИТМОМ
\item{N1.}~яРОЧИТАТЬ ЗАПИСЬ, ПОМЕСТИВ ЕЕ В РЕЗЕРВУАР ЕМКОСТЬЮ В ОДНО СЛОВО.
 чАТЕМ ПРОЧИТАТЬ СЛЕДУЮЩУЮ ЗАПИСЬ~|R|, И ПУСТЬ~|K| БУДЕТ ЕЕ КЛЮЧОМ.
%
\item{N2.} тЫВЕСТИ СОДЕРЖИМОЕ РЕЗЕРВУАРА, УСТАНОВИТЬ~|LASTKEY| РАВНЫМ ЕГО
КЛЮЧУ И ОПУСТОШИТЬ РЕЗЕРВУАР.
%
\item{N3.}~хСЛИ~$|K|<|LASTKEY|$, ТО ВЫВЕСТИ~|R|,
УСТАНОВИТЬ~$|LASTKEY|\asg |K|$ И ПЕРЕЙТИ К~N5.
%%317
\item{N4.}~хСЛИ РЕЗЕРВУАР НЕ ПУСТ, ВЕРНУТЬСЯ К~N2; В ПРОТИВНОМ СЛУЧАЕ
ПОМЕСТИТЬ~|R|
В РЕЗЕРВУАР.
%
\item{N5.}~яРОЧИТАТЬ НОВУЮ ЗАПИСЬ~|R| И УСТАНОВИТЬ~|K| РАВНЫМ ЕЕ КЛЮЧУ. яЕРЕЙТИ
К~N3.
\endmark\medskip}

¤ТА ПРОЦЕДУРА, В СУЩНОСТИ, ЭКВИВАЛЕНТНА НАТУРАЛЬНОМУ ВЫБОРУ
С~$P=1$ И~$P'=1$ ИЛИ~$P'=2$ (В ЗАВИСИМОСТИ ОТ ТОГО, В КАКОЙ МОМЕНТ МЫ
ОПУСТОШАЕМ РЕЗЕРВУАР---КАК ТОЛЬКО ОН ЗАПОЛНИТСЯ ИЛИ КОГДА НАМ НАДО БУДЕТ
ЗАПИСАТЬ. В ЗАПОЛНЕННЫЙ РЕЗЕРВУАР НОВЫЙ ЭЛЕМЕНТ, ПЕРЕПОЛНЯЮЩИЙ ЕГО), ЗА
ИСКЛЮЧЕНИЕМ ТОГО, ЧТО ЭТА ПРОЦЕДУРА ПОРОЖДАЕТ \emph{УБЫВАЮЩИЕ} ОТРЕЗКИ И
НИКОГДА НЕ ОСТАНАВЛИВАЕТСЯ. ¤ТИ ОТКЛОНЕНИЯ НЕ ПРИНОСЯТ ВРЕДА, ОНИ УДОБНЫ
ДЛЯ НАШЕЙ ЦЕЛИ.

фЕЙСТВУЯ, КАК В УПР.~24, ОБОЗНАЧИМ ЧЕРЕЗ~$f_n(x, y)\,dy\,dx$ ВЕРОЯТНОСТЬ
ТОГО, ЧТО $(x, y)$~СУТЬ ЗНАЧЕНИЯ~$(|LASTKEY|,|K|)$ СООТВЕТСТВЕННО СРАЗУ ЖЕ
ПОСЛЕ $n\hbox{-ГО}$~ВЫПОЛНЕНИЯ ШАГА~N2. фОКАЖИТЕ, ЧТО СУЩЕСТВУЕТ
ФУНКЦИЯ~$g_n(x)$ ОТ ОДНОЙ ПЕРЕМЕННОЙ, ТАКАЯ, ЧТО~$f_n(x, y)=g_n(x)$,
ЕСЛИ~$x<y$, И~$f_n(x, y)=g_n(x)-e^{-y}(g_n(x)-g_n(y))$, ЕСЛИ~$x>y$.
ЇУНКЦИЯ~$g_n(x)$ ОПРЕДЕЛЯЕТСЯ СООТНОШЕНИЯМИ~$g_1(x)=1$,
$$
g_{n+1}(x)=\int_0^x e^ug_n(u)\,du+\int_0^x dv\,(v+1)
\int_v^1du\, ((e^v-1)g_n(u)+g_n(v))+
+x\int_x^1dv\,\int_v^1 du\,((e^v-1)g_n(u)+g_n(v)).
$$
яОКАЖИТЕ ДАЛЕЕ, ЧТО ОЖИДАЕМАЯ ДЛИНА $n\hbox{-ГО}$~ОТРЕЗКА РАВНА
$$
\int_0^1\,dx\int_0^x\,dy(g_n(x)(e^y-1)+g_n(y))\left(2-{1\over2}y^2\right)
+\int_0^1dx\,(1-x)g_n(x)e^x.
$$
[\emph{чАМЕЧАНИЕ.} ЁЕШЕНИЕ ЭТОГО УРАВНЕНИЯ В УСТАНОВИВШЕМСЯ РЕЖИМЕ
ОКАЗЫВАЕТСЯ ОЧЕНЬ СЛОЖНЫМ; ОНО БЫЛО ЧИСЛЕННО НАЙДЕНО фЖ.~ьАК-ъЕННОЙ. юН
ПОКАЗАЛ, ЧТО ДЛИНА ОТРЕЗКА СТРЕМИТСЯ К ПРЕДЕЛЬНОМУ ЗНАЧЕНИЮ~2.61307209.
ЄЕОРЕМА~K НЕ ПРИМЕНИМА К НАТУРАЛЬНОМУ ВЫБОРУ, ТАК ЧТО СЛУЧАЙ~$P=1$ НЕЛЬЗЯ
РАСПРОСТРАНИТЬ НА ДРУГИЕ~$P$.]

\ex[ь33] ЁАССМАТРИВАЯ АЛГОРИТМ УПР.~25 КАК ОПРЕДЕЛЕНИЕ НАТУРАЛЬНОГО ВЫБОРА
ДЛЯ~$P'=1$, НАЙДИТЕ СРЕДНЮЮ ДЛИНУ \emph{ПЕРВОГО} ОТРЕЗКА ДЛЯ~$P'=r$
ПРИ ЛЮБОМ~$r\ge0$ ПО СЛЕДУЮЩЕЙ СХЕМЕ:
\medskip
\item{a)}~яОКАЖИТЕ, ЧТО ПЕРВЫЙ ОТРЕЗОК ИМЕЕТ ДЛИНУ~$n$ С ВЕРОЯТНОСТЬЮ
$$
(n+r)\stir{n+r}{n}\Big/(n+r+1)!.
$$

\item{b)}~юПРЕДЕЛИМ "ЧИСЛА ёТИРЛИНГА ВТОРОГО ПОРЯДКА"~$\Stir{n}{m}$ ПРАВИЛАМИ
$$
\Stir{0}{m}=\delta_{m0},\quad
\Stir{n}{m}=(n+m-1)\left(\Stir{n-1}{m}+\Stir{n-1}{m-1}\right)\rem{ПРИ $n>0$.}
$$
фОКАЖИТЕ, ЧТО
$$
\stir{n+r}{n}=\sum_{0\le k \le r}\perm{n+r}{k+r}\Stir{r}{k}.
$$
%%318
\item{c)}~фОКАЖИТЕ, ЧТО СРЕДНЯЯ ДЛИНА ПЕРВОГО ОТРЕЗКА БУДЕТ, СЛЕДОВАТЕЛЬНО,
 $c_re-r-1$, ГДЕ
$$
c_r=\sum_{0\le k \le r}\left[\left[{r\atop k}\right]\right] (r+k+1)/(r+k)!.
$$

\ex[25] т ТЕКСТЕ РАССМАТРИВАЕТСЯ ТОЛЬКО СЛУЧАЙ СОРТИРОВКИ
ЗАПИСЕЙ ФИКСИРОВАННОГО РАЗМЕРА. ъАК РАЗУМНЫМ ОБРАЗОМ ПРИСПОСОБИТЬ ВЫБОР С
ЗАМЕЩЕНИЕМ К ЗАПИСЯМ \emph{ПЕРЕМЕННОЙ ДЛИНЫ?}

\subsubchap{ьНОГОФАЗНОЕ СЛИЯНИЕ} %5.4.2
ЄЕПЕРЬ, ПОСЛЕ ТОГО КАК МЫ ВЫЯСНИЛИ, КАК МОЖНО ОБРАЗОВАТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ,
 РАССМОТРИМ РАЗЛИЧНЫЕ МЕТОДЫ РАСПРЕДЕЛЕНИЯ  ОТРЕЗКОВ ПО ЛЕНТАМ И СЛИЯНИЯ
ИХ ДО ТЕХ ПОР, ПОКА НЕ ПОЛУЧИТСЯ ЕДИНСТВЕННЫЙ ОТРЕЗОК.

яРЕДПОЛОЖИМ СНАЧАЛА, ЧТО В НАШЕМ РАСПОРЯЖЕНИИ ИМЕЮТСЯ ТРИ ЛЕНТОЧНЫХ
УСТРОЙСТВА: $T1$, $T2$ И~$T3$; МОЖНО ВОСПОЛЬЗОВАТЬСЯ СБАЛАНСИРОВАННЫМ
СЛИЯНИЕМ, ОПИСАННЫМ В НАЧАЛЕ~\S~5.4, ДЛЯ~$P=2$ И~$T=3$. юНО ПРИНИМАЕТ
СЛЕДУЮЩИЙ ВИД:
%% !!! ОПРЕДЕЛИТЬ СТИЛЬ, СВЯЗАННЫЙ С АЛГОРИТМОМ
{\medskip\narrower
\item{B1.}~ЁАСПРЕДЕЛИТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ ПОПЕРЕМЕННО НА ЛЕНТЫ~$T1$ И~$T2$.

\item{B2.}~ёЛИТЬ ОТРЕЗКИ С ЛЕНТ~$T1$ И~$T2$ НА~$T3$; ЗАТЕМ ОСТАНОВИТЬСЯ,
 ЕСЛИ~$T3$ СОДЕРЖИТ ТОЛЬКО ОДИН ОТРЕЗОК.

\item{B3.}~ёКОПИРОВАТЬ ОТРЕЗКИ С~$T3$ ПОПЕРЕМЕННО НА~$T1$ И~$T2$,
ЗАТЕМ ВЕРНУТЬСЯ К ШАГУ~B2.\endmark
\medskip\noindent}
хСЛИ НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ДАЛО 5~ОТРЕЗКОВ, ТО ПЕРВЫЙ ПРОХОД СЛИЯНИЯ
ПРИВЕДЕТ К $\ceil{S/2}$~ОТРЕЗКАМ НА~$T3$, ВТОРОЙ---К~$\ceil{S/4}$ И~Т.~Д.
ЄАКИМ ОБРАЗОМ, ЕСЛИ, СКАЖЕМ, $17\le S \le 32$, ТО ПРОИЗОЙДЕТ 1~ПРОХОД
РАСПРЕДЕЛЕНИЯ, 5~ПРОХОДОВ СЛИЯНИЯ И 4~ПРОХОДА КОПИРОВАНИЯ; В ОБЩЕМ
СЛУЧАЕ ПРИ~$S>1$ ЧИСЛО ПРОХОДОВ ПО ВСЕМ ДАННЫМ БУДЕТ РАВНО~$2
\ceil{\log_2 S}$.

яРОХОДЫ КОПИРОВАНИЯ В ЭТОЙ ПРОЦЕДУРЕ НЕЖЕЛАТЕЛЬНЫ, ТАК КАК ОНИ НЕ
УМЕНЬШАЮТ ЧИСЛА ОТРЕЗКОВ. ьОЖНО ОБОЙТИСЬ ПОЛОВИНОЙ КОПИРОВАНИЙ, ЕСЛИ
ИСПОЛЬЗОВАТЬ \emph{ДВУХФАЗНУЮ} ПРОЦЕДУРУ:
%% !!! ОПРЕДЕЛИТЬ СТИЛЬ, СВЯЗАННЫЙ С АЛГОРИТМОМ
{\medskip\narrower
\item{A1.}~ЁАСПРЕДЕЛИТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ ПОПЕРЕМЕННО НА ЛЕНТЫ~$T1$  И~$T2$.

\item{A2.}~ёЛИТЬ ОТРЕЗКИ С ЛЕНТ~$T1$ И~$T2$ НА~$T3$; ОСТАНОВИТЬСЯ, ЕСЛИ
$T3$~СОДЕРЖИТ ТОЛЬКО ОДИН ОТРЕЗОК.

\item{A3.}~ёКОПИРОВАТЬ \emph{ПОЛОВИНУ} ОТРЕЗКОВ С~$T3$ НА~$T1$.

\item{A4.}~ёЛИТЬ ОТРЕЗКИ С ЛЕНТ~$T1$ И~$T3$ НА~$T2$; ОСТАНОВИТЬСЯ, ЕСЛИ
$T2$~СОДЕРЖИТ ТОЛЬКО ОДИН ОТРЕЗОК.

\item{A5.}~ёКОПИРОВАТЬ \emph{ПОЛОВИНУ} ОТРЕЗКОВ С~$T2$ НА~$T1$. тЕРНУТЬСЯ
К ШАГУ~A2. \endmark
\medskip\noindent}
ўИСЛО ПРОХОДОВ ПО ВСЕМ ДАННЫМ СОКРАТИЛОСЬ
ДО~${3\over2}\ceil{\log_2 S}+{1\over2}$,
%%319
\bye