Создание эффективного алгоритма «Исключение игры»

Aug 17 2020

Я решал эту проблему с игрой на выбывание.

Сначала я попробовал перебором;

  • исключенные числа с самого начала с расстояния $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$. Тем не менее, мне нужна помощь, чтобы доказать, что этот алгоритм работает во всех случаях.

Любая помощь приветствуется.

Ответы

1 Ekin Aug 17 2020 at 03:21

Первый случай $n=1$очевидно. Во втором случае обратите внимание, что вы в основном выполняете первую итерацию и решаете проблему на оставшейся части (т.е.$2, 4, 6, ... 2⌊n/2⌋$) - Ну, почти. Вы делаете это в обратном порядке, поэтому у вас$⌊n/2⌋-f(⌊n/2⌋)+1$ вместо $f(⌊n/2⌋)$Здесь обратите внимание, что вы фактически возвращаете порядок «последнего числа», а не его значение, что было бы эквивалентно в исходной задаче. Поэтому умножаем на$2$ в конце, чтобы получить значение «последнего числа», порядок которого мы знаем.