Nth Tribonacci Number
Görev tanımı
Problem
Tribonacci dizisi T(0) = 0, T(1) = 1 ve T(2) = 1 ile başlıyor ve sonraki her terim kendisinden önceki üçünün toplamı: T(n) = T(n - 1) + T(n - 2) + T(n - 3). 0 ≤ n ≤ 37 olan n verildiğinde T(n)'i döndür.
Örnekler
Input: n = 4
Output: 4
Neden: dizi 0, 1, 1, 2, 4 diye gidiyor
Input: n = 25
Output: 1389537
Input: n = 0
Output: 0
Neden: edge case: ilk başlangıç değeri
İpuçları
0 / 3
Tanım zaten özyinelemeli bir fonksiyon. n = 6 için çağrı ağacını çiz ve T(3)'ün kaç kez hesaplandığını say.
Her çağrı üç yöne dallanır, bu yüzden düz özyineleme yaklaşık 1,84 üzeri n çağrı yapar. Her değer yalnız hemen önündeki üç değere bağlı.
Son üç terimi üç değişkende tut ve onları n kez ileri kaydır: yeni üçlü eski ikinci, eski üçüncü ve üçünün toplamıdır.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- 0 ≤ n ≤ 37
Çözüm
Özyinelemeli tanım doğrudur ama aynı terimleri tekrar tekrar hesaplar; tıpkı dersteki saf Fibonacci gibi, yalnız daha kötü, çünkü her çağrı iki yerine üç yeni çağrı doğurur. Memoization (sonuçları hafızaya alma) bunu düzeltirdi, ama bağımlılık o kadar kısa ki üç sayının ötesinde cache'lenecek hiçbir şey yok. Döngü T(i), T(i + 1) ve T(i + 2)'yi tutar ve pencereyi iterasyon başına bir adım kaydırır; böylece n adımdan sonra penceredeki ilk değer T(n) olur. Zaman O(n), alan O(1); 37'ye kadar n de cevabı 32 bitlik bir tam sayının içinde tutar.
def tribonacci(n):
a, b, c = 0, 1, 1 # T(0), T(1), T(2)
for _ in range(n):
a, b, c = b, c, a + b + c # slide the window one term forward
return a
print(tribonacci(4)) # -> 4
print(tribonacci(25)) # -> 1389537
print(tribonacci(0)) # -> 0Kodda değil de fikirde mi takıldın? Faktöriyel ve Fibonacci bunu anlatıyor.