Приветствую вас, друзья! Сегодня в беседе группы Physics.Math.Code один из участников задал интересную задачу. Сама по себе задача является относительно типовой в контексте информатики и программирования. Но в задаче было задано условию «решить через рекурсию». Именно это условие вызывает сложности у большинства учащихся. Да и в целом, рекурсия всегда сложна.
Задача
Царевна-лягушка съедает на 20% комаров больше, чем в предыдущий день и еще 2 комара. Написать программу, определяющую, через сколько дней количество съеденных комаров превысит 100, если в первый день было съедено 12 комаров (написать через рекурсию).
Решение
Способ 1. Проще всего данную задачу решить через цикл. Внутрь цикла в качестве аргумента можно передать начальное значение комаров, которое лягушка съела в первый день. Внутри цикла можно завести переменную days, которая будет отвечать за количество дней, которое понадобится лягушке, чтобы съесть комаров в количестве более заданного числа (в нашем случае это число 100). Минимум лягушке понадобится 1 день (для другой задачи начальный условия можно изменить). Тогда цикл while с предусловием будет после каждой итерации проверять «не превысило ли количество комаров нужной границы». Пока условие number_of_mosquitoes < 100 будет верно, мы будем изменять количество съеденных комаров number_of_mosquitoes = 1.2 * number_of_mosquitoes + 2 и инкриминировать (от англ. increment «увеличение») счетчик дней ++days. После отработки цикла while в переменной days будет лежать нужное нам целое число дней.
Способ 2. Рекурсивный способ немного посложнее с точки зрения логики. Но давайте попробуем разобраться и в нём. Сложность рекурсии всегда заключается в том, что сама структура алгоритма повторяет сама себя. Поэтому бывает сложно уложить в голове структуру формул, фрактально повторяющих самих себя. В качестве аргументов можно передать начальное количество комаров ( для нашего случая 12) и начальное количество дней (для нашего случая 1). Ключевым моментом в рекурсии является код, который будет отлавливать условия выхода. На мой взгляд, именно с него всегда стоит начинать. Потому что, если его не предусмотреть или спроектировать неверно, то программа быстро забьет стек вызовов и ничего полезного не сделает. Количество комаров number_of_mosquitoes мы должны передавать из одного вызова в другой. Каждый раз в рекурсивном коде нужно проверить превышение верхней границы ( 100 комаров в нашей задаче ). Если превышение есть, то вернуть текущее количество дней. Количество дней (переменная days ) тоже нужно передавать из одного вызова в другой (если не делать эту переменную глобальной, что является плохим тоном программирования ). В противном случае (ветка else), если количество комаров не превысило, то мы пересчитываем общее количество комаров, увеличиваем счетчик дней и возвращаем результат работы функции с уже обновленными параметрами. Рано или поздно у нас дойдет до верхней ветки if () , и тогда уже вернется готовое число. Прикрепляю код, который реализует описанное выше.
После запуска кода, обе функцию выдают результат: 10 дней. То есть 10 дней понадобится лягушке, чтобы съесть более 100 комаров, если в первый день она съест 12, а в каждый следующий будет есть на 20 % больше и еще 2 комаров сверху.
Полный код программы:
Что ж, результат вполне реалистичный. Да и обе функции решают задачу одинаково. Но что если хочется ещё как-то проверить? Тогда остается только один способ: взять в руки черновик, карандаш и воспользоваться старым дедовским способом решения задачи на листочке :)
Понравился разбор задачи ? Поставьте лайк, подпишитесь на канал! Вам не сложно, а мне очень приятно :)
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в telegram