ege11c 2016 04 10 17 02 18 748


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.

К. Поляков, 20
12
-
201
5


1

http://kpolyakov.
spb
.ru

11

(
бТзЭвый
урЭвень,
время


5

мЧн)

Тема
:
рекурсивные алгоритмы
.

Что нужно знать
:



рекурсия


это приём, позволяющий свести исходную задачу к одной или нескольким более
простым задачам того же типа



чтобы определить рекурсию, нужно задать

o

условие остановки
рекурсии (базовый случай или несколько базовы
х

случаев)

o

рекуррентную

формулу



любую рекурсивную процедуру можно запрограммировать с помощью цикла



рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более
понятным, хотя часто менее

эффективным



существуют языки программирования, в которых рекурсия используется как один из основных
приемов обработки
данных (
Lisp
,
Haskell
)

П
рЧмер

зТдТнЧя
:

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 5)
{



F(n + 1);



F(n

+ 3)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове
F(
1
)
.

Решение (вариант 1, построение дерева вызовов):

1)

поскольку в начале каждого вызова на экран выводится значение единственного параметра
функции, достаточно определить порядок рекурсив
ных вызовов и сложить значения
параметров

2)

поскольку при

выполняется два рекурсивных вызова, решать такую задачу

на
бумажке


удобно в виде двоичного дерева

(
в узлах записаны значения параметров при
выз
о
ве функции
)
:


3)

складывая все эти числа, получаем 49

4)

ответ:
49
.

Решение (вариант 2, подстановка):

1

2

4

5

3

4

5

7

6

5

7


К. Поляков, 20
12
-
201
5


2

http://kpolyakov.
spb
.ru

1)

м
ожно обойтись и без дерева, учитывая, что при каждом вызове с
n

< 5 происходит два
рекурсивных вызова
;

сумму чисел, полученных при вызове
,
обозначим через
:


2)

в
ыполняем вычисления:



3)

т
еперь остаётся вычислить ответ

обратным ходом

:

4)


5)

Ответ:
49
.

Ещё п
рЧмер

зТдТнЧя
:

Дан рекурсивный алгоритм:

void F(in
t n)

{


printf(

%d
\
n

,
n);


if
(n 6 )
{


F(n
+
2);


F(n
*3
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове
F(
1
)
.

Решение (вариант 1,
метод подстановки
):

6)

сначала определим рекуррентную формулу͖ обозначим через
G(n)

сумму чисел, которая
вывод
ится при вызове
F(n)

7)

при n >= 6 процедура выводит число
n

и заканчивает работу без рекурсивных вызовов:

G(n) = n

при
n �= 6

8)

при n < 6 процедура выводит число
n

и дважды вызывает сама себя:

G
(
n
) =
n

+
G
(
n
+2) +
G
(3
n
)

при
n

6

9)

в результате вызова F(1) получа
ем

G(1) = 1 + G(3) + G(3)

G(3) = 3 + G(5) + G(9) = 3 + G(5) + 9

G(5) = 5 + G(7) + G(15) = 5 + 7 + 15 = 27

10)

используем обратную подстановку:

G(3) = 3 + G(5) + 9 = 3 + 27 + 9 = 39

G(1) = 1 + 2*G(3) = 79

11)

Ответ:
79
.

Решение (вариант 2, динамическое программиро
вание):

1)

п. 1
-
3 такие же, как в первом варианте решения

2)

заполняем таблицу G(n) при
n

�= 6 (
где
G
(
n
) =
n
)

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

G(n)






6

7

8

9

10

11

12

13

14

15

3)

остальные ячейки заполняем
, начиная с n = 5 справа налево, используя формул
у :

G
(
n
) =
n

+
G
(
n
+2) +
G
(3
n
)


n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15


К. Поляков, 20
12
-
201
5


3

http://kpolyakov.
spb
.ru

G(n)

79

30

39

22

27

6

7

8

9

10

11

12

13

14

15

4)

ответ читаем в самой левой ячейке

5)

Ответ:
79
.

ПрЧмер

зТдТнЧя
:

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

*

)
;


�if (n 0) {


F(n
-
2);


F(n
/

2)
;


}

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Решение

(вариант 1, составление полной таблицы)
:

6)

сначала определим рекуррентную формулу͖ обозначим через G(n) количество звездочек,
которые выводит
программа при вызове F(n)

7)

из программы видим, что

G
(
n
) = 1 при всех
n

= 0

G(n) = 1 + G(n
-
2) + G(n
/

2) при n > 0

8)

вспомним, что
n
/

2



это частное от деления n на 2

9)

по этим формулам заполняем таблицу, начиная с нуля:

G(0) = 1

G(1) = 1 + G(
-
1) + G(
0) = 1 +

1 + 1 = 3

G(
2
) = 1 + G(
0
) + G(
1) = 1 + 1 + 3 = 5

G(
3
) = 1 + G(
1
) + G(
1) = 1 + 3 + 3 = 7

G(
4
) = 1 + G(
2
) + G(
2) = 1 +
5

+
5

=
11

G(
5
) = 1 + G(
3
) + G(
2) = 1 + 7 + 5 = 13

G(
6
) = 1 + G(
4
) + G(
3) = 1 + 11 + 7 = 19

G(
7
) = 1 + G(
5
) + G(
3) = 1 + 13 + 7 = 21

n

0

1

2

3

4

5

6

7

G(n)

1

3

5

7

11

13

19

21

10)

Ответ:
21
.

Решение (вариант 2,

с конца

):

1)

пп. 1
-
3


как в варианте 1

2)

по формулам G(7) =
1+
G(5) + G(3), поэтому нужно найти G(5) и G(3)

3)

G
(5) = 1 +
G
(3) +
G
(2), нужны
G
(3) и
G
(2)

4)

G(3) = 1 + G(1) + G(1), нужно G(1)

5)

G
(2) = 1 +
G
(0) +
G
(1) = 2 +
G
(1), нужно
G
(1)

6)

G(1) = 1 + G(
-
1) + G(0) = 1 + 1 + 1 = 3

7)

теперь идем

обратным ходом

:

G(2) = 2 + G(1) = 5

G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

8)

Ответ:
21
.

ПрЧмер зТдТнЧя
:

Алгоритм вычис
ления значений функций F(n) и G(n), где n


натуральное

число, задан
следующими соотношениями:

F(1) = 1; G(1) = 1;


К. Поляков, 20
12
-
201
5


4

http://kpolyakov.
spb
.ru

F(n) = F(n


1)


G(n


1),

G(n) = F(n

1) + G(n


1),
при

n�
=
2

Чему равно значение величины F(5)/G(5)?

В ответе запишите
только целое число
.

Решение:

9)

фактически рекуррентная формула задана для пары (
F
(
n
);
G
(
n
)
)

10)

замечаем, что F(n)


это разность

предыдущей пары, а
G
(
n
)


сумма
тех же значений

11)

заполняем таблицу, начиная с известной первой пары

n

1

2

3

4

5

F(n)

1

0


2


4


4

G(n)

1

2

2

0


4

12)

и
скомое значение
F
(5)/
G
(5) равно 1

13)

ответ:
1
.

Ещё
п
рЧмер зТдТнЧя
:

Алгоритм вычисления значения функции F(n), где n


натуральное число,

задан следующими соотношениями:

F(1) = 1

F(n) = F(n

1) * n, при n >

1

Чему равно значение функции F(5)?

В ответе запишите
только целое число
.

Решение
:


14)

используя заданную
рекуррентную
формулу, находим, что

F(5) = F(4) * 5

15)

применив формулу еще несколько раз, получаем

F(5) = F(
3
)
* 4
* 5

=

F(2)
*

3 *

4
* 5
=

F(1)
*

2 *
3 *

4
* 5

16)

мы дошли до базового случая, который останавливае
т рекурсию, так как определяет
значение F(1) = 1

17)

окончательно
F(5) = 1 *
2 *
3 * 4 * 5

= 120

18)

ответ:
120
.

Ещё п
рЧмер зТдТнЧя
:

Процедура
F(n), где n


натуральное число,

задан
а

следующим

образом (язык Паскаль)
:

void F(int n)

{


if
(
n 3
)


printf(

*

)
;


else
{


F(n
-
1);


F(n
-
2);


F(n
-
2)
;


}

}

Сколько звездочек напечатает эта процедура при вызове
F(
6
)?

В ответе запишите
только
целое число
.

Решение:

1)

эта задача по сути такая же, как и предыдущая, но

завёрнута


в другой фантик: для
n 3

(
то ест
ь, для 1 и 2
)

функция выводит одну звездочку

F
(1)

=

F
(2)

=

1


а для бóльших

n

имеем рекуррентную формулу


К. Поляков, 20
12
-
201
5


5

http://kpolyakov.
spb
.ru


F(n)

=

F(n
-
1)

+

F(n
-
2)

+

F(n
-
2)




= F(n
-
1) + 2*F(n
-
2)

2)

запишем в таблицу базовые случаи

n

1

2

3

4

5

6

F(n)

1

1





3)

заполняем таблицу, исполь
зуя рекуррентную формулу:

n

1

2

3

4

5

6

F(n)

1

1

3

5

11

21

F
(
3
) =
F
(
2
)

+ 2*F(
1
) = 3

F
(
4
) =
F
(
3
) + 2*F(2) =
5

F
(
5
) =
F
(
4
) + 2*F(
3
) =
11

F
(
6
) =
F
(
5
) + 2*F(
4
) =
21

4)

ответ:
2
1
.


К. Поляков, 20
12
-
201
5


6

http://kpolyakov.
spb
.ru

ЗТдТч
Ч

для тренЧрЭвкЧ
1
:

1)


Алгоритм вычисления значения функции F(n), где n


натур
альное число, задан следующими
соотношениями:

F(1) = 1

F(n) = F(n

1) *
(
n

+ 1)
,
при

�n 1

Чему равно значение функции F(5)? В ответе запишите
только целое число
.

2)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотнош
ениями:

F(1) = 1

F(n) = F(n

1) *
(
n

+
2
)
,
при

�n 1

Чему равно значение функции F(5)? В ответе запишите
только целое число
.

3)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F(1) = 1

F
(
n
) =
F
(
n

1) * (
2*
n

+
1
),
при

n

� 1

Чему равно значение функции F(4)? В ответе запишите
только целое число
.

4)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F(1) = 1

F
(
n
) =
F
(
n

1) * (2*
n

-

1),
при

n

� 1

Чему равно значение
функции F(
5
)? В ответе запишите
только целое число
.

5)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F(1) = 1

F
(
n
) =
F
(
n

1) * (
3
*
n

-

2
),
при

n

� 1

Чему равно значение функции F(4)? В ответе запишите
толь
ко целое число
.

6)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F
(0) = 1
,
F
(1) = 1

F
(
n
) =
F
(
n

1) +
F
(
n
-
2),
при

n


1

Чему равно значение функции F(
7
)? В ответе запишите
только целое число
.

7)

Алгоритм вычи
сления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F
(0) = 1
,
F
(1) = 1

F
(
n
) =
2*
F
(
n

1) +
F
(
n
-
2),
при

n

� 1

Чему равно значение функции F(
6
)? В ответе запишите
только целое число
.

8)

Алгоритм вычисления значения функции F(n
), где n


натуральное число, задан следующими
соотношениями:

F
(0) = 1
,
F
(1) = 1

F
(
n
) =
F
(
n

1) +
2*F
(
n
-
2),
при

n

� 1

Чему равно значение функции F(
6
)? В ответе запишите
только целое число
.

9)

Алгоритм вычисления значения функции F(n), где n


натуральное числ
о, задан следующими
соотношениями:

F
(0) = 1
,
F
(1) = 1

F
(
n
) =
3*
F
(
n

1)
-

F
(
n
-
2),
при

n

� 1




1

Источники заданий:

1.

Демонстраци
онны
е

вариант
ы

ЕГЭ 20
1
3

гг.

2.

Проверочные работы МИОО
.


К. Поляков, 20
12
-
201
5


7

http://kpolyakov.
spb
.ru

Чему равно значение функции F(
6
)? В ответе запишите
только целое число
.

10)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотнош
ениями:

F
(0) = 1
,
F
(1) = 1

F
(
n
) =
F
(
n

1)
*F
(
n
-
2)
+1
,
при

n

� 1

Чему равно значение функции F(
6
)? В ответе запишите
только целое число
.

11)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F
(0) = 1
,
F
(1) = 1

F
(
n
) =
F
(
n

1)*
F
(
n
-
2)+
2
,
при

n

� 1

Чему равно значение функции F(
5
)? В ответе запишите
только целое число
.

12)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F
(1) = 1,
F
(2) = 1

F
(
n
) =
F
(
n
-
2)
*n
,
при

n

� 2

Чему

равно значение функции F(
7
)? В ответе запишите
только целое число
.

13)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F
(1) = 1,
F
(2) = 1

F
(
n
) =
F
(
n
-
2)
*n

+ 2
,
при

n

� 2

Чему равно значение функции F(
8
)? В
ответе запишите
только целое число
.

14)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F
(1) = 1,
F
(2) = 1

F
(
n
) =
F
(
n
-
2)
*
(
n
-
1)
,
при

n

� 2

Чему равно значение функции F(
7
)? В ответе запишите
только целое чис
ло
.

15)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:

F
(1) = 1,
F
(2) = 1

F
(
n
) =
F
(
n
-
2)
*
(
n
-
1)

+ 2
,
при

n

� 2

Чему равно значение функции F(
8
)? В ответе запишите
только целое число
.

16)

Алгоритм вычисления знач
ения функции F(w), где
w

-

натуральное число, задан следующими
соотношениями:

F
(1) = 3;

F
(2)

=

3;

F
(
w
) = 5*
F
(
w
-
l
)
-

4*
F
(
w
-
2) при
w

� 2.

Чему равно значение функции F(15)?


17)

Алгоритм вычисления значения функции F(w), где
w

-

натуральное число, задан следующ
ими
соотношениями:

F
(1) =
4
;
F
(2)

= 5;

F
(
w
) = 4*
F
(
w
-
l
)
-

3*
F
(
w
-
2) при
w

� 2.

Чему равно значение функции F(
8
)?

18)

(
http
://
ege
.
yandex
.
ru
)
Алгоритм вычисления значений функций F(w) и Q(w), где
w

-

натуральное
число, задан с
ледующими соотношениями:

F
(1) =
1
;
Q
(
1
)

=
1
;

F
(
w
) =
F
(
w
-
l
)

+

2
*
Q
(
w
-
1
)
при

w

� 1

Q
(
w
) =
Q
(
w
-
l
)

-

2
*
F
(
w
-
1
)
при

w

� 1.

Чему равно значение функции F(
5
)
+
Q
(5)
?

19)

Алгоритм вычисления значения функции F(w), где
w

-

натуральное число, задан следующими
соотношениям
и:

F
(1) =
1
;
F
(2)

=
2
;


К. Поляков, 20
12
-
201
5


8

http://kpolyakov.
spb
.ru

F
(
w
) = 3*
F
(
w
-
l
)
-

2*
F
(
w
-
2)
при

w

� 2.

Чему равно значение функции F(
7
)?

20)

Алгоритм вычисления значения функции F(w), где
w

-

натуральное число, задан следующими
соотношениями:

F
(1) =
2
;
F
(2)

=
4
;

F
(
w
) =
4
*
F
(
w
-
l
)
-

3*
F
(
w
-
2) при
w

� 2.

Чему равно значение функции F(
7
)?

21)

(
http
://ege.
yandex
.
ru
) Алгоритм вычисления значения функции F(
n
), где
n

-

натуральное число,
задан следующими соотношениями:

F
(1) =
1
;
F
(2)

=
2
;

F
(
n
) = 5*
F
(
n
-
l
)
-

6*
F
(
n
-
2)
при

n

� 2.

Чему равно значение функции F(
7
)?

22)

(
http
://ege.
yandex
.
ru
) Алгоритм вычисления значения функции F(
n
), где
n

-

натуральное число,
задан следующими соотношениями:

F
(1) =
1
;
F
(2)

=
2
;

F
(3) = 3

F
(
n
) =
F
(
n
-
3
)
*
(
n
-
1
)
/3

при

n


3.

Чему равно значение функции F(
16
)?

23)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
2
;
G
(1) = 1;

F
(
n
) =
F
(
n

1)


G
(
n

1),

G
(
n
) =
F
(
n

1) +
G
(
n

1), при
n


=
2

Чему равно значение величины
F(5)/G(5)?

В ответе запишите
только целое число
.

24)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
1
;
G
(1) = 1;

F
(
n
) =
F
(
n

1)


G
(
n

1),

G
(
n
) =
F
(
n

1) + 2*
G
(
n

1),
при

n


=
2

Чему равно значен
ие величины F(5)/G(5)?

В ответе запишите
только целое число
.

25)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
1
;
G
(1) = 1;

F
(
n
) =
F
(
n

1)


2*
G
(
n

1),

G
(
n
) =
F
(
n

1) +
G
(
n

1),
при

n

�=2

Чему
равно значение ве
личины G
(5)/
F
(5)?

В ответе запишите
только целое число
.

26)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
1
;
G
(1) = 1;

F
(
n
) =
2*
F
(
n

1)


G
(
n

1),

G
(
n
) =
F
(
n

1) + 2*
G
(
n

1),
п
ри

n

�=2

Чему равно значение ве
личины G
(5)
+
F
(5)?

В ответе запишите
только целое число
.

27)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
1
;
G
(1) = 1;

F
(
n
) =
2*
F
(
n

1)


G
(
n

1),

G
(
n
) = 2*
F
(
n

1) +
G
(
n

1),
при

n

�=2

Чему равно значение ве
личины
F
(5)
-
G
(5)?

В ответе запишите
только целое число
.

28)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
1
;
G
(1) = 1;


К. Поляков, 20
12
-
201
5


9

http://kpolyakov.
spb
.ru

F
(
n
) =
F
(
n

1)


2*
G
(
n

1),

G
(
n
) =
F
(
n

1) +
2*
G
(
n

1),
при

n

�=2

Чему равно значение ве
личины
G
(5)
-
F
(5)?

В ответе запишите
только целое число
.

29)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
1
;
G
(1) = 1;

F
(
n
) =
3*
F
(
n

1)


2*
G
(
n

1),

G
(
n
) =
F
(
n

1) +
2*
G
(
n

1),
при

n

�=2

Чему равно значение ве
личины
G
(5)
-
F
(5)?

В ответе запишите
только целое число
.

30)

Алгоритм вычисления значений функций F(n) и G(n), где n


натуральное число, задан
следующими соотношениями:

F
(1) =
1
;
G
(1) =

1;

F
(
n
) =
3*
F
(
n

1)


3
*
G
(
n

1),

G
(
n
) =
F
(
n

1) +
2*
G
(
n

1),
при

n

�=2

Чему равно значение ве
личины
F
(5)
-
G
(5)?

В ответе запишите
только целое число
.

31)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(″*″);


�if (n 0) {


F(n
-
2);



F(n
/

2)
;



F(n
/

2)
;


}

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(
5
)?

32)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(″*″);


�if (n 0) {


F(n
-
2);


F(n
-
2);



F(n
/

2)
;


}

}


Сколько символов "звездочка" будет напечатано на экране

при выполнении вызова F(
6
)?

33)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(″*″);


�if (n 0) {


F(n
-
3
);



F(n
/

2)
;


}

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(
7
)?

34)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(″*″);


К. Поляков, 20
12
-
201
5


10

http://kpolyakov.
spb
.ru


�if (n 0) {


F(n
-
3
);


F(n
-
2
);



F(n
/

2)
;


}

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(
7
)?

35)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(″*″);


�if (n 0) {


F(n
-
3
);


F(n
-
2
);



F(n
/

2)
;



F(n
/

2)
;


}

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(
6
)?

36)

Дан рекурсивный алгоритм:

void F(int n)

{

printf(″*″);


�if (n 0) {


printf(″*″);


F(n
-
2
);



F(n
/

2)
;


}

}


Сколько символов "звездочка" буде
т напечатано на экране при выполнении вызова F(
7
)?

37)

Дан рекурсивный алгоритм:

void F(int n)

{

printf(″*″);


�if (n 0) {


printf(″*″);


F(n
-
2
);



F(n
/

2)
;



F(n
/

2)
;


}

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызов
а F(
7
)?

38)

Дан рекурсивный алгоритм:

void F(int n)

{

printf(″*″);


�if (n 0) {


printf(″*″);


F
(
n
-
2);


F
(
n
-
2);


F
(
n

/

2);


К. Поляков, 20
12
-
201
5


11

http://kpolyakov.
spb
.ru


}

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(
6
)?

39)

Дан рекурсивный алгоритм:

void F(int

n)

{


�if (n 0) {


F(n
-
2
);


F(n
-
1
);




F(n
-
1
)
;


}


printf(″*″);

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(
5
)?

40)

Дан рекурсивный алгоритм:

void F(int n)

{


�if (n 0) {


printf(″*″);


F(n
-
2
);


F(n
-
1
)
;




F(n
-
1
)
;


}


printf(″*″);

}


Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(
5
)?

41)

Дан рекурсивный алгоритм:

void F(int n)

{


�if (n 1)
{


F(n
-
2
);


F(n
-
1
);




F(n

/

2
)
;


}


printf(″*″);

}


Сколько символов "звездо
чка" будет напечатано на экране при выполнении вызова F(
7
)?

42)

Дан рекурсивный алгоритм:

void F(int n)

{


if
�(n 2)
{


printf(″*″);


F(n
-
2
);


F(n
-
1
);




F(n

/

2
)
;


}


printf(″*″);

}


Сколько символов "звездочка" будет напечатано на экране при выпол
нении вызова F(
6
)?

43)

Алгоритм вычисления значения функции F(n), где n


натуральное число, задан следующими
соотношениями:


К. Поляков, 20
12
-
201
5


12

http://kpolyakov.
spb
.ru

F
(
1
) = 1
,

F
(
n
) =
F
(
n

1)

+

2
n
-
1
,
при

n

� 1

Чему равно значение функции F(
12
)? В ответе запишите только целое число.

44)

Дан рекурсивный алго
ритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if
(n 6 )
{


F(n+2);


F(n*3)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
2
).

45)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 5)
{


F(n+2);


F(n*
2
)
;


}

}

Найдите су
мму чисел, которые будут выведены при вызове F(
1
).

46)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 5)
{


F(n+
3
);


F(n*
3
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
1
).

47)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 7)
{


F(n+
3
);


F(n*
2
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
2
).

48)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 7)
{


F(n+
2
);


F(n
+3
)
;


}


К. Поляков, 20
12
-
201
5


13

http://kpolyakov.
spb
.ru

}

Найдите сумму чисел, которые буду
т выведены при вызове F(
1
).

49)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 5)
{


F(n+
2
);


F(n
+3
)
;


F(n
*2
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
1
).

50)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 5)
{


F(n+
1
);


F(n
+
2
)
;


F(n
*
3
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
2
).

51)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if
(n 6 )
{


printf(

%d
\
n

,
n);


F(n+2);


F(n*3)
;


}

}

Найдите сумм
у чисел, которые будут выведены при вызове F(
2
).

52)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 5)
{


printf(

%d
\
n

,
n);


F(n+
3
);


F(n*3)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
1
).

53)

Дан рекурсивный алгорит
м:

void F(int n)

{


printf(

%d
\
n

,
n);


if
(n 6 )
{


К. Поляков, 20
12
-
201
5


14

http://kpolyakov.
spb
.ru


printf(

%d
\
n

,
n);


F(n+
2
);


F(n
+
3)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
1
).

54)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 7)
{


printf(

%d
\
n

,
n)
;


F(n+
1
);


F(n
+2
)
;


F(n
*
3)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
2
).

55)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if
(n 6 )
{


printf(

%d
\
n

,
n);


F(n+
1
);


F(n
+2
)
;


F(n
*2
)
;


}

}

Найдите сумму чисел,

которые будут выведены при вызове F(
1
).

56)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if
(n 6 )
{


printf(

%d
\
n

,
n);


F(n+
1
);


F(n
*2
)
;


F(n
*3
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
2
).

57)

Дан рекурсивный алг
оритм:

void F(int n)

{


printf(

%d
\
n

,
n);


if (n 7)
{


printf(

%d
\
n

,
n);


F(n+
2
);


F(n
*2
)
;


F(n
*3
)
;


К. Поляков, 20
12
-
201
5


15

http://kpolyakov.
spb
.ru


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
1
).

58)

Алгоритм вычисления значения функции F(
n
), где
n



натуральное число, задан след
ующими
соотношениями:

F
(
n
) =
1 при
n



2
;

F
(
n
) =
F
(
n
-
2
)*(
n+
2)
при

n

� 2.

Чему равно значение функции F(
8
)?

59)

Алгоритм вычисления значения функции F(
n
), где
n



натуральное число, задан следующими
соотношениями:

F
(
n
) =
1 при
n



2
;

F
(
n
) =
F
(
n
-
2)*(
n
+1)
при

n

� 2.

Чему равно значение функции F(
7
)?

60)

Дан рекурсивный алгоритм:

void F(int n)

{


printf(

%d
\
n

,
n);


�if (n 0) {


F(n
-
1
);


F(n
-
3
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
5
).

61)

Дан рекурсивный алгоритм:

void F(int n)

{


printf
(

%d
\
n

,
n);


�if (n 1)
{


F(n
-
3
);


F(n
-
1
)
;


}

}

Найдите сумму чисел, которые будут выведены при вызове F(
6
).

62)

Дан рекурсивный алгоритм:


int F(int n)

{


if
�(n 2 )


F(n
-

1) + F(n
-

2)
;


else


n;

}

Чему будет равно значение, вычи
сленное алгоритмом при выполнении вызова
F(
5
)
?

63)

(И. Тощенко)

Дан рекурсивный алгоритм:


int F(int n)

{


�if (n 3 )


F
(
n

-

1) *
F
(
n

-

2)
;


else


n
;

}

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова
F(
6
)
?


К. Поляков, 20
12
-
201
5


16

http://kpolyakov.
spb
.ru

64)

(И. То
щенко)

Дан рекурсивный алгоритм:


int F(int n)

{


�if (n = 3 )


F(n
-
3) + F(n
-
2)*F(n
-
1)
;


else


n;

}

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова
F(
7
)
?

65)

(И. Тощенко)

Дан рекурсивный алгоритм:


int F(int n)

{


if (n 5 )


F(n+2) + F(n+3) + F(n+1)
;


else


n;

}

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова
F(
2
)
?

66)

(И. Тощенко)

Дан рекурсивный алгоритм:


int F(int n)

{


if (n 5 )


F(n*3) + F(n+3) + F(n+
1)
;


else


n
/

2;

}

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова
F(
2
)
?

67)

(И. Тощенко)

Дан рекурсивный алгоритм:


int F(int n)

{


if (n 5 )


F(n+3) + F(2*n) + F(3*n
/

2)
;


else


n +

2;

}

Чему буде
т равно значение, вычисленное алгоритмом при выполнении вызова
F(
3
)
?

68)

(И. Тощенко)

Дан рекурсивный алгоритм:


int F(int n)

{


if
(
n 6

)


n+F(n+3) * F(2*n)
;


else


n*2;

}

Чему будет равно значение, вычисленное алгоритмом при выполнени
и вызова
F(
3
)
?

69)

(И. Тощенко)

Дан рекурсивный алгоритм:


int F(int n)

{


if
(
�n 1
)


2*n

+ F(n
-
3) + F(n
-
2)
;


else


К. Поляков, 20
12
-
201
5


17

http://kpolyakov.
spb
.ru


n

+

5;

}

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова
F(
6
)
?



Приложенные файлы

  • pdf 24150885
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий