Создание эффективного алгоритма «Исключение игры»
Я решал эту проблему с игрой на выбывание.
Сначала я попробовал перебором;
- исключенные числа с самого начала с расстояния $2$ (т.е. элемент после следующего)
- перевернул список
- исключенные числа с самого начала с расстоянием $2$
- перевернул список ...
Наконец, вернул последний оставшийся элемент. Однако неудивительно, что это подняло «Превышен лимит времени».
Вот код Python для этого:
def lastRemaining(n: int) -> int:
nums = [i for i in range(1, n + 1)]
l = len(nums)
while l != 1:
for i in range(0, len(nums), 1):
if i < len(nums):
nums.remove(nums[i])
l -= 1
nums.reverse()
return nums[0]
Затем я поискал лучшее решение и нашел следующее:
def lastRemaining(n: int) -> int:
if n == 1: return 1
return (n//2 - lastRemaining(n//2) + 1) * 2
и это работает. Математически это записывается как$$ f(n) = \begin{cases} 1, \text{ if } n=1, \\ 2\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor - f\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor\right) + 1\right), \text{ otherwise } \end{cases} $$ Я проверил это для некоторых значений $n$. Тем не менее, мне нужна помощь, чтобы доказать, что этот алгоритм работает во всех случаях.
Любая помощь приветствуется.
Ответы
Первый случай $n=1$очевидно. Во втором случае обратите внимание, что вы в основном выполняете первую итерацию и решаете проблему на оставшейся части (т.е.$2, 4, 6, ... 2⌊n/2⌋$) - Ну, почти. Вы делаете это в обратном порядке, поэтому у вас$⌊n/2⌋-f(⌊n/2⌋)+1$ вместо $f(⌊n/2⌋)$Здесь обратите внимание, что вы фактически возвращаете порядок «последнего числа», а не его значение, что было бы эквивалентно в исходной задаче. Поэтому умножаем на$2$ в конце, чтобы получить значение «последнего числа», порядок которого мы знаем.