Форум » Форум, сайт и общие вопросы » задача из ЕГЭ паскаль, при каком условии завершается? » Ответить
задача из ЕГЭ паскаль, при каком условии завершается?
Eugeny1984: Добрый день! Программа печатает звездочку (*) 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.
Ответов - 4
polyakovss: Здравствуйте, 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) = ****
Eugeny1984: polyakovss пишет: У меня сходится все до осталось пройти в обратном порядке. Далее я не понял, откуда добавилось еще 7 звездочек и откуда берется обратный порядок. Но в итоге их почему-то 5. Я верно понял, что программа заканчивает выполнение при N=48?
polyakovss: Здравствуйте, 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 на этом форуме).
Eugeny1984: polyakovss пишет: Cспасибо за разъяснение! Теперь понятно)
полная версия страницы