Задание 3. Тип заданий 11: рекурсивные алгоритмы.
- Задание:
Ниже на записан алгоритм рекурсивной процедуры F: Pascal: | Procedure F(n: integer);
begin
if n > 0 then
begin
F(n-1);
F(n div 2);
F(n-2);
end;
if n>1 then
writeln(n)
else
writeln(0-n);
end; |
Чему будет равна сумма выведенных значений при вызове процедуры F(4)?
- Решение:
Давайте сначала разберёмся, какие процедуры будут вызваны после вызова F(5). Как мы видим, пока N > 0 будут вызываться F(n-1), F(n div 2), F(n-2). Построим граф: По условию при n>1 выводится значение n, а при n<=1 — значение 0-n. Выражение 0-n по сути делает число n отрицательным. Подсветим все значения n>1 синим, а n<=1 — красным: Итак, синие значения будут выведены такими же, как и записаны, а красные поменяют знак на противоположный. Сумма синих равна: 4+3+2+2+2=13 Сумма красных равна: -1-1-1-1+1+1+1+1-1-1+1+1-1-1+1+1=0 Общая сумма равна 13+0=13 Ответ: 13
|
Комментарии ()
Елизавета Красильникова
#
15 июня 2016 в 21:26
0
|
|
Разве ответ не 9? Программа же сначала просчитывает все, а только потом выводит на экран число. Или я ошибаюсь?
|
|