"Oyunu Ortadan Kaldırmak" için verimli bir algoritma oluşturma
Bu Eleme Oyunu problemini çözüyordum .
Önce kaba kuvvetle denedim;
- mesafe ile baştan ortadan kaldırılan sayılar $2$ (yani bir sonraki öğeden sonraki öğe)
- listeyi tersine çevirdi
- mesafe ile baştan ortadan kaldırılan sayılar $2$
- listeyi tersine çevirdi ...
Son olarak, kalan son öğeyi döndürdü. Ancak, şaşırtıcı olmayan bir şekilde, bu "Zaman Sınırı Aşıldı" yı yükseltti.
İşte bunun için Python kodu:
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]
Sonra daha iyi bir çözüm aradım ve şunları buldum:
def lastRemaining(n: int) -> int:
if n == 1: return 1
return (n//2 - lastRemaining(n//2) + 1) * 2
ve çalışıyor. Bu matematiksel olarak şöyle yazılmıştır$$ 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} $$ Bunu bazı değerler için doğruladım $n$. Yine de, bu algoritmanın her durumda işe yaradığını kanıtlamak için yardıma ihtiyacım var.
Herhangi bir yardım takdir edilmektedir.
Yanıtlar
İlk durum $n=1$açıktır. İkinci durum için, yaptığınız şeyin temelde ilk yinelemeyi çalıştırmak ve kalan sorun üzerinde sorunu çözmek olduğunu unutmayın ($2, 4, 6, ... 2⌊n/2⌋$) - iyi, neredeyse. Ters sırayla yaparsınız, bu yüzden$⌊n/2⌋-f(⌊n/2⌋)+1$ onun yerine $f(⌊n/2⌋)$Burada, orijinal soruna eşdeğer olacak şekilde, değerini değil, "son sayı" nın sırasını döndürdüğünüzü unutmayın. Bu nedenle ile çarpıyoruz$2$ sonunda sırasını bildiğimiz "son sayı" nın değerini almak için.