Def f n print if n 0 f n 2 f n 2 сколько звездочек напечатает эта процедура при вызове f 7

ЕГЭ ПО ИНФОРМАТИКЕ

1) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1
F(n) = F(n–1) * (n + 1), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.
Решение:
F(5)= F (4)*6=60*6=360
F(4)= F (3)*5=12*5=60
F (3)= F (2)*4=3*4=12
F (2)= F (1)*3=1*3=3
Ответ: 360
Решение на Python:
def F( n ):
if n==1: return 1
if n>1: return F(n-1)*(n+1)
print ( F (5))
Ответ:360

2) Алгоритм вычисления значения функции F(w), где w — натуральное число, задан следующими соотношениями:
F (1) = 3; F (2) = 3;
F ( w ) = 5* F ( w — l )- 4* F ( w -2) при w > 2.
Чему равно значение функции F(15)?
Решение на Python:
def F ( w ):
if w==1: return 3
if w==2: return 3
if w>2: return 5*F(w-1)-4*F(w-2)
print(F(15))
Ответ: 3

3) Алгоритм вычисления значений функций 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)?
Решение на Python:
def F ( w ):
if w==1: return 1
if w>1: return F(w-1)+2*Q(w-1)
def Q(w):
if w==1: return 1
if w>1: return Q(w-1)-2*F(w-1)
print(F(5)+Q(5))
Ответ: -14

4) Дан рекурсивный алгоритм:
def F ( n ):
print (‘*’)
if n > 0:
F ( n -2)
F ( n // 2)
F ( n // 2)
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(5)?
Решение на Python:
s=0
def F(n):
global s
#print(‘*’)
s=s+1
if n > 0:
F(n-2)
F(n // 2)
F(n // 2)
F(5)
print (s)
Ответ:34

5) Дан рекурсивный алгоритм :
def F(n):
print(‘*’)
if n > 0:
print(‘*’)
F(n-2)
F(n // 2)
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(7)?
Решение на Python:
s=0
def F(n):
global s
#print(‘*’)
s=s+1
if n > 0:
#print(‘*’)
s=s+1
F(n-2)
F(n//2)
F(7)
print (s)
Ответ :31

6) Дан рекурсивный алгоритм :
def F(n):
print(n)
if n < 5:
F(n+2)
F(n*2)
Найдите сумму чисел, которые будут выведены при вызове F(1).
Решение на Python:
s=0
def F(n):
global s
#print(n)
s=s+n
if n <5:
F(n+2)
F(n*2)
F(1)
print (s)
Ответ :53

7) Дан рекурсивный алгоритм:
def F ( n ):
if n > 2:
return F(n — 1) + F(n — 2)
else :
return n
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(5)?
Решение на Python:
def F(n):
if n > 2:
return F(n — 1) + F(n — 2)
else:
return n
print(F(5))
Ответ: 8

8) Определите, что выведет на экран программа при вызове F(7).
def F(n):
n -= 1
if n > 2:
print(n, end=»)
F(n — 1)
G(n — 2)
else:
print(n+2, end=»)
def G(n):
print(n, end=»)
if n > 2:
n -= 1
G(n — 1)
F(n — 2)
Решение на Python:
def F(n):
n -= 1
if n > 2:
print(n, end=»)
F(n — 1)
G(n — 2)
else:
print(n+2, end=»)
def G(n):
print(n, end=»)
if n > 2:
n -= 1
G(n — 1)
F(n — 2)
print(F( 7 ))
Ответ: 6442422

F (0) = 0,

F ( n ) = F ( n / 2), когда n > 0 и делится на 2,

F ( n ) = F ( n – 1) + 3 , когда n > 0 и не делится на 2.

Сколько существует значений n, принадлежащих отрезку [1; 1000], для которых F (n) равно 18?

Задача №11. Использование рекурсивных алгоритмов.

Рекурсия — это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта.

Для того, чтобы задать рекурсию, необходимо описать:

— условие остановки рекурсии (базовый случай);

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

Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия — основной прием программирования).

Классическим примером рекурсивного алгоритма является описание вычисления факториала:

Рекурсивные алгоритмы вычисления одной функции

Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми ре­кур­рент­ны­ми со­от­но­ше­ни­я­ми:

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

В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.

По­сле­до­ва­тель­но на­йдём зна­че­ния функции от базового случая F(1) до искомого значения F(6):

Рекурсивные алгоритмы вычисления нескольких функций

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

G(n) = F(n–1) + 2*G(n–1), при n >=2

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

По­сле­до­ва­тель­но на­йдём зна­че­ния функций от базового случая F(1), G(1) до искомых значений F(5), G(5):

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

G(2) = F(1) + 2*G(1) = 1+2 = 3;

F(3) = F(2) – G(2) = 0 – 3 = -3;

G(3) = F(2) + 2*G(2) = 0+6 = 6;

F(4) = F(3) – G(3) = -3 – 6 = -9 ;

G(4) = F(3) + 2*G(3) = -3+12 = 9;

F(5) = F(4) – G(4) = -9 – 9 = -18;

G(5) = F(4) + 2*G(4) = -9+18 = 9.

Рекурсивные алгоритмы выполнения процедур

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­сан ре­кур­сив­ный ал­го­ритм F.

Бей­сик

Python

PRINT n

IF n < 5 THEN

END IF

Пас­каль

Ал­го­рит­ми­че­ский язык

begin

writeln(n);

if n < 5 then

begin

end

нач

вывод n, нс

если n < 5 то

все

Си

if (n < 5) <

Чему равна сумма всех чисел, на­пе­ча­тан­ных на экра­не при вы­пол­не­нии вы­зо­ва F(1)?

Выпишем последовательно все действия, которые выполнят запускаемые процедуры:

F (1) выполнит следующие действия : Вывод числа 1, F(2), F(4)

F (2) выполнит следующие действия : Вывод числа 2, F(3), F(5)

F (4) выполнит следующие действия : Вывод числа 4, F(5), F(7)

F (3) выполнит следующие действия : Вывод числа 3, F(4), F(6)

F (5) выполнит следующие действия : Вывод числа 5

F (5) выполнит следующие действия : Вывод числа 5

F (7) выполнит следующие действия : Вывод числа 7

F (4) выполнит следующие действия : Вывод числа 4, F(5), F(7)

F (6) выполнит следующие действия : Вывод числа 6

F (5) выполнит следующие действия : Вывод числа 5

F (7) выполнит следующие действия : Вывод числа 7

Просуммируем все числа, выведенные на экран: 1+2+4+3+5+5+7+4+6+5+7 = 49

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­са­ны две ре­кур­сив­ные функ­ции (процеду­ры): F и G.

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(11)?

Выпишем последовательно все действия, которые выполнят запускаемые процедуры:

F(11) G(10) * F(7) G(6) * F(3) G(2) * F(-1)

Всего на экране будет напечатано 3 «звездочки».

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

procedure F(n: integer);

begin

writeln(‘*’);

if n > 0 then begin

F(n-3);

F(n-2);

F(n div 2);

F(n div 2);

end

end;

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

Для наглядности изобразим схему работы алгоритма в виде дерева:

Причем, распишем до конца каждое значение F(n) только один раз. Например, расписав один раз F(1), мы видим, что она напечатает в результате 5 звездочек. Т.е. F(1) = 5.

ЕГЭ по информатике — Задание 11 (Рекурсия)

Одиннадцатое задание из ЕГЭ по информатике обычно даётся на рекурсию.

В программировании рекурсией называется процесс, когда функция (процедура) вызывает сама себя или, когда две функции попарно вызывают друг друга.

Переходим к задачам 11 задания из ЕГЭ по информатике

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Бейсик	Python
Паскаль	Алгоритмический язык
Си++

Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(1). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Задачу будем рассматривать на языке программирования паскаль.

В начале, в процедуру F передаётся переменная n, значение которой равно 1.

Первом делом в процедуре переменная n проходит проверку: меньше ли переменная n восьми (n прежде чем завершит первоначальную функцию F(1)! .

При анализе процедуры F(2), мы всё равно смотрим на ту же самую процедуру, начинаем её анализировать с начала , но c другим параметром n = 2. Снова n проходит проверку, что она меньше 8. Успешно пройдя это условие (2 не запустит новых процедур , а завершиться, ничего не сделав больше.

После того, как процедура F(8) полностью завершиться, нужно закончить процедуру F(4). В процедуре F(4) напечатается переменная n . Т.е. напечатается первое число 4. Дальше процедура F(4) запустит процедуру F(n+3), т.е. запустится процедура F(7).

В процедуре F(7) переменная n = 7 успешно пройдёт условие (7 напечатает 7 , и промежуточный ответ будет: 47. Далее, запустится процедура F(7+3), но в ней переменная снова не пройдёт условие (10 не меньше 8), поэтому F(10) ничего не даст!

Здесь процедура F(7) будет завершена! После чего завершиться и F(4)!

Теперь нужно доделать процедуру F(2). Печатаем 2 . Теперь промежуточный ответ будет 472. И запускаем процедуру F(2+3).

В процедуре F(5) переменная n проходит условие (5 печатается 5 . Промежуточный ответ получается 4725. И запускается процедура F(5 + 3), в которой переменная n тоже не пройдёт условие (8 не меньше 8!), и процедура F(5 + 3) не принесёт никаких плодов.

На этом завершается процедура F(5), а после этого завершается и процедура F(2).

Вот теперь мы вернулись к первоначальной процедуре F(1). Следующая команда в процедуре F(1) будет: печать 1 . В общий ответ записываем ещё одно число 47251

Процедура F(1) запускает ещё одну процедуру F(1+3).

В этой процедуре F(4) переменная n легко удовлетворяет условию (4 прибавит к ответу число 4 , который станет 472514.

Процедура F(4) запустит ещё одну процедуру F(4 + 3).

Процедура F(7) выполнится в полном объёме, потому что 7 Напечатается 7 . Строчка, которую хотим записать в ответе, станет равна 4725147. Запустится ещё одна процедура F(7 + 3), но снова (10 не меньше 8!). На этом F(7) завершится.

И на этом завершится первоначальная процедура F(1). В ответе напишем 4725147!

Графический метод решения

Оранжевым -показан ход выполнения программы.

Красным — отмечены процедуры, в которых переменная n не прошла проверку (n

Пометка красного креста под процедурой означает, что в данной процедуре переменная n не прошла проверку условия ( n >= 3 ).

Как видно из графического решения ответ будет 4322322.

Ответ: 4322322

Определите, сколько звёздочек будет напечатано в результате вызова F(5) приведённой программы:

Бейсик	Python
Паскаль	Алгоритмический язык
Си++

Решение:

В этой задачке в любом случае печатается звёздочка, если процедура была запущена, т.к. сама печать на входит в условие! Если условие (n > 1) выполняется, то процедура запускает ещё две процедуры.

Красным цветом отмечены процедуры, в которых переменная n не проходит условие. Значит, такие процедуры не запускают новых процедур. Оранжевым цветом показан ход выполнения программы.

Теперь не сложно подсчитать количество команд печати! В ответе напишем 13.

Задача (С двумя функциями F и G)

Даны рекурсивные алгоритмы F и G. Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(8) ?

Бейсик	Python
Паскаль	Алгоритмический язык
Си++

Решение:

Решаем данную задачу из тренировочного варианта ЕГЭ по информатике, как всегда, на языке паскаль.

Слово forward обозначает, что мы объявляем процедуру, но не прописываем сразу тело процедуры. Ведь внутри этой процедуры мы хотим вызывать вторую процедуру, которая ещё не описана. Поэтому применяется такой приём: мы обозначаем процедуру G, но тело процедуры прописываем, когда уже есть вторая процедура F.

Ничего нет сложного, когда работаем с двумя процедурами, которые вызывают друг друга. Действуем так же!

Процедура G(0) не вызовет процедуру F, т.к. не выполнится условие (n > 1), но данная процедура напечатает своё число, потому что команда печати не входит в условие.

Ответ напишем 6 + 3 + 0 = 9.

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

F(n) = F(n — 1) + n — 2, при n > 1
F(1) = 2

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

F(7) = F(6) + 7 — 2 = F(5) + 6 — 2 + 7 — 2 = F(4) + 5 — 2 + 6 — 2 + 7 — 2 =

= F(3) + 4 — 2 + 5 — 2 + 6 — 2 + 7 — 2 = F(2) + 3 — 2 + 4 — 2 + 5 — 2 + 6 — 2 + 7 — 2 =

= F(1) + 2 — 2 + 3 — 2 + 4 — 2 + 5 — 2 + 6 — 2 + 7 — 2 =

= 2 + 2 — 2 + 3 — 2 + 4 — 2 + 5 — 2 + 6 — 2 + 7 — 2 = 17