\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=1
%% 130

\excercises
\ex[�25]\exhead(���������� � ����������.) ��������� �������� ����� 
������ ����� �� ����� � ���������� �� �� ���� �����. ���� �� �������� 
�������� ������� ���������� � ����������---����������, ����� �����������, 
���������� ��� �������� �� ����� ����� � ������ ����� � ��������� �� � 
������ ����� �� ��� ���, ���� ����� �� �������� �������������� � ���������� 
�������.

����� $\pi=a_1\ a_2\ \ldots\ a_n$---������������ ��������� 
$\{1, 2, \ldots, n\}$. "�������� ��������-�������" �������� $\pi$ ��
$$
a_1\ a_2\ \ldots\ a_{i-1}\ \ldots\ a_j\ a_i\ a_{j+1}\ \ldots\ a_n
$$
��� ��
$$
a_1\ \ldots\ a_j\ a_i\ a_{j+1}\ \ldots\ a_{i-1}\ a_{i+1}\ \ldots\ a_n
$$
��� ��������� $i$ � $j$. ����� $\mathop{\rm dis}\nolimits 
(\pi)$---����������� ����� �������� ��������-�������, ����������� ��� 
������������ ������������ $\pi$. ����� �� �������� $\mathop{\rm 
dis}\nolimits (\pi)$ ����� ����� ������� �������������� $\pi$?

\ex[40] ��������� ������������ �� ��������� ������������ ���������� � 
��������� �����, ������� ����� ��������� "����������� �����": ��� $s=t$, 
$t-1$, \dots, $2$ � ��� $j=h_s+1$, $h_s+2$, \dots, $N$ �������� 
������� $R_{j-h_s}\xchg R_j$, ���� $K_{j-h_s}>K_j$. ( �� �������, 
��������� ������� �� ����������������; �� ������������ ��������� 
$K_{j-h_s}:K_{j-2h_s}$. ������ �� ����������� ����� $h_s$-�������������, 
�� ��� ��������������� ��������� ������������ ���������� ����� 
��������.) ᎐������� ����������� ����������� ������� �������.
\subsubchap{�������� ����������}
�� ������� ������ �� ������� �� �������� ���������� ����������, 
���������� � ����� ������ \S~5.2,---� ������� "�������" ��� "������������", 
����������������� ��������������� ����� ������� ����� ���������� ���, � 
������� ���������� ���������������, �� ��� ���, ���� ����� ��� �� ���������.

������� ������� ������� (�������� 5.2.1S) ����� ������������� ��� 
�������� ����������: �� ����� ����� ������ $R_j$ �, �� ��������, ������ 
������� � �������� ����� �� ��� ���, ���� ��� �� ������ ������� �����. 
 �� �������, ������������� ������� ���������� �� ����� ����������, 
��� "�������", "������", "�����" � �. �., �� ������ ����� ����������. � 
���� ������ �� ���������� ������ ���� ������� ����������, ��� ������� 
������ �������� �������� ���������������: 
\emph{�������� ���������� � �������} ("����� ��������"), 
\emph{�������� ���������� �� ��������} (������������ ���������� �������), 
\emph{�������� ���������� � �����������} ("������� ����������" 厀��), 
\emph{����������� �������� ����������}.

\section ����� ��������. �������, �������� ��������� ������ �������� 
���������� ��� ���������� $K_1$ � $K_2$, ����� ������� $R_1$ � $R_2$, ���� 
�� ����� �� �����������, ����� ��������� �� �� ����� � $R_2$ � $R_3$, 
$R_3$ � $R_4$ � �. �. ��� ���������� ���� ������������������ �������� 
������ � �������� ������� ����� ������������ ������, � �� ����� ���� 
������ � ���������� ������ 
%% 131
������ ��������� $R_N$. ��� ������������ ���������� ����� �������� 
��������������� ������ ������� � ������� $R_{N-1}$, $R_{N-2}$ � �. �., ��� 
��� � ����� ������ ��� ������ ����� �����������.

�� ���.~14 �������� �������� ����� ������ ���������� �� ����������� ������ 
503 087 512 \dots 703. 䀉� ����� ������
\picture{���. 14.  ᎐������� ������� �������� � ��������.}
������������ �� �������������, � �����������, ����� ������ $R_N$ ���� 
������, a $R_1$---�����. ����� ������ "������� ��������", ������ ��� 
������� ��������, ������� ���������, "���������" �� ��������������� 
������� � ����������������� "������ ����������" (�. �. ������ ������� 
�������), � ������� �������� ����������� �� ��������������� �������. ����� 
�������� �������� ����� ��� ����� ������������� �������, ������, 
��� "�������� ���������� � �������" ��� ����� "���������������". �������� 
������, ��� ����� ������� ��������� ����� ��� ������, ������� � ����� 
���������, ������� ����������� � ������,
%%132
� ����, ������ ������ ���� ������������� �������,��� ��� �� �� ����� 
��������� ��� ����������� ����������. �� ���.~14 ������ ���� ����������� 
��������� �������� ����������. �������, ��������, ��� ����� ���������� 
��������� ����� ��������, ��� ��� ���� ������� ������ ���� ������������� 
�������. ��� ���������, ��������� ������ �� ���� ����������� 
�������. ⅏���, ������ ��� ����������, �� ������ �������������� ��������.

\alg �.(����� ��������.) ������ $R_1$, \dots, $R_N$ ��������������� �� 
��� �� �����; ����� ���������� ���������� �� ����� ����� �����������: 
$K_1\le \ldots \le K_N$.

\st[��������� ��������� BOUND.] 㑒������� 
$|BOUND|\asg N$. (|BOUND|---������ ������ �������� ��������, � ������� ��� 
�� ��������, ����� �� �� ��� ���� ������������� �������; ����� �������, �� 
��������, ��� � ����� ������� ��� ������ �� ��������.)

\st[戊� �� $j$.] 㑒������� $t\asg0$. ��������� ��� \stp{�} ��� $j=1$, 2, 
\dots, $|BOUND|-1$. ����� ������� � ���� \stp{4}. (���� $|BOUND|=1$, �� 
����� ������� � \stp{4}.)

\st[᐀������/����� $R_j : R_{j+1}$]%
\note{�����, ��� � �����, ��������� ������������ ��� ����������� 
��������� ���������.---{\sl ����. ���.}}).
���� $K_j>K_{j+1}$, �� �������� �������  $R_j\xchg R_{j+1}$ � ���������� 
$t\asg j$.

\st[���� �� ������?] ���� $t=0$, �� ��������� ������ ���������. � 
��������� ������ ���������� $|BOUND|\asg t$ � ������������ � ���� \stp{2}.
\algend
\picture{���. 15. ����-����� ���������� ������� ��������.}

\prog �.(����� ��������.) ��� � � ���������� \MIX-���������� ���� �����, 
�� ������������, ��� ����������� �������� ��������� � ������� 
$|INPUT|+1$, \dots,  $|INPUT|+N$;
��������: $|rI1|\equiv t$; $|rI2|\equiv j$.
%% 133
\code
START &ENT1 & N          & 1   & B1. ��������� ��������� |BOUND|.  $t\asg N$.
1H    &ST1  & BOUND (1:2)& A   & $|BOUND|\asg t$.
      &ENT2 & 1          & A   & �2. 戊�. �� $j$.
      &ENT1 & 0          & A   & $t \asg 0$.
      &JMP  & BOUND      & A   & �����, ����  $j\ge |BOUND|$.
3H    &LDA  & INPUT, 2   & C   & B3. ᐀������/����� $R_j:R_{j+1}$.
      &�� & INPUT+1,2  & C 
      &JLE  & 2F         & C   & ���� $K_j\le K_j+1$, �� ��� ������.
      &LDX  & INPUT+1,2  & B   & $R_{j+1}$
      &STX  & INPUT,2    & B   & $\to R_j$.
      &STA  & INPUT+1,2  & B   & $\hbox{(������� $R_j$)}\to R_{j+1}$
      &ENT1 & 0,2        & B   & $t\asg j$.
9H    &INC2 & 1          & C   & $j\asg j+1$.
BOUND &ENTX & -*,2       & A+C & $|rX|\asg j-|BOUND|$. (���������� ����������)
      &JXN  & 3�         & A+C & $1\le j <|BOUND|$.
4H    &J1P  & 1B         & A   & �4. ���� �� ������?  � �2, ���� $t>0$.
\endcode
\progend

\section ������ ������ ��������. ����� ������� ����������� ����� ������ 
��������� �. ��� ������������ ����� ����������: ������ ���������� $A$, 
������ ������� $B$ � ������ ��������� $C$. ���� �������� ����� �������� � 
����������� � ��������� �������, �� ����� ������������, ��� ��� �������� 
��������� ������������ ��������� $\{1,2, \ldots, n\}$. ������� ������� 
�������� (�.~5.1.1) �������� � �������� ������� �������� �������� 
������� ��������� ��� ���������� ������� ��������.

\proclaim ⅎ���� I. ����� $a_1$ $a_2$ \dots\ $a_n$---������������   
��������� $\{1, 2, \ldots, n\}$,  � $b_1$ $b_2$ \dots 
$b_n$---��������������� ������� ��������. ���� � ���������� ���������� 
��������� ��� ���������� ������� �������� (�������� �) ������������ $a_1$ 
$a_2$ \dots $a_n$ ������������� � $a'_1$ $a'_2$ \dots $a'_n$, �� 
��������������� ������� �������� $b'_1$ $b'_2$ \dots $b'_n$ ���������� �� 
$b_1$ $b_2$ \dots $b_n$ ����������� �� ������� ������� �������� ��������.

\proof ���� ����� $a_i$ ������� ������� �������, �� $a_i$ ���������� 
������� � ���������� �� �������������� ���������, ��� ��� $b_i$ 
���������� �� �������. � ������ �������, ���� ����� $a_i$ ��� ��������, 
�������� $a_i$, �� $a_i$ ������� �� ���������� ������� � ������� ���������,
��� ��� $b_{a_i}$ ��������� 0. 
\proofend

����, ����� ����������� � ���, ��� ���������� � �������� ���������� 
������� ��������, ������ ������������������ ������ �������� ����� 
�����������. ��� ��� ��������, ��������,
%% 134
\bye
