-
. ,
, .
, -
(., ,
Recur4 Recur6).
.
Recur1◦. Fact(N) , -
N! = 12... N
(N > 0 ).
.
Recur2. Fact2(N) , -
N!! = N (N −2)(N −4)...
(N > 0 ;
2, N , 1, N ).
.
Recur3. PowerN(X, N) ,
N - X :
X 0 = 1,
X N = (X N/2)2 N > 0,
X N = X X N−1 N > 0,
X N = 1/ X −N N < 0
(X 6= 0 , N ; N -
).
X N X -
N.
Recur4◦. Fib1(N) ,
N - (N ):
F 1= F 2= 1,
F K= F K−2 + F K−1, K = 3, 4,....
-
,
Fib1, .
Recur5◦. Fib2(N) ,
N - (N ):
F 1= F 2= 1,
F K= F K−2 + F K−1, K = 3, 4,....
, N 20. -
Fib1 (. Recur4)
Fib2. -
Fib2 .
Recur6. Combin1(N, K) , -
C (N, K) N K
:
C (N, 0) = C(N, N) = 1,
C (N, K) = C (N − 1, K) + C (N − 1, K − 1) 0 < K < N.
; N > 0, 0 ≤ K ≤ N. N
K. C (N, K) -
|
|
|
Combin1,
.
112
. . . Programming Taskbook 4.6
Recur7. Combin2(N, K) , -
C (N, K) N K
:
C (N, 0) = C(N, N) = 1,
C (N, K) = C (N − 1, K) + C (N − 1, K − 1) 0 < K < N.
; N > 0, 0 ≤ K ≤ N. ,
N 20.
Combin1 (. Recur6)
-
C (N, K) Combin2.
Combin2 C (N, K) N
K.
Recur8. RootK(X, K, N) ,
K - X
:
Y 0= 1,
Y N+1 = Y N− (Y N− X /(Y N)K−1)/ K,
Y N RootK(X, K, N) X K. -
: X (> 0) , K (> 1) N (> 0) .
RootK X
K - N.
Recur9. NOD(A, B) ,
() A
B, :
(A, B) = (B, A mod B), B 6= 0;
(A, 0) = A.
(A, B), (A, C), (A, D),
A, B, C, D.
Recur10◦. DigitSum(K) ,
K, .
.
Recur11. MaxElem(A, N) , -
A N
(1 ≤ N ≤ 10), .
A, B, C N A, N B, N C
.
Recur12. DigitCount(S) ,
S, .
.
Recur13. Palindrom(S) , -
TRUE, S (
), FALSE .
. -
Palindrom .
, ,
, .
.
Recur14◦. ,
S. :
<>::= <> | <> + <> |
<> − <>
Recur15◦. ,
|
|
|
S. :
<>::= <> | <> + <> |
<> − <>
<>
::= <> | <> * <>
Recur16◦. ,
S. :
<>::= <> | <> + <> |
<> − <>
<>
<>
::= <> | <> * <>
::= <> | (<>)
Recur17◦. ,
S. :
<>::= <> |
(<><><>)
<>
::= + | − | *
Recur18◦. ,
S ( ,
114
. . . Programming Taskbook 4.6
Recur17). , TRUE,
FALSE.
Recur19. ,
S ( , -
Recur17). , 0,
, -
S.
Recur20. ,
S. ( M -
, m -
):
<>::= <> | M(<>, <>) |
m(<>, <>)
Recur21◦. , -
S. (T TRUE, F
FALSE):
<>::= T | F | And(<>, <>) |
Or(<>, <>)
Recur22. ,
S. ( M -
, m -
):
<>::= <> | M(<>) | m(<>)
<>::= <> | <>, <>
Recur23. , -
S. (T TRUE, F
FALSE):
<>::= T | F | And(<>) | Or(<>)
<>::= <> | <>, <>
Recur24. , -
S. (T TRUE, F
FALSE):
<>::= T | F | And(<>) |
Or(<>) | Not(<>)
<>::= <> | <>, <>
Recur25◦. N,
K (< 10) ( 1 K).
0.
, . ,
(
).
Recur26. N, -
K (< 10) ( 1 K).
0.
, -
|
|
|
:
. , Recur25.
Recur27◦. N (N ),
2 : A 1 B −1.
C 0.
, :
0.
, Recur25.
Recur28. N , Recur27.
,
:
.
, Recur25.
Recur29. N,
3 : A 1, B 0 C −1.
D 0. -
, :
-
, 0.
, Recur25.
Recur30. N , Recur29. -
,
: -
, -
0. ,
116
Recur25.
. . . Programming Taskbook 4.6
