“게임 제거”를위한 효율적인 알고리즘 구축
이 제거 게임 문제를 해결하고있었습니다.
첫째, 나는 무차별 대입으로 시도했습니다.
- 거리에서 처음부터 제거 된 숫자 $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$ 마지막에 우리가 순서를 알고있는 "마지막 숫자"의 값을 얻기 위해.