Задача к ЕГЭ по информатике на тему «рекурсия» №1

Просмотров 5 Комментарии 0

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

|------------------------|---------------|------------------| |Pascal |Python |C | |procedure-F(n:-integer);-|def-F(n):------|void-F-(int-n){-----| | | | | |begin | if n > 2: | if (n > 2 ){ | | if n > 2 then | print(” ∗ ”) | printf(” ∗ ”);| | begin | F (n − 1) | F (n − 1); | | writeln (” ∗ ”); | F (n∕∕2 ) | F (n∕2); | | F (n − 1); | | } | | | | | | F (n div 2); | |} | | end; | | | -end.——————————————————— » class=»math-display» width=»auto»></center> Сколько символов «<img decoding=

Данная рекурсивная функция останавливается, если $n$ принимает значение 2 или меньше. Следовательно, начнем выполнение функции, когда $n = 3$ . С помощью стрелочки $→$ обозначим печать символа на экране.

При запуске $F (3)$ на экране появляется один символ « $∗$ ». Далее никакие функции не вызываются. $F (3) → ∗$ .

При запуске $F (4)$ на экране появляется один символ « $∗$ ». Далее вызываются функции $F (4 − 1 = 3)$ и $F (4∕2 = 2)$ . Так как $n > 2 » class=»math» width=»auto»>, то смотрим на <img decoding=$ и добавляем количество символов от данной функции к количеству символов от $F (4)$ .

$F(3) → ∗$

$F(4) → ∗∗$ .

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

$F(3) → ∗$ ;

$F(4) → ∗∗$ ;

$F(5) → ∗ ∗ ∗$ . Т.к. $5 > 2 » class=»math» width=»auto»> печатется один символ «<img decoding=$ » , а также вызывались функции $F (4)$ и $F (2)$ . Так как $n > 2 » class=»math» width=»auto»>, то взяли кол-во символов только от <img decoding=$ .

$F(6) → ∗ ∗ ∗ ∗ ∗$ . Т.к. $6 > 2 » class=»math» width=»auto»> печатется один символ «<img decoding=$ » , а также вызывались функции $F(5)$ и $F (3$ ). Того 5 символов.

$F(7) → ∗ ∗ ∗ ∗ ∗ ∗ ∗$ . Т.к. $7 > 2 » class=»math» width=»auto»> печатется один символ «<img decoding=$ » , а также вызывались функции $F(6)$ и $F (3)$ . Того 7 символов.

Ответ: 7