Question

Дан рекурсивный алгоритм: procedure F(n: integer); begin if n > 0 then begin F(n-2); F(n-1); end; writeln('*'); end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)? (НУЖНО РЕШЕНИЕ)

Answer 1

В случае F(0) или от меньшего числа будет напечатана одна звездочка.

В случае F(1) будут вызваны F(0) и F(-1), каждая из которых напечатает по одной звездочке и сама F(1) напечатает еще одну - итого 3.

В случае F(2) будут вызваны F(1) и F(0). F(1), как мы выяснили, в результате своей работы напечатает 3 звездочки, F(0) - одну и еще одну сама F(2). Итого: 5

Таким образом, F(3) = F(2) + F(1) + 1 = 3+5+1 = 9

F(4) = F(3) + F(2) + 1 = 9 + 5 + 1 = 15

F(5) = F(4) + F(3) + 1 = 15 + 9 + 1 = 25

Ответ: 25

Answer 2

Давайте разберемся, как работает данный рекурсивный алгоритм и сколько символов "звездочка" будет напечатано на экране при вызове F(5).

Когда функция F вызывается с аргументом n, она проверяет, если n больше 0, то вызывает себя дважды с аргументами n-2 и n-1, а затем выводит символ "*" на экран.

Давайте представим дерево вызовов для F(5):

F(5) /
F(3) F(4) / \ /
F(1) F(2) F(2) F(3) / \ / \ /
F(-1) F(0) F(0) F(1) F(1) F(2) / \ / \ /
F(-2) F(-1) F(-1) F(0) F(0) F(1)

Когда алгоритм вызывается с отрицательным значением n, он просто завершает выполнение без вывода символа "*".

Теперь давайте посчитаем количество символов "*" в этом дереве вызовов:

1. Каждый вызов F(n) выводит одну звездочку, за исключением случаев, когда n <= 0.
2. Все вызовы F(n) с n <= 0 не выводят символ "*" на экран.

Таким образом, нам нужно посчитать, сколько раз функция F будет вызвана с аргументами, которые больше 0.

Посчитаем:

F(5) вызывает F(3) и F(4) (1 раз) F(3) вызывает F(1) и F(2) (2 раза) F(4) вызывает F(2) и F(3) (2 раза) F(2) вызывает F(0) и F(1) (2 раза) F(3) вызывает F(1) и F(2) (2 раза) F(1) вызывает F(-1) и F(0) (1 раз) F(2) вызывает F(0) и F(1) (2 раза) F(0) не делает вызова F(1) вызывает F(-1) и F(0) (1 раз) F(-1) и F(0) не делают вызовов

Теперь сложим все вызовы, которые приводят к выводу символа "*":

1 + 2 + 2 + 2 + 2 + 1 + 2 + 1 = 13

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