����� ����������

������

 

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.  �� ��������� ���������� ����� ������� ������� ��� �����, ����� ��� ����� ���������� ��������, �������, ��� ���������� �������.

����� ����������

������