Yarıya indir ya da bir çıkar
Görev tanımı
Problem
Sıfır ya da daha büyük bir n tam sayısından başla. Bir adımda çiftse onu yarıya indir, tekse bir çıkar. Sıfıra ulaşmanın kaç adım sürdüğünü döndür. Sayı 2 üzeri 1000 kadar büyük olabilir, bu yüzden adım başına bir özyinelemeli çağrı yapan bir çözüm Python'un varsayılan özyineleme (recursion) sınırını aşar.
Örnekler
Input: n = 14
Output: 6
Neden: 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0
Input: n = 2 ** 1000
Output: 1001
Neden: 1000 yarıya indirme 1'e, bir çıkarma da 0'a ulaşır
Input: n = 0
Output: 0
Neden: edge case: zaten sıfırda, yani hiç adım atılmaz
İpuçları
0 / 3
Doğal özyinelemeli cevap, bir artı sonraki sayının cevabıdır. En büyük girdi için call stack'in ne kadar derine indiğini say.
Özyinelemeyi adım sayacı fazladan bir argüman olarak yanında taşınacak şekilde yeniden yaz. Artık özyinelemeli çağrı fonksiyonun yaptığı en son şey.
Son eylem olan bir çağrının yerine argümanları yeniden atayıp en üste geri atlamak konabilir: n sıfır olana kadar n'i ve sayacı güncelleyen bir döngü.
- Hedef zaman
- O(log n)
- Hedef alan
- O(1)
Kısıtlar
- 0 ≤ n ≤ 2¹⁰⁰⁰
Çözüm
Bir biriktiriciyle özyineleme bir tail call'a dönüşür: n için cevap, sayaç bir artırılmış halde sonraki sayının cevabıdır ve çağrı döndükten sonra yapılacak hiçbir şey kalmaz. Python tail call'ları kendiliğinden kaldırmaz; bu yüzden çağrı n'i ve sayacı yeniden atayan bir döngüye çevrilir ve stack hiç büyümez. Adım sayısının sıfırın üstündeki n için kapalı bir formu da var: ilkinden sonraki her ikili basamak için bir adım, artı 1 olan her bit için bir adım. Zaman O(log n) adım, sayının kendisi dışında alan O(1).
def steps_to_zero(n):
# tail-recursive shape: steps(n, done) = done if n == 0 else steps(next n, done + 1)
done = 0
while n: # the tail call, as a loop
n = n // 2 if n % 2 == 0 else n - 1
done += 1
return done
print(steps_to_zero(14)) # -> 6
print(steps_to_zero(2 ** 1000)) # -> 1001
print(steps_to_zero(0)) # -> 0Kodda değil de fikirde mi takıldın? Tail call'lar ve döngüler bunu anlatıyor.