“게임 제거”를위한 효율적인 알고리즘 구축

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$ 마지막에 우리가 순서를 알고있는 "마지막 숫자"의 값을 얻기 위해.