ЕГЭ - Демоверсия 2018 №11

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

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

Решение:

1. F(9) => n = 9

9>0 => “9” F(9-3) = F(6); F(9 div 3) = F(3)

2.1 n = 6

6>0 => “6” F(6-3) = F(3); F(6 div 3) = F(2)

n = 3

3>0 => “3” F(3-3) = F(0); F(3 div 3) = F(1)

n = 1

1>0 => “1” F(1-3) = F(-2); F(1 div 3) = F(0)

n=2

2>0 => “2” F(2-3) = F(-1); F(2 div 3) = F(0)

2.2 n=3

3>0 => “3” F(3-3) = F(0); F(3 div 3) = F(1)

n = 1

1>0 => “1” F(1-3) = F(-2); F(1 div 3) = F(0)

Вариантов удовлетворяющих условию больше нет. Получили следующую очерёдность чисел:

9631231

Ответ: 9631231

ЕГЭ - Демоверсия 2017 №11

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

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

 

Решение:

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

Рассмотрим решение по шагам.

Изначально n = 10.

1. 10 > 2 => «10», F(7), F(6);

После первого шага рекурсивных функций становится две, и соответственно, на втором шаге условие проверится два раза.

2.1 7 > 2 => «7», F(4), F(3)

2.2 6 > 2 => «6», F(3), F(2)

После второго шага рекурсивных функций станет 4, но F(2) не пройдёт условие.

3.1 4 > 2 => «4», F(1), F(0)

3.2 3 > 2 => «3», F(0), F(-1)

3.3 3 > 2 => «3», F(0), F(-1)

После третьего шага рекурсивных функций станет 6, но все они не пройдут условие и значит выполнение закончится.

Складываем числа, которые были выведены в процессе выполнения алгоритма: 10 + 7 + 6 + 4 + 3 + 3 = 33.

 

Ответ: 33