\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