Pascal üçgeninin bir satırı
Görev tanımı
Problem
Bir olasılık kütüphanesinin, verilen bir k için C(k, 0)'dan C(k, k)'ya kadar her binom katsayısına ihtiyacı var; bu, 0. satırdan sayarak Pascal üçgeninin k. satırıdır. 0 ile 1.000 arasında bir k verildiğinde o satırı tam sayılardan oluşan bir liste olarak döndür. Onu üstündeki satırları kurmadan O(k) aritmetik adımda kur.
Örnekler
Input: k = 3
Output: [1, 3, 3, 1]
Input: k = 5
Output: [1, 5, 10, 10, 5, 1]
Input: k = 0
Output: [1]
Neden: edge case: 0. satır tek bir 1 tutar
İpuçları
0 / 3
k. satırın j. elemanı C(k, j), yani k öğeden j tanesini seçmenin yolu sayısı.
C(k, j)'den C(k, j + 1)'e geçmek k! / (j! (k - j)!) formülünü üstte bir, altta bir çarpanla değiştirir.
C(k, j + 1) = C(k, j) × (k - j) / (j + 1). Önce çarp, sonra // ile böl; bölme her zaman tamdır.
- Hedef zaman
- O(k)
- Hedef alan
- O(k)
Kısıtlar
- 0 ≤ k ≤ 1000
Çözüm
k. satırın her elemanı bir binom katsayısıdır ve komşu katsayılar basit bir oranla farklılaşır: C(k, j + 1) = C(k, j) × (k - j) / (j + 1). C(k, 0) = 1'den başlayınca sonraki her eleman bir çarpma ve bir bölmeye mal olur. Bölmeden önce çarpmak aritmetiği kesin tutar, çünkü C(k, j) × (k - j), C(k, j + 1) × (j + 1)'e eşittir ve bu yüzden her zaman j + 1'in bir katıdır; Python'un büyük tam sayıları da 1.000. satırın ortasının bile asla taşmaması demektir. Bu, O(k²) toplama gerektirecek olan üstteki k satırı kurmaktan kaçınır. Satır O(k) aritmetik adım ve çıktı için O(k) alan alır.
def pascal_row(k):
row = [1]
for j in range(k):
row.append(row[-1] * (k - j) // (j + 1)) # exact: C(k, j+1) * (j+1)
return row
print(pascal_row(3)) # -> [1, 3, 3, 1]
print(pascal_row(5)) # -> [1, 5, 10, 10, 5, 1]
print(pascal_row(0)) # -> [1]Kodda değil de fikirde mi takıldın? Permütasyon ve kombinasyon bunu anlatıyor.