[̲] [] []

 

6. ϲ

6.1.

6.2.

6.3. ϳ

6.4.

 

6. ϲ

 

, , , . , ', , , ' . , . , , . .

, : . . . ϳ () . - - .

. - . , . .

 

6.1.

 

, . ij, , , , . . , - , , , + ( ). , . , : .

. <, > - ' y. , <2,3> <3,2>. f , , D, , R. , f ( ) D ( ) R, f: D -> R.

D={0,1,2,3,4,5}, R={0,1}. , , f 0, 1 - f={<0,0>, <1,1>, <2,0>, <3,1>, <4,0>, <5,1>}. .

D R :

"x ( Î D) <=> $ (<, > Î f);))

"y ( Î R) <=> $ (<, > Î f).))

"x, , z (<, > Î f) & (<, z> Î f) => (=z).))

 

, , .

6.1. .

m k

 

n <- 0;

k

n <- n+m (6.1)

{ n=m*k }.

(6.1) : 1) ', ; 2) , , k, m, ; 3) , , .

 

(M, K: ):

N: ;

N <- 0;

K

N <- N+M

;

<- N

_.

.

.

 

6.2. .

 

(X: ; N: ):

Y: ;

Y <- 1;

N

Y <- Y*

;

<- Y

.

 

6.3. .

 

(M, N: ):

M<>N

M>N M <- M-N

N <- N-M

;

<- M

.

 

, , , (+b, c) , (+b)*c. , , .

 

6.4. 1 n.

 

N, D, K, I, J: ;

(M, N: ):

M<>N

M>N M <- M-N

N <- N-M

;

<- M

;

(N);

I<-1 N

J<-1 I-1

D <- (I, J);

K <- (I div D)*J;

(I, J, D, K)

.

, 糿 : N . , , , .

. f

 

f ( : t ;...; : t ): t

1 1 n n

[ : s ;...; : s ; ] (F)

1 1 m m

(, ..., [, , ..., ])

f 1 n 1 m

,

1, ..., n - t1, ..., tn, ; t - ; 1, ..., m - s1, ..., sm, ; f = f (1, ..., n [, 1, ..., m ]) , , , .

.

(F) . , f f, 1, ..., n, 1, ..., m .

f '

 

f <- , (6.2)

- t.

, , , , , , (F). (F), - , - f.

, .

f 1, ..., n t1,..., tn, ,

f ( , ..., ). (6.3)

1 n

 

.

 

F1) . n+m+1 , x1',..., xn', y1',..., ym' f', . - , , t1, ..., tn, s1, ..., sm t:

 

x':t ; ...; x':t ; y':s ; ...; y':s ; f':t.

1 1 n n 1 1 m m

 

F2) ϳ . , f

 

x' -> , ..., x' -> , y' -> , ..., y' -> , f'-> f,

1 1 n n 1 1 m m

 

f f' .

 

P' = (x', ..., x'[, y',..., y']).

f f 1 n 1 m

 

F3) .

 

x' <- ; ...; x' <- ; P',

1 1 n n f

 

, , , .

f'.

F4) ϳ f' (6.3).

 

6.4.

────────────────────────────────────────────────────────────────────

N I J D K ' M' N' '' M'' N''

────────────────────────────────────────────────────────────────────

.......................... 25 15 9

D <- (I, J)

------------------------

M' <- I; N' <- J 15 9

M'<>N'(), M'>N'()

M' <- M'-N' 6

M'<>N'(), M'>N'()

N' <- N'-M' 3

M'<>N'(), M'>N'()

M' <- M'-N' 3

M'<>N'()

' <- M' 3

------------------------ 3

K <- (I div D)*J 45

J <- J+1 10

D <- (I, J)

------------------------

M''<- I; N''<- J 15 10

M''<>N''(), M''>N''()

M''<- M''-N'' 5

M''<>N''(), M''>N''()

N''<- N''-M'' 5

M''<>N''()

'' <- M'' 5

------------------------ 5

.............................

 

6.5. n- i 1, 2, ..., m, ... . 5.4 6.2

 

, Eps: ;

K, N: ;

(N, K: ; , Eps: ):

Y, Z, X: ;

(X: ; N: ):

Y: ;

Y <- 1;

N

Y <- Y*

;

<- Y

;

Y <- 0.; X <- (+K)/2.;

X-Y>=Eps

Y <- X; Z <- (X, K);

X <- (K*+/Z)/N

;

<- X

;

(N, Eps); K <- N-1;

();

<=0 ;

(,'^1/', N,'=', (N, K, , Eps))

.

 

, ABRN (.).

. , .

 

6.2.

 

.

6.6. .

 

Modn (M, N: ):

R: ;

R <- M;

R>=N

R <- R-N

;

Modn <- R

.

 

6.7. .

 

Divn (M, N: ):

R, Q: ;

R <- M; Q <- 0;

R>=N

R <- R-N; Q <- Q+1

;

Divn <- Q

.

 

³, , . , , R , .

, .

 

6.8. .

 

DivModn ( M, N: ; Q, R: )

R <- M; Q <- 0;

R>=N (6.4)

R <- R-N; Q <- Q+1

;

.

 

M N , Q R - .

, , DivModn(15,6, , ) , 2, - 3. , , , .

, .

 

6.9. .

,

 

z <- ; <- ; <- z

 

y. , - - , - y. : . - , , .

 

( X, Y: )

Z: ;

Z <- X; X <- Y; Y <- Z

.

 

. ,

 

Q ( : t; ...; : t;

1 1 n n

: s; ...; : s;

1 1 m m

z: r; ...; z: r ) (Pr)

1 1 k k

[ u: ; ...; u: ; ]

1 1 l l

(, ..., , , ..., , z, ..., z [, u, ..., u ])

Q 1 n 1 m 1 k 1 l

.

 

Q - ' ; 1: t1, ..., n: tn - , 1: s1, ..., m: sm - , z1: r1, ..., zk: rk - , u1: 1, ..., ul: l - , ; Q = Q (1, ..., n, 1, ..., m, z1, ..., zk [, u1, ..., ul ]) - - , .

(Pr), ' Q.

, , (Pr), .

Q

 

Q (,. .., , v,. .., v, w,. .., w ), (6.5)

1 n 1 m 1 k

 

1, ..., n - t1, ..., tn, ; v1, ..., vm; w1, ..., wk - s1, ..., sm; r1, ..., rk, . 1, ..., n; v1, ..., vm; w1, ..., wk . 1, ..., n ; v1, ..., vm - ; w1, ..., wk , .

 

(Pr) .

 

P1) . n+m+k+l ,

 

x',..., x', y',..., y', z',..., z', u',..., u'

1 n 1 m 1 k 1 l

 

. - , :

 

x':t; ...; x':t;

1 1 n n

y':s; ...; y':s;

1 1 m m

z':r; ...; z':r;

1 1 k k

u':; ...; u':.

1 1 l l

 

P2) ϳ . , Q

 

P' = (x', ..., x', y',..., y', z',..., z'[, u',..., u']).

Q Q 1 n 1 m 1 k 1 l

 

P3) . ,

 

x' <- ; ...; x' <- ;

1 1 n n

 

 

y' <- v; ...; y' <- v;

1 1 m m

 

 

P';

Q

 

 

v <- y'; ...; v <- y';

1 1 m m

 

 

w <- z'; ...; w <- z'.

1 1 k k

 

,

 

X <- 1; Y <- 2; U <- 3; V <- 4;

(X, Y);

(U, V).

 

─────────────────────────────────────────────────────────

X Y U V X1 Y1 Z1 X2 Y2 Z2

─────────────────────────────────────────────────────────

1 2 3 4

(X, Y)

-------------------

X1 <- X; Y1 <- Y 1 2

Z1 <- X1 1

X1 <- Y1 2

Y1 <- Z1 1

X <- X1; Y <- Y1 2 1

-------------------

(U, V)

-------------------

X2 <- U; Y2 <- V 3 4

Z2 <- X2 3

X2 <- Y2 4

Y2 <- Z2 3

U <- X2; V <- Y2 4 3

-------------------

 

(Pr) P1) - P3) , . , , ( 쳿 ) , , , -, .

 

Q ( : t; ...; : t;

1 1 n n

: s; ...; : s ) (Pv)

1 1 m m

[ u: ; ...; u: ; ]

1 1 l l

R (, ..., , , ..., [, u, ..., u ])

Q 1 n 1 m 1 l

.

 

, Q

 

Q (, ..., , v, ..., v ),

1 n 1 m

1, ..., n - t1, ..., tn, ; v1, ..., vm - s1, ..., sm, .

(Pv) .

 

R1) . n+l ,

 

x',..., x', u',..., u',

1 n 1 l

 

. - , :

 

x':t; ...; x':t;

1 1 n n

u':; ...; u':.

1 1 l l

 

R2) ϳ -. , RQ , -

 

R' = R (x', ..., x', v, ..., v [, u',..., u']).

Q Q 1 n 1 m 1 l

 

R3) . ,

 

x' <- ; ...; x' <- ;

1 1 n n

 

RQ'.

 

.

6.10. , .

 

1 ( X, Y: )

X <- X+1; Y <- Y+1

 

1(X, X) X=0 . X=1.

X=2.

6.10 , - , .

 

6.11. .

 

Y: ;

1y ( X: )

X <- X+1; X <- X+Y

;

 

Y <- 1; 1y(Y);

(Y)

.

 

Y, 3.

, X - 4.

, .

 

, , .

 

6.12.

 

1 1 1

= 1 + - + - +... + -

n 2 3 n

 

/Q.

 

_

Ch, Zn, N, J: ;

_ ( Ch1, Zn1: ;

Ch2, Zn2: )

Ch2 <- Ch1*Zn2+Ch2*Zn1;

Zn2 <- Zn1*Zn2

;

_ ( Ch, Zn: )

K: ;

(M, N: ):

M<>N

M>N M <- M-N

N <- N-M

;

<- M

;

K <- (Ch, Zn);

K>1

Ch <- Ch div K; Zn <- Zn div K

;

Ch <- 1; Zn <- 1;

(' n (n>1)=? '); (N)

N>1;

J<-2 N

_ (1, J, Ch, Zn);

_ (Ch, Zn);

(Ch,'/', Zn)

.

 

[̲] [] []