2.8. ��������
����������� ����������� ��������� ��� ������� ������� � �������������� ��� ����� ����������� ����� ��������� ��� �������. � [2] ������� ����������� ���� �����, ��� �������� ��������, ���������, ���������� � �������, ������� ����������, ������� ���������������, ������� ���������, ������������� �������, ���������� ������, � ����� �������� � �������������� �������������� ����� ���� ����������� �� ���� ��������. �������� �������� ���������� ��������� �������� ������ ������ ���������� �������� ���������� ( n! ).
function factorial(n: byte): byte;
begin
if n= 0 then factorial:= 1
else factorial:= factorial( n � 1 ) * n
end;
����� ����������� �������� ������ ��������� ����� ����������� ��� ��������� �������� ��������� (��� ����������) �� ��������� ���������� ������������ ��������������� ��������. � ������� � ����������� ��� ����������� ������� � ���, ��� ��� ������� �������� ���������, �������� ���� ������� ����� �������.
��� ������ ������ �������� �������� ������� �������. ��� �������� �������� ���������� ����� ������������� ���������� ������� � �������� �� ���������� ��� ������� ��������� ��� ������ ���������� ��� �������, ��� ������ ������� ���������� ������� �� ����� ���� ��������� �� ��������� ������� ������� ���������� ���� �������. ��������, ��� ���������� ������� factorial( 3 ) � ������������ � ����������� ��������� ���������� ��������� factorial( 2 ), factorial( 1 ) � factorial( 0 ), ������� ����� �������, ��� ����� �������� ����� ������� � ��� ������. � ������� � �������� factorial ������� �������� ��� ����� ���������� �������� ��������� ��������. ��� �������� ������ �����������, ��� �������� � ������ ���� ��� � ���� ������� �������� ������� ������� �������� ������ �� �������� ���������. � �������� ������� �������� �������� � ������� ����������� ������� ���������� �������� ������� ��� ���������� ����������� ������ �������� ���� ������������� ����� n � m. ���� �������� ����� ���� ������� ��������� ��������: ���� m �������� ������ ��������� n, �� ���= m, � ��������� ������ ����� ����� ������� ��� �� m � �� �������, ����������� ��� ������� n �� m. �� Pascal ��� ����� ��������� ��������� �������:
function nod( n, m: integer ): integer;
begin
if m > n then nod( m, n )
else
if n mod m= 0 then nod:= m
else nod:= nod( m, n mod m )
end;
���� ��� �������� �������� ���������� �������, ��� �� �� ����� ��������, ����� ������� �������� ����� ���������� ��� ����������, ��������, �������� nod( 385, 1105 ). ��������, ��� ��� ������������ ���������� ������� �������� ������ ���� ��������.
������ ������������� ��������� �������� �������, ��� �������, � ��������� ������ �������� � ����������� ��������, ��� �������� � ���������� ����������� ����������. ���������� �������� ���������� � ��������� �������:
1) ��� ������ � ������������ ����������� ������;
� �������� ������� ����� �������� ��������� ����������� �������� ����� ����� ��� �����:
<����� ��� �����>::= <�����> | <����� ��� �����> <�����>
<�����>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
�������������� ������ ������� �� ������� ������������ ������� �������� ����� ���� ������ � �������� ������������� � �������� ��������, ��������� �� ���������� ���� � �������� �������. ��������, ��� ������� �123' ������� �������� ��������� �� ���� (� ������� 123 � ����� ��� �����, �� ������� ������� ����� 3; 12 � ����� ��� ����� 1, �� ������� ������� ����� 2; 1- �����).
2) ��� ���������� ��������, �������� ����������� ������� (��������, � �����, ��� factorial � nod, ������������� ����). � ��������� �������, �� ���� ��� ��������� �� ����������� ����������� �� ����� ������� �������� ������ � ���������, ������������� ������ ������ ���������� �������������� � ����������.
���������� ����� ��������, � ������ ������� ��������� � ��������� ��� ������� ���������� � �� ���� � �������, ������� ������� � �������� ��������� � ������ ��������� ��� ������� � ��� ��������� ��� �������, ����� ������� �������������� �� ������.
���������� ��������� �������� ������� � ������������ ����� �������������� ����� ��� ������� ������ ����������� ��������� � �������. ��������, ��� ������ ������� f � ����������� ���������� n= 3 ����� ������������ ��������� ����� ���������� n�= 2, n��= 1, n���= 0:
f( 3 ) � f( 2 ) * 3 � f( 1 ) * 2 * 3 � f( 0 ) * 1 * 2 * 3 � 6
n n� n�� n���
��� ����, ������ ������������ �� �����, ������� �� ����� ���� ���������� (� ������� n���= 0), � �������� ���������� ���������� ����� � �. �. �� ����� �������, ��� �� ��������� ����������� �������� ������� �������� �������� �� ������� ������� ������ �� ������������ �������� (� ������ ������� n= 0).
�������� ������� �������� ������, ��������� � �������������� ��������� ��������.
����� �������
�� ������� ����� �������� (��� ������) ������� ���������� ����:
<�������>::= <�����>|(<�������><����><�������>)
<����>::= +|-|*
<�����>::= 0|1|2|3|4|5|6|7|8|9
������� ��� ������� � ��������� �� ��������.(��������, ((1-2)*4): -4.)
�������
program formula;
var
Source: file of char;
function F: integer;
{F ������ �� ������ �������� ����� ������, ���������� ����������� �������, � ��������� �� �������� ��� �����}
var
c, op: char;
x, y: integer;
begin
read( Source, c );
if ( c >= '0' ) and ( c <= '9' ) then
{����� ���� �������}
F:= ord( c ) - ord( '0' )
else begin
{�������� ������� ���� (x op y)}
x:= F;
read( Source, op );
y:= F;
case op of
'+': F:= x + y;
'-': F:= x - y;
'*': F:= x * y
end;
read( Source, c ) {������� �)�}
end
end; {of F}
begin
assign( Source, 'c:\temp\source.txt' );
reset( Source );
writeln( F );
close( Source )
end.
�������� �������
1. ������ � 8 ������: �� ��������� ����� ���������� 8 ������ ���, ����� ��� "�� ����" ���� �����. �������� ���������, ������� �������� ���� �� ����� �����������.
2. ������ � 8 ������: �� ��������� ����� ���������� 8 ������ ���, ����� ��� "�� ����" ���� �����. �������� ���������, ������� �������� ��� 92 ����� �����������.
3. ���� n ��������� ����������� ����� (n=5). ���������� ��� ������������ ���� �����.
4. ������� n ���������� �������, ���������������� �� 1 �� n (n=10). ��������� ���� ������� ��������� ��������. ����������, ����� �� �� ���� ������� ������� �� 1-�� ������ � n-�. ���������� � ������� �������� � ���� ������������������ ��� ����� i � j (i < j), �����������, ��� i-� � j-� ������ ��������� �������; ������� ����� ���� ������������������ - ���� �����.
5. (���������� ����ɻ). ������� ��� ������� � ,� � � � n ������ ������� �������, ���������������� �� 1 �� n � ������� ����������� �� ��������. ������� ��� ����� ������ �� ������� �. ��������� ��������� ��� ����� � ������� � �� ������� �, �������� ��� ���� ��������� �������: ����� ����� ���������� ������ �� ������, ������� ���� ������ ������� �� �������. �������� ���������, ������� �������� ������������������ �������� (� ���� "��������� ���� � q �� r " , ��� q � r - � , � ��� � ), �������� ��������� ������ ��� n ������, ��� n - �������� ����������� �����.
6. �� ������� ����� ����� �����, �� ������� ������� �����. ��������� ������������� �� ��� ��������� ���������� �����������:
<����� >:: = <������� > | <������� > < ����� >
<������� >::= a | b | (<����� >) | [<����� >] | {<����� >}
7. �� ������� ����� �������� ��� ������ ���������� ��������� ���������� ����:
<���������� ���������>::= true | false | <��������> ( <�������� > )
<�������� >::= not | and | or
<��������>::= <�������> | <�������>, <��������>
<�������>::= <���������� ��������� >
(� �������� and � or ����� ���� ����� ����� ���������, � not - ������ ����.) ������ ��� ��������� � ��������� ��� �������� .(��������, and (or (false ,not (false)),true,not (true)): false)
8. �� ������� ����� ����� �����, �� ������� ������� �����. ���������, �������� �� ���� ����� ���������� ������� ������� ���������� ����:
<�������>::= <�����> | (<�������> <����> <�������>)
<����>::= + | - | *
<�����>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
9. ���� ������������������ ��������� ����� �����, �� ������� ������� 0. ���������� ������� ��� ������������� ����� ���� ������������������, � ����� - ��� ������������� (� ����� �������).
10. ���������� � �������� ������� �������� �� ������� ����� ����� (�� ������� ������� �����).
11. ������� ����������� ������� digits ��� ����������, ������� ������������ ���������� ���� � ������, �������� �� ������� ����� (�� ������� ������� �����).
12. �� ������� ����� ������� �������� ������������������ ������������� ������������ �����, �� ������� ������� ������������� �����. ������� ����������� ������� sum ��� ���������� ��� ���������� ����� ���� ������������� �����.
13. type ������ = packed array [1..100] of char; ������� ����������� ���������� ������� sim( s, i, j ), �����������, �������� �� ������������ ����� ������ s, ������������ i-� � ����������� j -� �� ����������.
14. const n=40; type vector =array [1..n] of real; ������� ������� min ( x ) ��� ����������� ������������ �������� ������� x, ����� ��������������� ����������� ������� min1( k ), ��������� ������� ����� ��������� ��������� ������� x, ������� � k-��.
15. ������� ����������� ������� root (f, a, b, eps), ������� ������� ������� ������� ������� ������� � ��������� eps ������ ��������� f(x)=0 �� ������� (a, b). (C������, ��� eps > 0 ,a < b, f(a)*f(b) < 0 � f(x) -����������� � ���������� ������� �� ������� (a, b).)
16. ���������� ������� ������� C(m, n) ��� 0<=m<=n ,� ��� �������������� ������������ �n �� ��������� ������� :
17. ������� ����������� ������� pow(x, n) �� ������������� x (x <> 0) � ������ n , ������� ��������� �������� xn �������� �������
X^n= 1, ��� n= 0
X^n= 1/ X^|n|, ��� n < 0
X^n= X*X^(n-1) 1, ��� n > 0
18. type name= (George, Alex, Piter, Ann, Paul, John, Fred, Natalie, Robert); family= (son, daugther, father, mother, no); ����������� ��� ���������� ������� father(x) � mother(x), ���������� ������� �������� ����� �������������� ���� � ������ �������� �� ����� x ��� ������������� no, ���� ����������� �������� � ��������������� ��������, ������� ���������� ������� child(a, b) ����������� �������� �� ������� � ������ b �������� (��������, ������, ���������, � �.�.) �������� � ������ a.
19. type name= (George, Alex, Piter, Ann, Paul, John, Fred, Natalie, Robert); family= (son, daugther, father, mother, no); ����������� ��� ���������� ������� father(x) � mother(x), ���������� ������� �������� ����� �������������� ���� � ������ �������� �� ����� x ��� ������������� no, ���� ����������� �������� � ��������������� ��������, ������� ���������� ������� child(a, b) ����������� �������� �� ������� � ������ b �������� (��������, ������, ���������, � �.�.) �������� � ������ a. ������ ������ ������ � �������������, ��� ������� ������� childcount(x), ����������� ����� ����� �������� � ������ x, � ������� ischild(x, k), ����������� ��� k-�� ������� �������� � ������ x (k �� ������ ��������� ����� ����� �������� x).
20. ��������� ������������ �������� ���������� ������� A n-�� ������� (n= 15), ��������� ������� ���������� �� ������ ������
-�������, ���������� ��������� 1-� ������ � k-�� �������. (������������: ���������� ����������� ������� �� ���������� l � s, ������� �� ��������� ������� ��������� ������������ �������, ���������� �� A ��������� ������ l ����� � ���� ��������, ������ ������� ����������� ��������� s.)
21. ��� ��������� �����, �� ������� ������� ����� (� ��� ����� ����� �� ������). ����������, �������� �� ���� ����� ���������� ������� �������:
<�������>::= <����> | ( <�������> <����> <�������> )
<����>::= + | - | *
<����>::= <���> | <�����>
<���>::= <�����> | <���> <�����> | <���> <�����>
<�����>::= <�����> | <�����> <�����>
<�����>::= � | � | � | � | � | � | �
<�����>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
22. ������� ����������� ������� digits1 ��� ����������, ������� ������������ ���������� �������� �+�, �-�, �*� � ������, �������� �� ������� ����� (�� ������� ������� �����).
23. �� ������� ����� ������� �������� ������������������ ������������� ������������ �����, �� ������� ������� ������������� �����. ������� ����������� ������� sum1 ��� ���������� ��� ���������� ������������ ���� ������������� �����.
24. const n=100; type vector =array [1..n] of real; ������� ������� max ( x ) ��� ����������� �������� �������� ������� x, ����� ��������������� ����������� ������� max1( k ), ��������� �������� ����� ��������� ��������� ������� x, ������� � k-��.
25. ������� ����������� ������� digits1 ��� ����������, ������� ������������ ���������� �������� ������� ���� � ������, �������� �� ������� ����� (�� ������� ������� �����) � ��������� �� �������� ��������� ����.
26. ������� ����������� ������� digits2 ��� ����������, ������� ������������ ���������� �������� ��������� ���� � ������, �������� �� ������� ����� (�� ������� ������� �����) � ��������� �� �������� ��������� ����.
27. �� ���������� �����, ���������� �� �������� ��������� ���� ������� ������� ��� ������� �����, ����� ��� ���������.
28. �� ������� ����� ����� �����, �� ������� ������� �����. ���������, �������� �� ���� ����� ���������� ������� ��������� ���������� ����:
<���������>::= <�����> <���� ���������> <�����>
<���� ���������>::= < | = | > | <= | <> | >=
<�����>::= <�����> | <�����>
<�����>::= <������> <�����> | <�����> <�����>
<������>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<�����>::= 0 | <������>
29. �������� ������������ ������ �� n ��������� ��������� (n = 100) ����������� �� ����������� ��������� ������� ������� ����������: ������� �����-������ (��������, �������) ������� ������� � ����������� �������� ������� ���, ����� ����� �� ���������� �������� ��������� ������ ������� ��������, � ������ � ������ ������� (��� ����� ��������� ������� �������� �� ����� �����), ����� ���� ���������� ��������� ���� �� ����� � ����� � ������ ������ �������.
30. �� ��������� ���������� ����� ������� ������� ��� �����, ����� ��� ����� ���������� ��������, �������, ��� ���������� �������.