[̲] [] [] [ ]

 

6.4.

 

, ,- . .

 

6.15. f(n) = n!

 

f(0) = 1;

f(n+1) = f(n)*(n+1).

 

6.16. g(n, m) = n*m.

 

g(0, m) = 0;

g(n+1, m) = g(n, m)+m.

 

6.17. h(n, ) = n.

 

h(0, ) = 1;

h(n+1, ) = h(n, )*.

 

6.15-6.17 .

, f n ,

 

a) f(0) = c;

b) f(n+1) = j(n, f(n)), (6.6)

 

j - .

. , :

 

a) f(0, , ..., ) = h (, ..., );

1 m 1 m

 

b) f(n+1, , ..., ) = j (n, , ..., , f(n, , ..., )), (6.7)

1 m 1 m 1 m

 

j h - .

6.15 (6.6), c = 1, j(n, t) = t*(n+1); 6.16 h () = 0, j(n, , t) = t+; 6.17 h () = 1, j(n, , t) = t*.

, (6.6), -, :

 

f (n: ): t

: t;

n=0 <- c

<- j(n-1, f(n-1)) ;

f <-

.

 

³, f .

- ,

 

6.15'. .

 

Fact (n: ):

: ;

{ Fact(n) = n! }

n=0 <- 1

<- n*Fact(n-1) ;

Fact <-

.

 

, .6.1 , , , Z= Fact(3).

 

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

Z k n1 y1 n2 y2 n3 y3 n4 y4 F1 F2 F3 F4

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

....................... 3

Z <- Fact(k)

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

n1<- k 3

n1=0()

y1<- n1*Fact(n1-1)?

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

n2<- n1-1 2

n2=0()

y2<- n2*Fact(n2-1)?

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

n3<- n2-1 1

n3=0()

y3<- n3*Fact(n3-1)?

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

n4<- n3-1 0

n4=0()

y4<- 1 1

Fact4<- y4 1

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

y3<- 1*Fact(0) 1

Fact3<- y3 1

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

y2<- 2*Fact(1) 2

Fact2<- y2 2

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

y1<- 3*Fact(2) 6

Fact1<- y1 6

--------------------- 6

 

.

 

6.15''. .

 

Fact1 (n: ):

, : ;

{ Fact1(n) = n! }

<- 0; <- 1;

n

<- +1; <- *

;

Fact1 <-

.

 

() .

 

, F(n, , ) ,

 

a) F(0, , ) = ;

b) F(n+1, , ) = F(n, g(), h(, )). (6.8)

 

6.1. (6.8)

 

{ =a & =b }

n

<- h(, );

<- g()

{ = F(n, a, b) }.

. n.

a) n=0 = b = F(0, a, b) (6.8 a).

b) n - b, a' b', :

 

{ =a' & =b' }

n

<- h(, );

<- g()

{ = F(n, a', b') }.

 

c) n+1. - n+1 n- .

 

{ =a & =b }

<- h(, ); (6.9)

<- g()

{ =g(a) & =h(a, b) }.

 

a' = g(a) b' = h(a, b)

 

{ =g(a) & =h(a, b) }

n

<- h(, ); (6.10)

<- g()

{ = F(n, g(a), h(a, b)) }.

 

(6.8 b) F(n, g(a), h(a, b)) = F(n+1, a, b). ' (6.9) (6.10),

 

{ =a & =b }

n+1

<- h(, );

<- g()

{ = F(n+1, a, b) },

 

.

 

6.18. , F(n, , )

 

F(0, , ) = ; F(n+1, , ) = F(n, +1, (+1)*),

 

6.1 , F(n, 0,1) Fact1(n).

 

' - .

6.2. f (6.6),

 

f(n) = F(n, 0, c),

 

F

 

a) F(0, , ) = ;

b) F(n+1, , ) = F(n, +1, j(, )). (6.11)

 

6.1. 6.2 f(n+m) = F (n, m, f(m)).

n.

 

a) n=0. (6.11 a)

 

F(0, m, f(m)) = f(m) = f(0+m).

 

b) , n

 

f(n+m') = F(n, m', f(m')).

 

c) n+1. (6.11 b)

 

F(n+1, m, f(m)) = F(n, m+1, j(m, f(m))).

 

(6.6 b)

 

F(n, m+1, j(m, f(m))) = F(n, m+1, f(m+1)).

 

m'=m+1

 

F(n, m+1, f(m+1)) = f(n+m+1) = f(n+1+m),

 

.

 

6.2 6.1 m=0.

 

6.2 - (6.7).

6.15, , F(n, 0,1) 6.18 n! , , 6.2.

6.1 6.2 - . 6.2 - , 6.1 .

, .

6.19. ,

 

Akk(0, m) = m+1;

Akk(n+1,0) = Akk(n, 1);

Akk(n+1, m+1) = Akk(n, Akk(n+1, m)),

 

-.

 

Akk (n, m: ):

: ;

n=0

<- m+1

m=0

<- Akk(n-1,1)

<- Akk(n, m-1); <- Akk(n-1, )

;

Akk <-

.

 

.

6.20. . . n . , , , . .

, 쳺 n-1 . n C :

1) n-1 C;

2) 1 ;

3) n-1 C .

, n>1.

 

Hanoi ( n, , , C: )

n>0

Hanoi (n-1, , C, );

(,' -> ', );

Hanoi (n-1, C, , )

,

 

: Hanoi (n,1,2,3). n=3 Hanoi(...), (...):

 

------------- (3,1,2,3) --------------

 

--- (2,1,3,2) ---- 1->2 --- (2,3,2,1) ----

[4]

 

(1,1,2,3) 1->3 (1,2,3,1) (1,3,1,2) 3->2 (1,1,2,3)

[2] [6]

 

(0,1,3,2) (0,2,1,3) (0,3,2,1) (0,1,3,2)

1->2 [1] 2->3 [3] 3->1 [5] 1->2 [7]

(0,3,2,1) (0,1,3,2) (0,2,1,3) (0,3,2,1)

 

(,' -> ', ), . 1 2:

 

1 -> 2 1 -> 3 2 -> 3 1 -> 2 3 -> 1 3 -> 2 1 -> 2.

 

, 15 Hanoi(...) 15*4=60 .

 

6.5.

 

.

6.4 . ( 6.20).

 

program Han;

var n: byte;

procedure Hanoi (n, A, B, C: byte);

begin

if n>0 then begin

Hanoi (n-1, A, C, B);

writeln(A:1,' -> ', B:1);

Hanoi (n-1, C, B, A)

end

end;

begin

write('- =? '); readln(n);

Hanoi (n,1,2,3)

end.

 

, , .

.

 

ѳ .

6.4 . ( 6.20).

 

#include <stdio.h>

 

/* Han */

 

hanoi(unsigned n, unsigned a, unsigned b, unsigned c)

{

 

if (n>0)

{

hanoi(n-1, a, c, b);

printf(%u -> %u\n, a, b);

hanoi(n-1, c, b, a);

}

}

 

main()

{

unsigned n;

 

printf(- =? ); scanf(%u, &n);

hanoi(n,1,2,3);

}

 

 

6.4. 6.1 :

 

a) F(0, , , z) = z;

F(n+1, , , z) = F(n, g(), h(, ), t(, , z));

 

b) F(0, , ) = ;

F(n+1, , ) = F(n, g(, ), h(, )).

 

6.5. F (6.11), , F(n+1, , ) = j(n+, F(n, , )).

 

6.6. 6.2, 6.5.

 

[̲] [] [] [ ]