\input style
������� �������� ��� ���.~14:
$$
\vcenter{\halign{
#\hfil\bskip&&\bskip$#$\bskip\cr
 & 3 & 1 & 8 & 3 & 4 & 5 & 0 & 4 & 0 & 3& 2 & 2 & 3 & 2 & 1 & 0\cr
�����~1\cr
 & 2 & 0 & 7 & 2 & 3 & 4 & 0 & 3 & 0 & 2 & 1 & 1 & 2 & 1 & 0 & 0\cr
�����~2\cr
 & 1 & 0 & 6 & 1 & 2 & 3 & 0 & 2 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\cr
�����~3\cr
 & 0 & 0 & 5 & 0 & 1 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
}}
\eqno  (1)
$$
�~�.~�. ����, ����~$b_1\,b_2\,\ldots\,b_n$---������� �������� 
�������� ������������, �� ������ ����������� ���������
$$
\eqalignno{
A&=1+\max(b_1, b_2,\ldots, b_n); & (2) \cr
B&=b_1+b_2+\cdots+b_n; & (3) \cr
C&=c_1+c_2+\cdots+c_A, & (4) \cr
}
$$
���~$c_j$---��������~$|BOUND|-1$ ����� ������� 
$j\hbox{-��}$~���������. 葏������ ������� ��������, �������
$$
c_j=\max\set{ b_i+i \mid b_i\ge j-1}-j
\eqno(5)
$$
(��.~���.~5). 񋅄���������, � �������~(1) $A=9$, $B=41$, 
$C=15+14+13+12+7+5+4+3+2=75$. �� ����� ���������� �� ������ \MIX{} ��� 
���.~14 �����~$1030u$.

������������� ��������~$B$ (��������� ����� �������� � ��������� 
������������) ��� ��� ������ ��������; ����� �������, �������� 
���������������� ��������~$A$ �~$C$.

⅐�������� ����, ���~$A\le k$, ����� ������������~$1/n!$ �� ����� ������ 
��������, �� ���������� ���������~$\ge k$, ������~$k^{n-k}k!$ 
���~$1\le k \le n$. 񋅄���������, ����������� ����, ��� ����������� ����� 
$k$~����������, �����
$$
A_k={1\over n!}(k^{n-k}k!-(k-1)^{n-k+1}(k-1)!).
\eqno(6)
$$
򅏅�� ����� ��������� ������� ��������~$\sum k A_k$, 
��������� ������������ �� ������, ��������
$$
A_{ave}=n+1\sum_{0\le k \le n} -{k^{n-k}k!\over n!}=n+1+P(n),
\eqno(7)
$$
���~$P(n)$---�������, ��������������� ��������� �������, ��� ���� �������� � 
�.~1.2.11, ����������� ��������~$\sqrt{\pi n/2}-{2\over3}+O(1/\sqrt{n})$. 
􎐌���~(7) ���� ������� ��� ��������������
�.~X.~������� [{\sl JACM,\/} {\bf 3} (1956), 150]; �������������� � 
����� ���������� ����������� ������ ㎂���~�.~䅌�� 
[(Stanford University: October, 1956), 64--68]. 񒀍������� 
���������� ��������~$A$ ��.~�~���.~7.

%% 135

񓌌����� ����� ���������~$C$ ����������� ��������� �������, � �� 
���������� ������~$C_{ave}$. ��~$f_j(k)$---����� ����� ������ 
��������~$b_1\,\ldots\,b_n$ ($n$~�����������), ��� ���~$1\le i \le n$ 
����~$b_i<j-1$, ����~$b_i+i-j\le k$; �����
$$
f_j(k)=(j+k)! (j-1)^{n-j-k} \rem{���~$0\le k \le n-j$.}
\eqno (8)
$$
(�.~���.~8.) 񐅄��� ��������~$c_j$ �~(5) �����~$\sum 
k(f_j(k)-f_j(k-1)))/n!$; �������� �� ������, � ����� ��~$j$, �������� �������
$$
C_{ave}=\perm{n+1}{2}-{1\over n!}
\sum_{\scriptstyle 1\le j \le n \atop \scriptstyle 0\le k \le n-j} f_j(k)=
\perm{n+1}{2}-{1\over n!}\sum_{0\le r < s \le n} s! r^{n-s}.
\eqno(9)
$$
������� ��������������� �������� ����� �� ��� ������, �  �� �������� � 
���� � ����� ����� ������.

����� �������� ���� ������ ������� ������ ��������, ������� �������, 
���������� ���� (� ����� ����), ��������� �������:
$$
\eqalignno{
A&=(\min 1, \ave N-\sqrt{\pi N/2}+O(1), \max N); & (10) \cr
B&=(\min 0, \ave {1\over4}(N^2-N), \max{1\over 2}(N^2-N)); & (11) \cr
C&=\left(\min N-1, \ave{1\over 2}(N^2-N\ln N-(\gamma+\ln 2-1)N)+O(\sqrt{N}),
   \max {1\over 2}(N^2-N)\right). & (12) \cr
}
$$
� ���� ������� ������� �����������, ����� �������� ���� ��� ����������, � 
��������---����� ������ ����������� � �������� �������; ����� �������, 
����� ������ ��� ������~\MIX{} 
�����~$8A+7B+8C+1=(\min 8N+1, \ave 5.75N^2+O(N \ln N), \max 7.5N^2+0.5N+1)$.

\section 󑎂�������������� ������ ��������. � ��������� ����� ������ �� 
������ ������ ��������, �, ���� �������, ������������� ��� �����������, 
�����������, ���������� ��������������, ��������� ��� ������� � ���, ��� 
����� �������� ����� �� ��� �� �����. � ��������� � �������� ��������� 
(��������~5.2.1S) ����� �������� ����������� ����� ������� ���������� 
� ������� �������� � 2~���� ������ �������!

쎆�� ���������� ��������� ����� ��������� ������ ��������. 퀏�����, �� 
���.~14 ������ ��������� � 4-� ��������� �������, ��� �� ��� � ������ ��� 
��������� � 5-� ��������� � ������ ��� � 6-� � 7-� ����������. 瀌���� 
�����, ��� �� ���� �������� ������� �� ����� ������������� ����� ��� 
�� ���� ������� �����; ��� ��� ���� ���������� ������� �������
%%136
��������� � ������ �����, �� �� ��������� ��������� ������������ ����� 
���������. ��� ������� �� ����� � "������-����������", ����� ���� 
��������������� ����������� � ����� ������������ (���.~16).  ����� 
������� ������� ����� ��������� ��������� �����������. �.~�.~�������� [A 
Programming Language (Wiley, 1962), 218--219] ������ ���������� � ���� 
��������� ����������: ����~$j$---����� ������, ���~$R_j$ �~$R_{j+1}$ �� 
�������� ������� ��� ���� ���������������� ����������
\picture{���.~16.  "������-����������".}
� ��������������� ������������, �� ������~$R_j$ �~$R_{j+1}$ 
������ �������� ���� ������������� �������, � ��� ����� �� ����������� � 
����������� ����������. 퀏�����, ������������ ������������ 
$4\,3\,2\,1\,8\,6\,9\,7\,5$ ����� �������, �������� $3\,2\,1\,4\,6\,8\,7\,5\,9$: 
������~$R_4$ �~$R_5$ �� ���������� �������.  ��������� ��������� 
������������ ������ ������ $R_4$ ��� ��� ������ (�����) ������~$R_5$; 
�������������, ����� ����� �� ������� ����� � ���, ��� ������~$R_4$ 
�~$R_5$ ����� � �� ����������� �� � ����� �� �����������, ���������.

��� �� ���� �� ���� ������������������ �� �������� � ������� ���������, 
��� �������� ���������� �������� ���������,
%%137
� �� ��� �����, ��� ���� �� �� ������� ��� �������~$N$. 䐓��� ���� 
������� � ���, ����� �������� ����������� �������. � ��� ������� ����� 
��������� �� ����� ������� ������ ���������� �� ���� ��� �����, �� ����� 
���� �� ������� ���� �� �������, ����� ������������ ������---������� 
������ �������! � ���������� �������� �� ����������� ������ �������� 
\emph{������} (��������~5.2.3S), ������� �� ������ �����.

ꎐ��� ������, ����� ��������, �������, �� �������� �������� 
�������������, �� ������� ��� ����� ���� �� ���������������, ���� �� 
������� ����� ��������������� �������� � ���������� ������������� �����, � 
������� �� ��������.

\section ��������� ���������� ᝒ����. 呋� �� ����� �������� �������� 
�������� ����������, ����� ������ �������� ����� �������, �������~$N^2$, 
�� ���������� ��������� ��� ��������� ��������� ���� \emph{����������} 
������~$(K_i, K_j)$; ����� ��������
\picture{���.~17. ��������~M.}
��������� ������� �������, ������� �������� ������� � �������� 
������������, � ������� ����� �������� �����~$(N^2-N)/4$. � 1964~�.\ 
�.~�.~ᝒ��� 
[Proc. AFIPS Spring Joint Computer Conference, {\bf 32} (1968), 307--314]
������ ���� �������� ������ ����������������� ������������������ 
���������, ��������������� ��� ��������� ��������� �������. 僎 ����� 
������ �� ��������. � ����� ����, ������ ��� ����, ����� �������� ��� 
��������������, ��������� ������ ������� ��������������, ��� ��� 
�����������, ������������ ���� ���������. � ������� ��� ��������������, 
���� � ���� ������ � ���� � �.~5.3.4.

񕅌� ���������� ᝒ���� ��������� ���������� ���������� �����, �� 
��������� ����������� ��-������, ��� ��� ��������������� ������� �� 
�����������. �, ����� �������� ����.~1 � ����.~5.2.1-3. 񎐒������ 
ᝒ���� ��������� ��� 8-����������, 4-����������, 2-���������� � 
1-����������, �� ��������� ��
%%138
�������������. � ��� � ��������� ᝒ����, �� ��������, ���������� 
������� ��� ��������������� ����������������������, �� ��� ����� ������� 
"�������� ����������� �� ��������".

\alg M.(����� ���������� �� ��������.) 瀏���$R_1$,~\dots, $R_N$ 
��������������� �� ��� �� �����. �� ���������� ���������� �� ����� 
����� �����������: $K_1\le\ldots\le K_N$.  �����������, ���~$N\ge2$.

\st[퀗������ ���������~$p$.] 󑒀������~$p\asg 2^{t-1}$, 
���~$t=\ceil{\log_2 N}$---���������� ����� �����, �����, ���~$2^t\ge N$. 
(����~\stp{2},~\dots, \stp{5} ����� ����������� �~$p=2^{t-1}$, 
$2^{t-2}$,~\dots, $1$.)

\st[퀗������ ���������~$q$, $r$, $d$.] 󑒀������~$q\asg 2^{t-1}$, $r\asg 0$, 
$d\asg p$.

\st[���� ��~$t$.] 䋟 ����~$t$, �����, ���~$0\le i < N-d$ �~$i\land p=r$,
��������� ���~\stp{4}. 瀒�� ������� � ����~\stp{5}. (焅�� �����~$i\land p$ 
���������� �������� "���������� �" ��� ��������� ��������������� 
�����~$i$ �~$p$; ��� ���� ���������� �����~$0$, ����� ���, ��� ������� � 
��������������� ��������~$i$ �~$p$ ��������� ��������� ����. 
�, $13\land 21=(1101)_2\land (10101)_2=(00101)_2=5$. � ����� 
�������~$d$---�������� �������~$p$ (�.~�.\ ������� �� �������~$d$ ��~$p$ 
�������), �~$p$---������� ������, ��� ���~$i\land p \ne (i+d)\land p$; 
������ �������, ��� �������� ����~\stp{4} ����� ��������� ��� ���� 
������ ���������~$i$ � ����� ������� ��� ���� ������������.)

\st[񐀂�����/�����~$R_{i+1}:R_{i+d+1}$.] 呋�~$K_{i+1}>K_{i+d+1}$,  �� 
�������� �������~$R_{i+1}\xchg R_{i+d+1}$.

\st[���� ��~$q$.] 呋�~$q\ne p$, �� ����������~$d\asg q-p$, $q\asg q/2$,
$r\asg p$ � ������������ � ����~\stp{3}.

\st[���� ��~$p$.] (� ����� ������� ������������~$K_1\,K_2\,\ldots\,K_N$ 
����� $p$-�����������.) 󑒀������~$p\asg \floor{p/2}$. 呋�~$p>0$, 
�� ������������ � ����~\stp{2}.
\algend

� ����.~1 ���� ����� ���������������� ���~$N=16$. 瀌����, ��� �������� 
��������� $N$~���������, �� ��������, ����� ����������� ���������� 
���������~$R_1$, $R_3$, $R_5$,~\dots{} �~$R_2$, $R_4$, $R_6$,~\dots, ����� 
���� ����������� ����~M2,~\dots, M5 �~$p=1$, ����� ����� ��� 
��������������� ������������������.

����� ��������, ��� ���������� ������������������ ���������/�������, 
��������� � ���������~M, ������������� ��������� ����� 
����~$R_1\,R_2\,\ldots\,R_N$, �� ������ �������� ������, ��� � ���������� 
���������� ����� ��~M2 ��~M5 �~$p=1$ ����� ���� ����� 2-������������� 
����~$R_1\,R_2\,\ldots\,R_N$. 䋟 ���� ���� ����� ��������������� ������� 
���������� �������� �� �.~5.2.1 (��.~���.~11); ������ 2-������������� 
������������ ���������~$\set{1, 2,~\ldots, N}$ ������������� �� ������� 
������������� ���� �� �������~$(0,0)$ �~$(\ceil{N/2}, \floor{N/2})$. 
� ���.~18(�) �������
%%139
\picture{򀁋���~1. p.139}
������ ���~$N=16$, ��������������� ������������ 
$1\,3\,2\,4\,10\,5\,11\,6\,13\,7\,14\,8\,15\,9\,16\,12$. 
䅉����� ����~M3 ���~$p=1$, $q=2^{t-1}$, 
$r=0$, $d=1$ ������� � ��������� (�, ��������, ������) �������~$R_1:R_2$, 
$R_3:R_4$ �~�.~�. ���� �������� ������������� ������� �������������� 
����������� ����: "�������" ������������ ���������, ���� ����������, ���,
����� ���� ����� �� �������� ���� ���������. (�.~���.~18(b) � 
�������������� � ���.~10.) 䅉����� ����������� ���������� ����~M3 
�~$p=r=1$ �~$d=2^{t-1}-1$, $2^{t-2}-1$,~\dots, $1$ ������� � 
���������/������ �������~$R_2:R_{2+d}$, $R_4:R_{4+d}$ �~�.~�., � ����� 
������� ������� �������������� �������������: ���� "������������" 
������������ ������, ������������� �� $(d+l)/2$~������ ���� ��������� 
(��.~���.~18(c) �~(d)). � ����� ������ �������� � ����, ������������� �� 
���.~18(e), ������� ������������� ��������� ��������������� 
������������. � ���� "�������������� ��������������" �������������� ����-
%%140
\bye