Отправлено: 27.07.19 07:27. Заголовок: задача из ЕГЭ паскаль, при каком условии завершается?

Добрый день! Программа печатает звездочку (*) 4 раза. Но не могу понять, когда программа заканчивает свою работу при каком n или F(n)? Я на листочке решаю у меня 3 звезды, а по шагам в паскале не могу отследить изменение значений.
procedure F(n: integer); forward;
procedure G(n: integer); forward;

procedure F(n: integer);
begin
if n mod 5=0 then G(n-5)
else F(n-3);
end;

procedure G(n: integer);
begin
writeln('*');

if n > 0 then F(n-1)
end;

begin
F(51);
end.

 Отправлено: 27.07.19 12:15. Заголовок: Ответ

Здравствуйте, Eugeny1984!

F(51) = F(48)
F(48) = F(45)
F(45) = G(40)
G(40) = * F(39)
F(39) = F(36)
F(36) = F(33)
F(33) = F(30)
F(30) = G(25)
G(25) = * F(24)
F(24) = F(21)
F(21) = F(18)
F(18) = F(15)
F(15) = G(10)
G(10) = * F(9)
F(9) = F(6)
F(6) = F(3)
F(3) = F(0)
F(0) = G(-5)
G(-5) = *

Осталось пройти в обратном порядке:

F(0) = G(-5) = *
F(3) = F(0) = *
...

F(9) = F(6) = *
G(10) = * F(9) = **
F(15) = G(10) = **

...

F(51) = F(48) = ****

 Отправлено: 27.07.19 14:29. Заголовок: polyakovss пишет: ..

polyakovss пишет:
[quote]` У меня сходится все до осталось пройти в обратном порядке. Далее я не понял, откуда добавилось еще 7 звездочек и откуда берется обратный порядок. Но в итоге их почему-то 5. Я верно понял, что программа заканчивает выполнение при N=48?

 Отправлено: 27.07.19 15:44. Заголовок: Ответ

Здравствуйте, Eugeny1984!

Вы пишете:

цитата:

Я верно понял, что программа заканчивает выполнение при N=48?

Нет. При n = - 5.

цитата:

Далее я не понял, откуда добавилось еще 7 звездочек и откуда берется обратный порядок. Но в итоге их почему-то 5.

Нет, не 5, а 4.

Запись F(51) = F(48) означает, что процедура F при n = 51 вызывает процедуру F при n = 48.

Запись G(40) = * F(39) означает, что процедура G при n = 40 печатает ОДНУ звездочку и вызывает процедуру F при n = 39.

F(51) = F(48)
F(48) = F(45)
F(45) = G(40)
G(40) = * F(39)
F(39) = F(36)
F(36) = F(33)
F(33) = F(30)
F(30) = G(25)
G(25) = * F(24)
F(24) = F(21)
F(21) = F(18)
F(18) = F(15)
F(15) = G(10)
G(10) = * F(9)
F(9) = F(6)
F(6) = F(3)
F(3) = F(0)
F(0) = G(-5)
G(-5) = *

Из последней строчки видно, что G(-5) просто печатает ОДНУ звездочку и никаких процедур уже не вызывает.

Значит, G(-5) - это просто печать ОДНОЙ звездочки.

Ранее было найдено, что F(0) = G(-5). Подставим G(-5).
F(0) = G(-5) = *
Значит, F(0) - это просто печать ОДНОЙ звездочки.

G(-5) = *
F(0) = G(-5) = *
F(3) = F(0) = *
F(6) = F(3) = *
F(9) = F(6) = *
G(10) = * F(9) = * * (G(10) печатает 2 звездочки. Можете проверить на компьютере.)
F(15) = G(10) = * *
F(18) = F(15) = * *
F(21) = F(18) = * *
F(24) = F(21) = * *
G(25) = * F(24) = * * * (1 звездочка плюс 2 звездочки = 3 звездочки)
F(30) = G(25) = * * *
F(33) = F(30) = * * *
F(36) = F(33) = * * *
F(39) = F(36) = * * *
G(40) = * F(39) = * * * *
F(45) = G(40) = * * * *
F(48) = F(45) = * * * *
F(51) = F(48) = * * * *

Таким образом, при вызове F(51) будет напечатано 4 звездочки.

Если все-таки что-то непонятно, можно обратить внимание на то, что ОДНА звездочка печатается при КАЖДОМ вызове процедуры G.

Таких вызовов 4: G(40), G(25), G(10), G(-5).

Соответственно, будет напечатано 4 звездочки.

Полный разбор, приведенный выше, весьма полезен при решении задач на рекурсивные алгоритмы (смотрите, например, здесь, здесь и разбор других задач задания 11 на этом форуме).

 Отправлено: 27.07.19 16:44. Заголовок: polyakovss пишет: ..

polyakovss пишет:
[quote]` Cспасибо за разъяснение! Теперь понятно)