Question

Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln('*'); if n > 0 then begin writeln('*'); F(n-2); F(n div 2); F(n div 2); end end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Answer 1

Ответ:

61

Объяснение:

function f(n:integer):integer;

var i:int64;

begin

 i:=1;

 if n>0 then i:=2+f(n-2)+f(n div 2)+f(n div 2);

 f:=i;

end;

begin

 writeln(f(7));

end.

Answer 2

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

Алгоритм F(n) выполняет следующие действия:

1. Печатает одну звездочку (writeln('*')).

2. Если n больше 0, то алгоритм выполняет следующие шаги:

   • Печатает еще одну звездочку (writeln('*')).
   • Вызывает F(n-2).
   • Вызывает F(n div 2).
   • Вызывает F(n div 2).

Давайте рассмотрим, что происходит при вызове F(7):

1. Первый вызов F(7) печатает 1 звездочку, и n становится равным 7 - 2 = 5.

2. Второй вызов F(5) также печатает 1 звездочку и делает следующие вызовы:

   • F(3) (печатает 1 звездочку, n становится равным 1)
   • F(2) (печатает 1 звездочку, n становится равным 1)

3. При вызове F(3) печатается 1 звездочка, n становится равным 1, и вызовы F(1) и F(1) печатают по одной звездочке каждый.

Итак, при вызове F(7) будет напечатано следующее количество звездочек:

1 (из F(7)) + 1 (из F(5)) + 1 (из F(3)) + 1 (из F(1)) + 1 (из F(2)) + 1 (из F(1)) = 6 звездочек.

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