Эффективное решение задач с помощью рекурсии: пример из теории игр
Представьте, что вы играете с другом в игру, в которой вы по очереди выбираете числа из списка. На каждом ходу вы можете выбрать один номер в начале или в конце списка, и этот номер будет удален из списка. Игра продолжается до тех пор, пока список не станет пустым. Ваша цель состоит в том, чтобы максимизировать общую сумму чисел, которые вы выбрали.
Чтобы решить эту проблему, мы можем использовать технику под названием «рекурсия». Рекурсия — это способ решения проблемы путем разбиения ее на все более мелкие части до тех пор, пока она не станет достаточно простой для непосредственного решения.
Рекурсия — это метод программирования, который включает определение функции в терминах самой себя. Это может быть мощный инструмент для решения задач оптимизации, поскольку он позволяет создавать алгоритмы, которые разбивают проблему на более мелкие подзадачи, решают эти подзадачи, а затем объединяют решения подзадач, чтобы найти решение исходной проблемы. Этот процесс можно повторять до тех пор, пока проблема не станет достаточно малой, чтобы ее можно было легко решить. Рекурсия может быть эффективным способом решения проблем оптимизации, поскольку она позволяет повторно использовать код и часто может привести к более кратким и удобочитаемым решениям. Однако важно гарантировать, что рекурсия в какой-то момент завершится, поскольку бесконечная рекурсия может привести к ошибкам времени выполнения и другим проблемам.
В этом случае мы можем использовать рекурсию, чтобы рассмотреть оба варианта (выбор из начала или конца списка) и выбрать тот, который приводит к максимальному общему баллу. Для этого мы напишем функцию optimize_output, которая принимает список чисел в качестве входных данных и возвращает максимальный общий балл, который можно получить, выбрав числа оптимальным образом.
Функция optimise_output работает, рассматривая три разных случая:
- Если в списке только один элемент, мы просто возвращаем этот элемент.
- Если в списке два элемента, мы возвращаем максимум из двух.
- Если в списке более двух элементов, нам нужно рассмотреть оба варианта: выбор с начала или с конца списка. Для этого мы используем рекурсивный вызов optimize_output для вычисления оптимального значения для обоих вариантов. Затем мы возвращаем максимум из двух.
def optimize_output(numbers):
# base case: if the list has only one element, return it
if len(numbers) == 1:
return numbers[0]
# if the list has two elements, return the maximum of the two
if len(numbers) == 2:
return max(numbers[0], numbers[1])
# if the list has more than two elements, we need to consider both
# options: picking from the beginning or the end of the list
# we will use a recursive call to compute the optimal value for both
# options and return the maximum of the two
return max(numbers[0] + min(optimize_output(numbers[2:]), optimize_output(numbers[1:-1])),
numbers[-1] + min(optimize_output(numbers[1:-1]), optimize_output(numbers[:-2])))
Используя этот подход, мы можем решить проблему, выполнив серию рекурсивных вызовов optimize_output, начиная с исходного списка чисел. Функция будет продолжать выполнять рекурсивные вызовы, пока не достигнет одного из базовых случаев (когда список содержит только один или два элемента), после чего она вернет оптимальное значение.
Чтобы упростить использование функции optimize_output, мы можем написать вторую функцию с именем pick_number, которая принимает список чисел в качестве входных данных и возвращает число, которое нужно выбрать (либо с начала, либо с конца). список). Функция pick_number работает, вычисляя оптимальное значение для обоих вариантов (выбор из начала или конца списка) с помощью функцииOptimize_output, а затем возвращая вариант, который приводит к максимальному общему баллу.
def pick_number(numbers):
# base case: if the list has only one element, return it
if len(numbers) == 1:
return "BEGINNING"
# if the list has two elements, return the maximum of the two
if len(numbers) == 2:
return "BEGINNING" if numbers[0] > numbers[1] else "END"
# compute the optimal value for both options: picking from the beginning
# or the end of the list
beginning_option = numbers[0] + min(optimize_output(numbers[2:]), optimize_output(numbers[1:-1]))
end_option = numbers[-1] + min(optimize_output(numbers[1:-1]), optimize_output(numbers[:-2]))
# return the option that leads to the maximum total score
if beginning_option > end_option:
return "BEGINNING"
else:
return "END"
В качестве примера рассмотрим список [5, 6, 9, 7]. Если мы вызовем pick_number с этим списком в качестве входных данных, он вычислит оптимальное значение для обоих вариантов: выбор числа 5 в начале списка или выбор числа 7 в конце списка.
В этом случае оптимальное значение для начального варианта равно 5 + максимальное из оптимальных значений для подсписка [6, 9]. Ваш друг выберет 7, чтобы максимизировать свои шансы. Результат равен 5 + 9 = 14. Оптимальное значение для конечного варианта равно 7 + максимум оптимального значения для подсписка [5, 6]. Ваш друг выберет 7, чтобы максимизировать свои шансы. Результат равен 7 + 6 = 13.
Поскольку оптимальное значение для начального параметра (14) больше, чем оптимальное значение для конечного параметра (13), pick_number вернет число 5 (НАЧАЛО). Это оптимальный выбор, так как он приводит к максимальному общему количеству баллов (14) из всех возможных вариантов.
Одним из преимуществ использования этого подхода является то, что он относительно прост для понимания и реализации. Это также эффективно, поскольку рекурсивные вызовы могут повторно использовать ранее вычисленные результаты, что экономит время и позволяет избежать ненужных вычислений.
Однако у этого подхода есть и некоторые недостатки. Одна потенциальная проблема заключается в том, что функция может выполняться долго, если список чисел очень большой, так как ей нужно сделать много рекурсивных вызовов. Кроме того, этот подход требует много памяти для хранения промежуточных результатов рекурсивных вызовов, что может быть проблемой, если список чисел очень велик.
В целом, функции optimise_output и pick_number обеспечивают простое и эффективное решение проблемы выбора чисел из списка, чтобы максимизировать общий балл. Хотя у них есть некоторые ограничения, они являются полезными инструментами для решения проблем такого типа.
Узнайте больше об оптимизации с помощью Numbrail.
Numbrail — это оптимизационная головоломка, в которой игроки должны использовать стратегическое мышление и навыки оптимизации, чтобы набрать 61 очко в структурированной игровой среде. Игра предназначена для того, чтобы пробудить интерес к информатике и напомнить игрокам, что оптимизация является неотъемлемой частью повседневной жизни. Numbrail начинался как технический вопрос на собеседовании и превратился в сложную и захватывающую игру.
