Question

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

Бейсик	Python
DECLARE SUB F(n) SUB F (n) IF n > 0 THEN F(n \ 4) PRINT n F(n - 1) END IF END SUB	def F(n): if n > 0: F(n // 4) print(n) F(n - 1)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin if n > 0 then begin F(n div 4); write(n); F(n - 1); end end;	алг F(цел n) нач если n > 0 то F(div(n, 4)) вывод n F(n - 1) все кон
Си++
void F(int n){ if (n > 0){ F(n / 4); std::cout << n; F(n - 1); } }

В качестве ответа укажите последовательность цифр, которая будет напечатана на экране в результате вызова F(5).

Accepted Answer

1514321

Answer

Идея решения: проследить порядок выполнения рекурсивных вызовов и выводов, учитывая, что каждый вызов сначала рекурсивно обращается к F(n // 4), затем выводит n, затем рекурсивно обращается к F(n - 1).

Проследим вызов F(5):

```
F(5):
  F(5 // 4) = F(1):
    F(1 // 4) = F(0): (условие n > 0 не выполнено, выход)
    вывод: 1
    F(1 - 1) = F(0): (условие n > 0 не выполнено, выход)
  вывод: 5
  F(5 - 1) = F(4):
    F(4 // 4) = F(1):
      F(1 // 4) = F(0): (условие n > 0 не выполнено, выход)
      вывод: 1
      F(1 - 1) = F(0): (условие n > 0 не выполнено, выход)
    вывод: 4
    F(4 - 1) = F(3):
      F(3 // 4) = F(0): (условие n > 0 не выполнено, выход)
      вывод: 3
      F(3 - 1) = F(2):
        F(2 // 4) = F(0): (условие n > 0 не выполнено, выход)
        вывод: 2
        F(2 - 1) = F(1):
          F(1 // 4) = F(0): (условие n > 0 не выполнено, выход)
          вывод: 1
          F(1 - 1) = F(0): (условие n > 0 не выполнено, выход)
```

Порядок выводов: 1, 5, 1, 4, 3, 2, 1.

Задание №16Алгоритмы и исполнителиЕГЭ по информатике