\input style

\chapter{8 ���������� ������������ ���������� ��������� ��������}
� ���� ����� � ������� ���������� ���������� ���������� ��������� 
�������� ��� ������� ������� �����. � ������� �������� ��� ����� 
��� ����������� ������� ��������� ������ ��� � �� �����: ����� 
����������� ���� �� ��������  ������������. � �������, ��� ������ 
�� ���� ��������� ������� ����������� ��������, � ���� ���, ���, 
��������, �� ����������� ������ �������� ����� �� ���� ��������. 

񋅄���������, ���������� �������� ���������� ����� ������ �� 
������ ��������. �-������, ��� ����� ���������� ��� � �����������, 
�������� � ���������� ������. �-������, ������ ��� � ���, ��� �� 
������� ���� � ��������, ��������� �������� ������� ����� � 
���������� ������� ��, ��� ����� ����������� ��� ������ ���������� 
������������. �-�������, ������ �� ��� ��������� ������ ����� ��� 
���������, ��� ��� ������, ����� ������� ������-����� �� ��������� 
� �� ������������: � ���� ��������� ��������� ����� ���������� 
��������� ����� �����������, ������� �� �������� ����������� 
�������������� ����������. �-���������, �� ����� �������� 
����������, � ������ ���������, ��� ��������� �������� ������� �� 
����� ��� ��������. 퀊����, ������� ���������� �������� ����� 
������� ���� �� ��������������, ��������� � ����������� 
��������������� ����������� �������� ��� ������������� ������ � 
�������� ����������������. ��� ����� ��������� ������, ���� ���� 
�������������� ����������� �������� �� �������� � ��� �� ��������� 
��������, ������ ��� ����� ������ ��� ����� ������� �� ����, 
������� ����� ��� ������ ������ ���� ���������������� �����������.

� ���� �������� � ���� ������������� ���������� ������ � ����e "��� 
������������� $x$, $y$, \dots", ��� �������� ����������� ������� 
����� "��� ����� �������� $x_0$, $y_0$, ... ����������� ���� 
$x=x_0 \and y=y_0 \and \ldots$ ������ �������� �����������, �� 
�������� �������, ��� $x=x_0 \and y=y_0 \and \ldots$". ��� 
����� ����� ������������ � ������������ ����� ������������� ���, 
��� �� ����� ���������� � ����� ��������� ��� � "��������� 
����������"; ��� �� ����� ����������� � ����� ������ ���������� 
������������.

{\sl ��� ������}

䋟 ������������� $x$ � $y$ ���������� ���������� ��������� $R(m)$. 
$$ 
(m=x \or m=y) \and m\ge x \and m\ge y 
$$

䋟 ����� �������� $x$ � $y$ ��������� $m=x$ ����� ����� �������� 
������ � ���������� ������������ $m:=x$; �������������, ���������� 
$(m=x \or m=y)$ �������������� ������ ����������� ���� $m:=�$, ���� 
$m:=y$. � ���� ����-�����:
\pict{8.1}

⑅ ���� � ���, ��� �� ����� ����� ������� ���������� �����, 
������� ��������� ���������� $R(m)$ ����� ���������� ����������. 
䋟 ����� �� "������������ ����������� ����� ������������":
\pict{8.2}
� �� �������� ��������������! � ��� 
$$ 
R(x) = ((x=x \or x=y) \and x\ge x \and x\ge y) = (x\ge y) 
$$ 
 �
$$ 
R(y)= ((y=x \or y=y) \and y \ge x \and y\ge y) = (y \ge x) 
$$ 
�� �������� � ������ �������: 
\prg 
\.{if} x\ge y \to m:=x \wbox y\ge x \to m:=y \.{fi}
\grp
������ $(x\ge y \or y \ge x)=T$, ������ ������� �� ���������� 
(������� �� �������� �������������� �������������: ��� ����� 
�������� $x$ � $y$ ���������� $m$, ��������������� $R(m)$). 
������ $(x\ge y \and y\ge x)\not=F$, ���� ��������� �� 
����������� ���������������. 呋� ������������� $x=y$, �� 
����������� ��������������, ����� �� ���� ������������ ����� 
������� ��� ����������; ����� ��������������������� ���������� 
���������, ��� ��� �� ��������, ��� ����� �� ����� ��������.

{\sl 瀌������.} 呋� �� ����� ��������� ���������� ������� ������� 
"$\max$", �� ����� �� �������� ��������� $m:=\max(�,y)$, ��������� 
$R(\max(x,y))=T$. {\sl(ꎍ�� ���������.)}

������� ��������� �� ���������� ����� �������� �����������; � 
������ �������, �� �����, ��� � �������� ������ ��������� �� 
����������� �� ���� ����� ����������������� ����� ���ero �� 
��������.

{\sl ⒎��� ������}

䋟 �������������� �������� $n$ $(n>0)$ ������ ������� $f(i)$ ��� 
$0\le i< n$. ������� ���������� $R$:
$$
 0 \le k< n \and (\forall i:0 \le i<n:f(k)\ge f(i)) 
$$
������ ���� ��������� ������ �������� ��� �����  ������������� 
�������� $n$, ������ ���� �����������, ��� ����� ���������� 
���������� $R$, �� �������� � ������ �����; ������� �� ���� 
��������� $P$, ������� ����� ����� ������� ��������  � ������ 
��������� � �����, ��� � ����� $(P \and \non BB)\Rightarrow R$.  
񋅄���������, ��������� $P$, �� ���� ���������, ����� ������, ��� 
$R$; ����� ������, �� ����� �������� ��������� ������ ��������� 
���������. 񒀍������� ������ ��������� ��������� --- ��� ������ 
��������� ���������� (��������, � ������������ ���������), � ����� 
��� ���� ������������ ���, ��� �����  ��������  ��������� $n$ ����� 
����������, �������� $j$, � ����� � �������� $�$
$$
 0\le k<j\le n \and (\forall i:0\le i<j:f(k)\ge f(i))
$$

��� ������� $j\le n$ ��������� ��� ����, ����� ������� 
����������� ������� $f$ ���� ��������. 򅏅��, ���� �����
���������, �� ����� ��������
$$
(P \and j =n) \Rightarrow R
$$

����� ����������� ����������� ������������� �����
������� ���������� �, �� ������ ����������� ������ 
��������� ��� ����������� ���������� � � ������ ���������.
������
$$
(k=0\and j=1) \Rightarrow P
$$
�� ������������ ���������� ��������� ��������� ���
����� ��������� (����������� ������ � �������):
\prg
k,j:=0, 1 \{P ����� ��������\};
\.{do} j\not= n \to ����� ��� � j=n ��� �������������� P \.{od}
\{R ����� ��������\}
\grp

񍎂� ��� ���� ������������ ��� ������� � �a������
��������� ��������� ������� $t$  �������� ��������� �������
$t=(n-j)$, ������� � � ����� ���� ������, ��� $�\Leftarrow(t\ge 0)$.
����� ������������� ���������� �������� $t$, � ���������
����������� $j$ �� 1, ����� ���� �� ����� ��������
$$
\displaylines{
\wp("j:=j+1", P)=\cr
0\le k<j+1\le n \and(\forall i:0\le i<j+1:f(k)\ge f(i))=\cr
0\le k<j+1\le n \and(\forall i:0\le i<j : f(k)\ge f(i))\and f(k)\ge f(j)\cr
}
$$

��� ��� ����� ������� �� $P \and j\not=n$  (������ ���
$(j\le n \and j\not=n)\Rightarrow (j+1\le n)$, � ������ ������� �� ������ ��������� 
$j$  ������ �� 1). 񋅄���������,
$$
(P \and j\not=n \and f(k)\ge f(j)) \Rightarrow  \wp ("j:=j+1",P)
$$
� �� ����� ������������ ��������� ������� � ��������
��������������. ������
\prg
k, j:=0,1;
\.{do} j \NE n\to \.{if} f(k)\ge f(j)\to j:=j+1 \.{fi} \.{od}
\grp
������������� ���� ���������� �����, ���� ��� ����������
���������. ��� ���������� ���������� �� �������������,
��������� ����������� ������ ����� �������� � ������ --- �
��� ������������� ��� � �����, ���� $k=0$ �� ������������� $R$.
呋� �������, ��� $f(k) \ge f(i)$, �� ����� ������� ��� ���������
������ ��� ������ ������������ $k:=j$ � ����������
���� ������������:
$$
\displaylines{
\wp("k,j:=j,j+1", P)=\cr
0\le j<j+1\le n \and (\forall i: 0\le i<j+1:f(j)\ge f(i))=\cr
0\le j<j+1\le n \and (\forall i:0\le i<j:f(j)\ge f(i))\cr
}
$$
� �������� ����������� �� ��������, ���
$$
(P\and j\not=n\and f(k)\le f(j))\Rightarrow \wp("k,j:=j,j+1",P)
$$

� ��������� ��������� ����� ��������, �� ����������� ��������� 
������.
\prg
k, j=0,1;
\.{do} j\NE n\to \.{if} f(k)\GE f(j)\to j:=j+1
\wbox f(k)\le f(j) \to k,j:=j,j+1 \.{fi} \.{od}
\grp

񋅄��� ������� ��������� ����������. ���: ���������
�������������� ����������� ������ �� ����������� ���������
���� �����, ��������� ���� � ���� ���������� ���������������������
���� �� ����, ��� � � ������ �������. ��� 
������������������� ����� ���������� � ������. �������
$f$ ����� ��������� �����, ��� �������� �������� $k$ ������������;
� ���� ������ ���� ��������� ����� ���������� �����
���������� ��������!

⒎��� ����������: ��, ��� �� ��������� ���������� ���������,
�� ��������, ��� �� ���������� � �������. �������������
� ������ ������� �������� ��� ��������������, ��� � ����������
�����������; �� ������ ���������� � ������������ � ���
�� ����, ��� ������, � �� �������������. 葕��� ��
�������������, ��� �� ���������� �������� ������� $f$ 
��� ������� ��������� ������������� ������������ ����� �������,
������� ������� ������ �������� �������� �� ��, ��� �
���������, �� ���� �����������, ����� ����������� �����������
$f(k)$ ��� ������ � ���� �� �������� $k$. � ���� ������
������������� ����� �� ������ � ������������ ���������
������� ������, ����� ���������� ����� �������, ��������������
�� ����������. � ��� ���� ���� ������, ������������ ��
��������� ������������� ��������� � ����������
������ �������, �� � ���� ���� �� ������ ������� ����������
�� �������� ���������� � ���������. (��� ��������� ����, �� � ����
����������� ��� �����, ������ ��� ����� �����
������������ ��������� ������������� ������� ��
�������������. ��� ��� ��������� ������������ �����
���������� ������ ����������� ��������������, ������ ����,
������, ��� ������������ ��������� ������ ������������.)
����� ��������� ����������� ����� ������� ���������� ��
������, ����� ��������������� ������� �������� ����� ���
���������� �������������� ����������, ��� �������� �����
������������, ��� ��� ����������� ������������ ���������
���������. � ������ ������� ���� ��������, ��� ��������
������ ��������� ���������� f(k) ��� ������ � ���� �� $k$, 
� ��� ������� �� ����� � �������� �������������� 
����������, ������ $max$, � ���������� ������������� ���������
�� ���� ��������������� �����
$$
max=f(k)
$$

��� ��������� ������ ����� ��������, ����� k  �������
��������� ��������, � ������ ����������� ������������ (���
������ ������ ������������ �������� ���������� $max$) 
����� ��������� k. � �������� � ��������� �po�pa���:
\prg
k,j, max:=0,1,f(0);
\.{do} j \NE n\to \.{if} max \GE f(j) \to j:=j+1
\wbox max\LE f(j) \to k, j, max:=j, j+1, f(j) \.{fi} \.{od}
\grp

⅐�����, ��� ��������� ������� ����� ����������, ���
���� ���������� ������, � ����� ������ ������� �������
�� ���� �� �����������, ������ ��� ������ �� ���������, ���
��� �� ������������� ���������� ������������ $f(j)$ ���
������ � ���� �� $j$. 䋟 ����� ����� ������ ��������������
����������, ������ $h$, � ���������� ��������������
$$
h=f(j)
$$

��� �� �e ����� ������� ��� �� ��� �� ����������
������, ��� ��� ������ ����������� �����: �������� $j=n$ ��
���������, � ��� ���� �������� $f(j)$ �� ����������� ����������.
񋅄���������, ���������� ��������� $h=f(j)$ ������
������ �������������� ����� ������ ��������, ������������,
��� $j\not=n$, �� ���������� ������� ���������� ������� (���
�������, "��� ��� ����� od") �� ����� $h=f(j-1)$, �� ��� ���
�� ������ ����������, � ����� ��� �������� ���, ��� ����.
\prg
k, j, max:= 0, 1, f(0);
\.{do} j\NE n\to h:=f(j);
         \.{if} max\GE h \to j:=j+1
\wbox max \LE h \to k, j, max:=j, j+1, h \.{fi} \.{od}
\grp

������ ���������� �������� �� ������� ������ �������
������, ������� ����� ����������� � ������� � �������.
� �������� � �������������� �������, �� �������� ��
���������� ������� � ������� ���������� ����� ����� ���������,
�������������� �������� �� �� �����, �� �� ������ �������.
���� ���������� �������� ��������� ����������,
����� ���� ���� � ����� ������� �������, � ������ �����������,
���, �������������� �������� �� ����� �� ��������, ��
������� ��������� ������������ ������ �������. ������������
�������������� ����� �������, �� ������ �������, ��� ����
������������� ���������� ��������� ����� ���������,
���� ��� ����� � ���������� ����� ������. ����������, �����������
"������" ����� ������� � ��������, �� ������ ������
��� ��������� � ��������������, ����� �� ������������
�� ������ ������ � ���������; ����� ����, ���� ��������������
��� �������� �������������� ������, �� ������
� ���� �� ���������� ������ ����������� � ������, �����
������ � ���, �������� �� �������������� ��������� � �������������
��������� ���������.

{\sl 瀌������.} � ���� ��� � ����� ������������ ����� �����������
������������, � ������ ����������� "$j<n$" � �������� 
�������������� � ���� ����������� ����������, ������ �
������ ��������� �� ���� ��������, ��� ��� � ������, ��������
�������, �������, ���������������� �������������� "$j\not= n$".
䋟 ����� ������� ��� �������. ����������� "$j\not=n$"
��������� ��� ������� �����, ��� �� ���������� ��������� 
$j=n$, �� �������� ��� ���� �� ������������ ��������� $P$;
��� ����� ���������� ��������� � ���, ��� ���� ���
��� ����������� � ����� �� ��������� � ��������������� "$j<n$".
㎐���� ������, ������, ��� �������������� "$j\not=n$"
������ ���������� ��������� � ����������� �� (�����) �������������
���������, � ������ $j\le n$, � ������� ��� �������
������ ������������, ��� ��� ��� ������������� �������� �
�������� �����������. 呋� � ���������� ���������� $j:=j+1$
�������� $j$ ��� ���������, ��� ������ ������������ ���������
$j>n$, �������������� "$j<n$" �� �������� �������, �����
��� �������������� "$j\not=n$" �� ������� ���� �� ��������
����������� ����������. 򀊎� �������� �������������� ������
�������, ���� ���� �� ��������� �� �������� ���� ������.
�� � ������������������ $x_0$, $x_1$, $x_2$, \dots �������� $x_0$ ��������,
� �������� $x_i$ ��� $i>0$ ������������ ��� $x_i=f(x_{i-1})$, ��� $f$ ---
��������� ���������� �������. ᓄ�� ����������� � �����
������� �� ���. ����� ����������� ������������ ���������
$X=x_i$. ��������, ��� � ��������� ������� ���������
������������ ���������� $n$, �����, ��� ��� ��������� 
�������� $n$ ��� ���������� $x_n$.  ������� ��� $n\ge i$, �� ������
����� ������� �������� ��������� $X=x_n$ ��� ������
\prg
\.{do} i\NE n \TO i, X:=i+1, f(X) \.{od}
\grp

呋� �� ��������� $n\ge i$ �� ����������� ����� �����
(����� ����, ����������� ��������� � ��������� ������� �
����, ��� � �������� ���������� $n$ ����� �� ������ ����������),
����������� ���� ����������� (� �������!) �� ������ � ����������,
� �� ����� ��� �����������
\prg
\.{do} i<n\TO i, X:= i+1, f(X) \.{od}
\grp
�� ��������� ���������� ��������� $X=x_n$. 쎐��� ����
������� ������, ��� ��� ������ ������ �������� �� ������
�������� ���� �������������� ��� ����� ����� �������.
{\sl (ꎍ�� ���������.)}

򐅒�� ������

䋟 ������������� $a(a\ge 0)\hbox{ � }d(d>0)$ ���������
���������� ���������� R:
$$
0\le r< d \and d|(a-r)
$$
(焅�� ������������ ����� "$|$" �������� ����� �����
"�������� ���������".) 荀�� ������, ��� ��������� ���������
���������� ��������������� ������� $r$, ���������� � ����������
������� $a$ �� $d$. ����� ��� ������ ������������� ���� �������,
�� ������ ���������� ������������� ��������������
�������� ������ ���������� �������� � ���������. ������
������� $d|(a-r)$ ����������� ��� $r=a$ � ��� ����, ��� ���
$a\ge 0$, �����, ��� $0\le r$, ������������ ������� � ��������
������������� ��������� $P$:
$$
0 \le r \and d|(a-r)
$$

� �������� ������� $t$, �������� ������� ������ 
���������� ���������� ������ ���������, �� �������� ���� $r$.
������ ��������� $r$ ������ ���� �����, ����� ���������
����������� ������� $d|(a-r)$, $r$ ����� �������� ������ �� �����,
������� $d$, �������� �� ���� $d$. 򀊈� �������, ���, ���
���������, ������������ ���������
$$
\wp("r:=r-d", P) \and \wdec("r:=r-d", r)=0\le r-d \and d|(a-r+d) \and d>0
$$

������ ���� $d>0$ ����� ���� �� �������� � �������������
��������� $P$, ����������� ������� ������ ������ ����;
�� ������� ��������������� �������������� "$r\ge d$"
� ������� ��������� ����� ���������:
\prg
\.{if} a \GE 0 \and d>0 \TO
  r:=a;
  \.{do} r \GE d \TO r:=r-d \.{od}
\.{fi}
\grp

� ���������� ��������� ����� �������� ���������
$P\and\non r\ge d$, �� ���� ������� ���������� $R$, �, ����� �������,
������ ������.

�������� ������, ��� ���, ����� ����, ������������� ��
��������� $q$  ����� ��������, ����� �� ��������� ���������
���� �� ����� �����, ���
$$
a=d *q+r
$$
����� ������, ��������� ����� �� ������ �������, �� � �������.
������ �������� ���� ���� � ������ ������������� ���������.
������
$$
(a=d* q+r)\Rightarrow (a=d*(q+1)+(r-d))
$$
�� �������� � ���������
\prg
\.{if} a \GE 0 \and d>0 \TO
 q, r:=0, a;
 \.{do} r \GE d \to q,  r:=q+1, r-d \.{od}
\.{fi}
\grp
� ���������� ����������� ���� �������� �����, �������,
������������� ����� ����� �������, ���� ������� ������. 쎆��
�� �� ��������� ��� �����? �����, ����� ����� ��������,
���� ��������� $r$ �� ��������, ������� � ������� $d$. ₎��
��� ���� ���� ����� ����������, ������ $dd$, �� ��������
�������, ������� ������ ��������� ����������� �� ����������
���� �a6o�� ���������:
$$
d|dd \and dd \GE d
$$

� ����� �������� ���� ������ ���������, �������
"$r:=r-d$" �����������, �������� ���������, $r$ �� $dd$,
������������ � �� �� ����� ����������� $dd$, ������������� 
������� $d$, �������� ������ ����������, �������� ������ ���
�������� $dd$. 򎃄� �� �������� � ��������� ���������:
\prg
\.{if} a \ge 0 \and d>0\to
  r:=a;
  \.{do} r\ge d \to
    dd:=d;
    \.{do} r\ge dd\to r:=r-dd; dd:=dd+dd \.{od}
  \.{od}
\.{fi}
\grp
ߑ��, ��� ��������� $0\le r \and d|(a-r)$ �����������
������������, � ������� ��������� ��������� ���������� $R$,
���� ��� ���������� ���������, �� ��� �� ���? ꎍ����, ���,
��������� ���������� ����, ������� ����������� ��� $dd>0$,
������������ ������ ��� ��������� ����������, ���������������
������� $r\ge dd$, � ������� ���������� $r:=r-dd$
����������� �� ������� ���� ���� ��� ��� ������� ����������
�������� �����.

� ����� ����������� (���� � ���������� ������������!)
�������� ������ ������������, � ��������� � ���� ����� ��
������� � ���������� ���������� ��������, �� ����� �����������
�������������� � �������� �������, ������� ���������� 
���������������.

�� IF, DO � �� ���������� � ������� ������, �
$P$ --- ��� ���������, ������������� ������������, �.�.
$$
(P \and BB)\Rightarrow \wp (IF, P) \qquad\hbox{��� ���� ���������}
\eqno(1)
$$
� ����� $t$ --- ������������� �������, �����, ��� ��� ������ 
�������� $t_0$ � ��� ���� ���������
$$
(P \and BB \and t\le t_0+1)\to \wp(IF, t\le t_0)
\eqno(2)
$$
���, ��� �� ��,
$$
(P \and BB)\Rightarrow \wdec(IF,t) \qquad\hbox{��� ���� ���������}
\eqno(3)
$$

򎃄� ��� ������ �������� $t_0$ � ��� ���� ���������
$$
(P \and BB \and \wp(DO, T) \and t\le t_0+1) \Rightarrow \wp (DO,t\le t_0)
\eqno(4)
$$
���, ��� �� ��,
$$
(P\and BB\and\wp(DO,T))\Rightarrow \wdec(DO,t)
\eqno(5)
$$
� ��������� ������������: ���� ����������� ������������
��������� $P$ �����������, ��� ������ ��������� ��� ����������
���������� ������� �������� �������������� ���������� $t$,
�� ����������� ���������� ������� �������������� ����������
$t$, ���� ��� ��������� ���������� ����� �� ������� ����
������ ���������� �����-���� ���������� �������.
򅎐��� ��������� ��������, ��� ���� �� �������, ���� �� ��
�������������� ��������� �������, ��, � �������, ��� �� ���.
� �������, ��� �� (1) � (2) �������, ��� ��� ������ ��������
$t_0$ � ��� ���� ���������
$$
(P \and BB and H_k(T)) \and t\le t_0+1)\Rightarrow  H_k (t \le t_0)   
\eqno (6)
$$
��� ���� $k \ge 0$. ��� ����������� ��� $k=0$, ��������� 
$(BB\and H_0(T))=F$, �, ������ �� �������������, ��� (6)
����������� ��� $k=K$, �� ������ ��������, ��� (6) �����������
� ��� $k=K+1$.
$$
\displaylines{
(P \and BB \and H_{K+1}(T) \and t \le t_0+1)\cr
\eqalign{
&\Rightarrow \wp(IF, P) \and \wp(IF, H_K (T)) \and \wp(lF, t\le t_0)\cr
&=\wp(IF, P \and H_K(T) \and t\le t_0)\cr
&\Rightarrow \wp ((IF, (P \and BB \and H_K(T) \and t\le t0+1) \or (t\le t_0  \and \non BB))\cr
&\Rightarrow \wp(IF, H_K(t\le t_0) \or H_0(t\le t_0))\cr
&=\wp(IF, H_K(t\le t_0))\cr
&\Rightarrow \wp(IF, H_K(t\le t_0)) \or H_0(t\le t_0)\cr
&=H_{K+1}(t\le t_0)\cr
}\cr
}
$$

��� ���������� ������� �� (1), ����������� 
$H_{K+1}(T)$ � (2);
��������� � ������� ������ ��������; ���������� � ���������
������ ��������� ��� ������ �������������
$(BB \or\non BB)$ � ������������ ���������� ����� ������;
���������� � ����� ������ ������� �� (6) ��� $k=K$ � �����������
$H_0(t\le t_0)$; ��������� �������. 򀊈� �������, �� ��������
�������������� (6) ��� ���� $k>0$, � ������ ����������
�������� (4) � (5).

{\bf 󏐀������}

臌����� ���� ������ ��������� ����� �������, �����
��� ��������� ����� � �������, � ����� ���������� ��������������
������������ ����� ���������. {\sl(ꎍ�� ����������.)}

�������� ������, ��� ������� ��������� �����,
������ 3, �� ������� ��� ��������� �������� � ������, � ���
��� �������� ����������� ���������� ������, ��� ��� �����
����� ��������������� ���. ᓄ�� ���������� ������������
"$m*3$" (��� "$3*m$") � ������� "$m/3$"; ��������� ���������
����� �������������� ������ ��� �������, ��� �������������
����������� $3|m$. (� ���� �������� � ������ �������, ��
��� ��?)

� ����� �� �������� ���������� ���������� ���������
��������� $R$ ��� ������ ����������� ����������, ��� �������
������������ ��������� $P$ ��������� ����� ������
��������� ����������. 瀌���� ��������� $d$ ���������� $dd$, ���
�������� ����� �������������� ������ � ���� $d * (\hbox{ ������� }3)$,
�� �������� � ������������� ��������� $P$:
$$
0\le r < dd \and dd \ (�-r) \and (\exists i:i\ge 0:dd=d*3^i)
$$

� ��������� ���������� ����� ��������� � �����,
������� ��� ������������, ����������� ������� ���������,
��� ������� $d=dd$.

����� ���������� ���������� $P$, ��� ����������� ��� ����
����������� ����������: ������� �� ��������� ����������
���������
$$
0\le r \and dd \ (a-r) \and (\exists i:i\ge 0:dd=d*3^i)
$$
� ����� ����� ����������� $dd$, ���� ��� �������� �� ������ 
���������� ������� � �����, ��� $r<dd$. ���� ���������
���������:
\prg
\.{if} a\GE 0 \and d>0 \TO
        r, dd := a, d;
\.{do} r\GE dd \TO dd:=dd*3 \.{od};
\.{do} dd \NE d\TO dd:=dd/3;
 \.{do} r\GE dd\TO r:=r-dd \.{od}
\.{od}
\.{fi}
\grp

{\bf 󏐀������}

臌����� ����������� ���� ��������� ����� �������,
����� ��� ��������� ����� � �������, � ����� ����������
�������������� ������������ ����� ���������, ��� 
�������������� ������ �������� ����������, ��� ������ ���, �����
����������� $dd/3$, ����� ����� $3|dd$. {\sl (ꎍ�� ����������.)}

䋟 ����������� ���� ��������� ���������� ��������
���������������� �����������. � ������� ������ ��� �����������
���������� ����������� ������; ����� ��� ���
������ ����������� ���������� �� ����� � ��� �� ������
������� ���� �� ������, ���������� ������� ����� �������
����������� �����������, ��� �������, ����� ��������, ���
������� ���������� �����������. (��� ������� �������� ���
"����� 䅉�����", �������, ������, �� ������ �����������.)
���� ����� ��������� ����: ������ ����������� ����������
��������� ���� "$\and \non BB$" � ���������, ������� ���
��������� ������������, � ��� �������������� ���������
��������� ����������� ����� ������ ��������� ������������.
呋� �� �� ���������� ����, ������ ���� ��� �� � ��������
�������������� �������; � ������� ���������������
���������
\prg
\.{do} r\GE dd\TO r:= r-dd \.{od}
\grp
������ � ��� � �������, ����� ��������������� �������� ����������
��������� $r<dd$, ����������� ��� ���������� ������� �����.

{\sl ��������� ������}

䋟 ������������� $Q1$, $Q2$, $Q3$ � $Q4$ ��������� ����������
���������� $R$, ������ $R$ �������� ��� $R1 \and R2$, ���

R1: ������������������ �������� (q1, q2, q3, q4) ���� ���������
      ������������ �������� (Ql, Q2, Q3, Q4)

R2: q1\LE q2 \LE q3 \LE q4

呋� �� ������� $R1$ � �������� ������������ ������������
��������� $P$, ������� ����� ��������� �������:
\prg
q1, q2, q3, q4:=Q1, Q2, Q3, Q4;
\.{do} q1>q2 \TO q1, q2 := q2, q1
\wbox q2>q3 \TO q2, q3 := q3, q2
\wbox q3>q4 \TO q3, q4:=q4, q3
\.{od}
\grp
�����, ��� ����� ������� ������������ $P$ ����������
�������� � �� ���� �� ���������� ������ �� �������� ���
����������. � ���������� ��������� �� ����� $\non BB$, �
��� ���� ��������� $R2$. � ���, ��� ��������� �������������
������ � ����������, ������ �� ��� ���������� ��-�������
� ����������� �� ����� ���������: ��������� ��� �� ��������,
��� ����� ������������ �������, ������������� ��������
����� ���������������� ��� ��� ������������ $q1+2*q2+3*q3+4*q4$,
� � --- ��� ����� --- ����� "����", ��� �����
������� ��������� � ����� ����������� (������, ���� ����
������). ������ ������������� � ��� ������, ���, �����
�� �������������� �� �� �������, ������� �� ���������
��������� ��������� ���������� �: ��������������,
������������ � ����� �������, �������� ������ ����������
������������� ���������� ���������.

{\sl 瀌������.} 瀌�����, ��� �� ����� �� �������� ����� �
������ ��������, �����, ���
\prg
q1>q3 \to q1, q3 := q3, q1
\grp
������ �� ������ ������������ ��� ������ ������ �� ����,
������������� � ���������. {\sl (ꎍ�� ���������.)}

��� ������� ������ ����, ������ ���� ������� �����
������� ��� ����� ���������������������; ������� ��������
������, ��� � �� ���������� ����������� ������� 
���������� �������� ����������� ��������.

{\sl �� ������}

퀌 ��������� ��������� ��������� �������������
����������� �����; ����� �����: ��� �������������� $n$ $(n>0)$
��������� ������ ���������� ����������
$$
R:              a^2\le n \and (a+1)^2>n
$$

����� �������� ��� ���������, �����, ��������,
��������� ���� �� ���������� ������������, ������ ���������,
� ��������������� ��
$$
P:                 a^2\le n
$$

�����, ��� ��� ��������� ����� ��� $a=0$, �������
����� ���������� �������� �� ������ ��� ����������.
� �����, ��� ���� ������ ���� �� �������� ��������, �� ���
���������� ������� ��������� ��������� $a$, ������� �� �����
�� ���������� � ��������� "$a:=a+1$". 􎐌����� ��
��������
$$
\wp ("a := a + 1 ", P)=((a + 1)^2\le n)
$$

葏������ ��� ������� � �������� (�������������!)
��������������, �� �������� $(P \and \non BB) =R$ � ��������
� ��������� ���������:
\prg
\.{if} n\GE 0 \TO
a:=0  \{� ����� ��������\};
\.{do} (a+1)^2\LE n\to a:=a+1 \{P �������� ��������\} \.{od}
\{R ����� �������� \}
\.{fi} \{R  ����� �������� \}
\grp

 ����������� ��������� �� �������� �� �������������,
��� ��a ����������, � ��� ������������� ���, ���������
������ �� ���������������� ����� ���� ��������� ������������
�������: � �������� $t$ �� ����� ����� ������� $n-a^2$.

��� ��������� �������� ��������, � ���� �� ��� � ��
����� ����������: ��� ������� ��������� $n$ ��� ����� ��������
�������� �����. 䐓��� ������ ��������� R --- ��� ��������
������ ���������� (������, $b$ --- � ����� � ������������
��������� ���������), ������� ������� ����� $R$, ��������,
$$
P:\quad a^2 \le n \and b^2>n \and 0\le a<b
$$
ዀ������ ������ ������ $P$ �������� ��� �������� ���������, ���
$$
(P \and (a+1=b))\Rightarrow R
$$

򀊈� �������, �� �������� � ���������, ��������������
� ����� ����� (����� � ����� ����������� \.{if} n\GE 0 \TO \dots \.{fi}
����������):
\prg
a,b:=0, n+1 \{� ����� ��������\};
\.{do} a+1\NE b \TO ��������� b-a ��� �������������� P \.{od}
\{R ����� ��������\}
\grp

�� $d$ ����� ���������, �� ������� ����������� �������� $b-a$
��� ������ ���������� ���������� �������.
�������� ����� ����������� ���� �� ���� ���������� $b$,
���� �� ���� ���������� $a$, ���� �� ���� � ���� � �������. �
����� ��������, �� ����� ������������ ������������� �����
�����, ����� ���������� ���� $a$, ���� $b$, �� �� $a$ � $b$ ������������:
���� $a$ ������� ���� � $b$ ������� ������ � �� ����� ����
������ ����������� $b$, ����� �� ��������� ���� �����
��������� $a$. ��� ����������� �������� ��� � ��������� �
��������� �����:
\prg
a, b:=0, n+1 \{P ����� ��������\};
\.{do} a+1 \NE b \TO
d:=\dots \{d  ����� ��������������� �������� � P ��-�������� �����������\};
\.{if} \dots\TO a:=a+d  \{P �������� ��������\}
\wbox\dots \TO b:=b-d \{P �������� ��������\}
\.{fi} \{P ����� ��������\}
\.{od} \{R ����� ��������\}
\grp

򅏅��
$$
\wp("a:=a+d", P)=((a+d)^2\le n \and b^2>n)
$$
������ ���������� ������� ����� ������� �� ���������� $P$,
�� ����� ������������ ������ ���� � �������� ������
������� ��������������; ���������� ��������� ������
��������������, � �� �������� ��������� ����� ����� 
���������:
\prg
a, b:= 0, n+1;
\.{do} a+1 \NE b \TO d:=\dots;
      \.{if}(a+d)^2 \LE n\TO a:=a+d
      \wbox (b-d)^2>n\TO b:= b-d
      \.{fi} \{� �������� ��������\}
\.{od} \{R ����� ��������\}
\grp

퀌 �������� ��� ��������������� ������� ������� $d$.
������ �� ����� $b-a$ (�� ����� ����, $b-�-1$) � ��������
����� ������� $t$, ����������� �������� ������ ���� �����,
����� d ������������� ������� $d>0$. ꐎ�� ����, 
����������� ����������� ������ �� ������ ��������� � ������, �. �.
�� ������� ���� ���� �� ��������������� ������ ����
��������. ��� ������, ��� �� ��������� ������, $(a+d)^2>n$, ������
��������� ������, $(b-d)^2>n$; ��� �������������, ����
$$
a+d\le b-d
$$
���
$$
2*d\le b-a
$$

퀐��� � ������ �������� �� ���������� ����� � �������
������� ��� $d$. � ����� �� ����� $d=1$, �� ��� ������ $d$, ���
������� �������� ���������, ������� �� ����������
\prg
a,b:=0,n+1;
\.{do} a+1 \NE b \TO d:=(b-a) \div 2;
             \.{if} (a+d)^2\LE n\TO a:=a+d
                \wbox (b-d)^2>n\TO b:=b-d
             \.{fi}          
\.{od}
\grp
��� $n\div 2$ ���� $n/2$, ���� $2|n$ � $(n-1)/2$, ���� $2|(n-1)$.

葏���������� �������� $\div$ ���������  ��� ����������
� ���, ��� ����������, ���� �� ������� ���� ����������� �� $b-a$,
�������, ��� $b-a$ ����� ��� ������ ���������� $d$. ₎�� 
$c=(b-a)$ � �������� $b$, �� �������� ������������ ���������
$$
P:\qquad a^2\le n \and (a+c)^2 > n \and (\exists i: i\ge 0 : c=2^i)
$$
� ��������� (� ������� $c$ ������ ���� $d$)
\prg
a,c:=0, 1; \.{do} c^2\LE n\TO c:=2*c \.{od};
\.{do} c \NE 1 \TO c := c/2;
           \.{if} (a + c)^2 \LE n \TO a:=a+c
               \wbox (a-c)^2 > n \TO \var{����������}
           \.{fi}
\.{od}
\grp

{\sl 瀌������.} ��� ��������� ����� ������ �� ���������
��������� ��� �������� �������, ��� ���������� ������� �
�������������, ��� �� ����� ����� �������� � ������ �� 3.
� ����������� ���� ��������� ����� ���� �� �������� �����������
������ ��
\prg
\.{d�} (a+c)^2 \LE n \TO a:=a+c \.{od}
\grp
呋� �������, �������� ������ ������������� �������,
$0\le r < d$, �������� ��� $r<d \and (r+d)\ge d$, �������� ������
��� ����� ����������. {\sl (ꎍ�� ���������.)}

����, ��� ��� ����� ������������ "��������" ���� ���������
�������, � �� ����� ��� �� ����� ���������� ���������
������� �������������� ���������. � �������� ���������,
������ �� �������������, ��� �������� ���������� ����� �
������� ������ � ������ ��������� ��������; �� �����������,
��� ��� �� ��� � ��� ������������ �������� ����
���������, ��������� � ����� ������������,--- ��� ���������
� ������� �� (�����) ������� 2. 򎃄� ���� ���������
��������� ����������� �� ����� �� �������, �. �. ���
��������, ���� �� ������������, ��� �������� ����������,
� �������� ��������������� ��������� ������, �������������
�� ���������� ���������� $a$ � $c$, ��� ��� ���� �� ��� 
"�����������" �����������. 䐓���� �������, �� �����
������������� $a$ � $c$ ��� ����������� ����������, ���
�������� �������������� (� ������������ � �����������, 
����������������� ����� ������� �������, ��� ������ 
���������������)
���������� ������ ����������, � ��������
� ���������������� ��������� ������ ��� ����������
���������. � ����� ��������� ������ �������� ��
��������������� � $a$ � $c$, � � $�$, $q$, $r$, ������, ���
$$
\eqalign{
p &= a * c \cr
q &=c^2\cr
r &=n-a^2\cr
}
$$

� �����, ��� ��� --- �������������� ���������, � ������
���������� � ����� $(a, c)$-������������ �������������
���������� � ����� $(p, q, r)$-������������. ����� �� ������
�����, ��� ��� �������� $p$, $q$ � $r$  �� ����������: � ��������
$p$, $q$  � $r$ �� �������� ������������ �, �������������,
������������� �����������, ����������� ��������� �������
������, ��  ������ �������� ����� ����������, ��
���� ���������� �� ������������� ��������� � �������!
(񎂅������ ����, ��� �������������� ������ ��� ����,
����� ��������� ��������������, ����������� ����� �
$(a,c)$-������������ � ����� � $(�, q, r)$-������������.) 򅏅�� ��
����� ���������� ��������� ��� ������ ��������� � 
����������� � $(a, c)$-������������ � ��������������� ������
��������� � ����������� � $(p, q, r)$ -������������. 呋� �� ���
������� ������� ��� � �������� ���������� ��������, ����
������ ���� �� ������� ������. ��������� ��������������
� � ����� ���� �������� ����� �����������, � �����������
��� �������� ��������� ��������� (���������� $h$ ����
������� ��� ����� ��������� �����������):
\prg
p,q,r:=0,1,n; \.{do} q\LE n \TO q:=q*4 \.{od};
\.{do} q \NE 1\TO q:=q/4; h:=p+q; p:=p/2 \{h=2*p+q\}
     \.{if} r \GE h \TO p,r:=p+q,r-h
       \wbox r<h \TO \var{����������}
     \.{fi}
\.{od} \{ p ����� ��������, ��������� ��� a \}
\grp

���� ����� ������ ��� ������� ��������� ������� ���
�������� (������, ��������� �������������). ꎃ��
������� �� ���� ����� ����� ���� ����� ��������� �������,
� ������� ������� ����� �������� � ���� ������. 퀇�����
��� ���������� ������ ������ ���������, ������� ����� ����
��������� ������ ����� ������ ����������� � �����������������,
� ��� ����� ���� ������� ������, ����� �� �� 
������� � ��� "�����������" �������. � ������� ������� ��������
� �������� ������, ������ � ��������� ���������, ������,
��������� ������ $h$ � ��������� ��������� � ���� ������
��� ������ ��������� � ������, ����� �������� �����. �
������ ���������, ���, ������� ��������� � $a$ � $b$ � �������
���� ����� ������������ ��� ���������� ������� � ������
�������� �������, � ������ ���� ��������� ������ ������ ---
� ��� ���� ����� � ������� ����� ���������� �����, ��� ������������
�����. ⒎��� ������� ��� �� ��������� � �����
�������������� �������� --- ��� ����������� ����� �������
�����������: �� ��������� � ��������� ��������� ������
������������ ����� ��� ������ ������ ��� ����������
"���������� �������������".

{\sl ������ ������}

䋟 ������������� $X\ (X>1)$ � $Y\ (Y\ge 0)$ ��������� ������
���������� ���������� ���������
$$
R: \quad z=X^Y
$$
��� ��������� �������������, ��� �������� ���������� � �������
�� ������ � ����� ��������� ��������. ��� ������ ����� ����
������ ��� ������ "����������� ����������", ������ $h$;
��� ������� ������ �� ����� ������������ ������, ��� ��������
������������ �������� ���������
$$
P:\qquad h * z=X^Y
$$
� ���� (� ������ ������� "�����������") ��������� ����� 
�� ��������� ���:
\prg
h,z:=�^Y,1 \{P ����� ��������\};
\.{do} h \NE 1\TO ������� $h$ ��� �������������� $P$ \.{od}
\{ R ����� �������� \}
\grp

������ ���������� �����������, ��������� $(P \and h=1)\Rightarrow R$.
�������� ���� ��������� ������ � ����������, ����
����� ��������� ����� ���������� �������� "��������" $h$
������ ������ 1. �����, �������, � ���, ��� �� �� �����
����������� �������� $h$ ��������� ���������� ����������, 
� ������� ��������������� ��������� ������; ���� �� ��
����� ��� �������, �� ����� �� ����� ��������� $z$ ��������
$X^Y$, �� ��������� ���� ��������� $h$. 􎊓� � ���, ���
��� ������������� �������� �������� $h$ �� ����� ������ ��� ---
�� ���� ������ ���������� --- ����������, ������ $x$ � $y$,
� ���� ������ ������������ ���������� � �������� ����������
�� ���� �������������
$$
h=x^y
$$

򎃄� ������� "$h\not=1$" ��������� � ������� "$y\not=0$", � ����
��������� ������ ������� � ���, ����� ��������� ����������
�������� "��������". ������ ��� ���� ��������
������������ $h*z$ ������ ���������� ������������, �� ������
������ $h$ �� �� �� ��������, �� ������� ���������� $z$.
葕��� �� ������������� $h$, �������� ������������ ���������� ��
��� �������� ����� ������� ������� �������� $x$. ᅇ 
���������� ����������� �� �������� � ������ ���� �����
����������� ���������:
\prg
x,y,z:=X,Y,1 \{P ����� ��������\};
\.{do} y\NE 0 \TO y,z:=y-1, z*x \{P �������� ��������\} \.{od}
\{R ����� ��������\}
\grp

㋟�� �� ��� ���������, �� ��������, ��� ����� 
���������� ����� ����� ��������������� �������� $Y$, � �����
������ ���� ������, ������ �� �������� ���������. ߑ��, ���
������� ���������� ������� �������� �������� $y$ � ����; ��
������� \emph{��������} $h$, �� ����� ���������, ������ �� ��������
\emph{�������������} ����� �������� � ������� ��������� ��������
$y$. ������� ��������������� ��� ������, ��� ����������
������������� �������� $h$, �������� ��� $x^y$, ����� �� ��������
�����������. 呋� $y$ �����, �� ����� ��������� $y$ �� 2 �
�������� $x$ � �������, ��� ���� �������� $h$ ������ �� ���������.
 텏������������ ����� ��������� �������� �� ���������
��������������, ���������� � �������� ����������������
�������������� $h$ � �������� ��������� ���������:
\prg
x,y,z:=X,Y,1;
\.{do} y\NE0 \TO \.{do} 2 | y\TO x, �:= x*x, y/2 \.{od};
              y,z:=y-1,z*x
\.{od} \{R ����� �������� \}
\grp

񓙅������ ������ ���� ��������, ������� �����
���������� ������ ������� � ��� �� ������ ��������, ���
�������� --- ����; ����� ������, ������� �������������� �����������
���, ��� ���������� ���� ������ � ����������.

� ������� ���� ������ �� ������ ��������. 셍� 
�������� ��������, ��� ���� ������ �������� � ��������� ���-��,
��� �� ����������� ������ ��������� ��� ������ ��������,
����� ��� �������� ��������, ��� ����� ��������, �������
������ ���� ��������������� $Y$, ������ ���������������
������ $\log (Y)$. ��� �������� ���� ������ ���������� ����,
��� � �������� ���� ������ � �������� ��������� �����������
����������. ������ ���������� � �������, ������� � ����,
���� ���������:
\prg
x,y,z:=�,Y,1;
\.{do} y<>0 \TO \.{if} \non 2| y\TO y,z:=y-1,z*x
                       \wbox 2|y \TO\var{����������} \.{fi};
                   x,y:=x*x,y/2
\.{od}
\grp
��� ��������� ��������� ����� ������ ��������, ������ ��
��� ������ � ��� ���������� ���� �� �����. ������ ���������
���������� $x$ � �������, ����� $y$ ���� ������ ����, ���
�������, �� ��� ��������� ����� ��������� ��� �� ������,
������������� ������������� ����� ��, ��� �� ������� ��
"��������������� ��������". ����� �� �������� ����
���������, � ������� � ����������, ��� ���� ����� ����.

{\sl 񅄜��� ������ }

䋟 �������������� �������� $n$ $(n\ge 0)$ ������ �������
$f(i)$ ��� $0\le i<n$. ������ ������� ���������� "\var{��������}"
����� ��������, ����� � �������� ���������� ����� ������������
$$
R:\qquad \var{��������} =  (\forall i: 0 \le i < n : f (i) = 6)
$$
(���� ������ ������������ ��������� �������� �� ������
�������� ������ �����. 瀌����, ������, ��� � ���� �������
����������� ��������� $n$ ����. � ����� ������ ��������
��������� �������� ��� �������� "$\forall$" ���� � ������ ����
������, ���  $\var{��������}=\var{������}$.) � �������� �� ������ ��������
������ ������������ ���������
$$
P:\qquad \var{��������}=(\forall i: 0\le i<j :f(i)= 6)) \and 0\le j\le n
$$
��������� ��� ��������� ����� ������� �������� ��� $j=0$
� � ���� �� $(P \and j=n) \Rightarrow R$ . 儈���������, ��� �� ������
�������, ��� ������, ��� ����������� $j$ ��� �������������� $�$.
���� �����
$$
\wp("j:=j+1", P)=
(\var{��������}= (\forall i: 0\le i<j+1: f(i)=6)) \and 0\le j+1\le n
$$
񏐀���������� ���������� ����� ������� �� ��������������
$P \and j\not=n$; � � ���� ��� ������� ��������, ��� ��� �� ���
������, ��� ������� $j\not=n$, ������ � �������� ��������������,
�������� ��������� ������, ����� ������ ������ � ��������

\bye
