Pascal's Triangle
Pascal üçgeninde ilk satır [1]'dir. Sonraki her satır bir eleman daha uzundur, 1 ile başlar ve biter; aradaki her eleman ise doğrudan üstündeki iki elemanın toplamıdır. Bir tamsayı olan numRows verilir. Üçgenin ilk numRows satırını, en üstteki satır ilk sırada olacak şekilde ve her satır bir tamsayı dizisi olarak döndür.
Fonksiyon
- numRowsinteger
- üçgenin kaç satırını oluşturmak gerektiği
- Döndürürinteger-2d-array
- ilk numRows satır, önce en üstteki satır
Kısıtlar
1 ≤ numRows ≤ 30- İlk 30 satırın her birindeki tüm değerler 32 bitlik işaretli bir tam sayıya sığar. En büyüğü, 30. satırın ortasındaki 77558760 değeridir.
Örnekler
- Girdi
- numRows = 5
- Çıktı
- [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
- Açıklama
- Her iç giriş, üzerindeki iki girişi toplar. Dördüncü satır: 3 = 1 + 2 ve 3 = 2 + 1. Beşinci satır: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.
- Girdi
- numRows = 1
- Çıktı
- [[1]]
- Açıklama
- Tek bir satırla üçgen yalnızca tepesinden,
[1]oluşur.
Ek soru
Yalnızca bir dizi tutup onu satır satır yerinde güncelleyebilir misin? İç döngü hangi yönde ilerlemeli ve neden?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
0. satır
[1], 1. satır ise[1, 1].rsatırı ne kadar uzun ve ilk ve son elemanları nelerdir?Her iç girdinin yalnızca hemen üstündeki satırdan iki değere ihtiyacı vardır. Satırları sırayla oluşturursan, ihtiyaç duymadan önce o satır her zaman tamamlanmış olur.
Her yeni satıra tüm değerleri 1 olarak başlayın. Ardından, her iç konum
ciçin önceki satırınc-1veckonumlarını toplayın. Satırı ekleyin ve devam edin.
Çözüm
Bir öğe, üstündeki satırdaki iki öğenin toplamıdır. Bu kuralı her öğe için baştan değerlendirmek aynı değerleri yeniden hesaplar ve işlem her satırda iki katına çıkar. Döndürdüğün satırlar, bu daha küçük problemlerin saklanan yanıtlarıdır; bu yüzden üçgeni yukarıdan aşağıya, her satırı bir öncekinin üzerine kurarak oluştur.
Her girdiyi özyinelemeli olarak hesapla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Satırları ve konumları 0'dan başlayarak numaralandırın. Tanım bir fonksiyona dönüşür: entry(row, col), kenarlarda 1'dir; burada col 0 veya row değerindedir. Diğer durumlarda entry(row-1, col-1) + entry(row-1, col) olur. Tanımın kendisi olduğu için doğrudur.
Özyineleme yalnızca kenarlarda durur ve bu kenarlar 1 döndürür; bu nedenle değeri v olan bir giriş için yaklaşık 2v çağrı gerekir. r satırının toplamı en fazla 2^r olur; bu yüzden 30 satır için yaklaşık 2^31 çağrı gerekir; bu sayı iki milyardan fazladır.
Algoritma
entry(row, col)yaz:col0 ise veyacol,row'a eşitse 1 döndür.- Aksi hâlde
entry(row-1, col-1) + entry(row-1, col)döndür. - 0'dan
numRows-1'e kadar herrowiçin, 0'danrow'a kadar hercoliçinentry(row, col)değerini topla. - Satırların listesini döndür.
def pascalEntry(row, col):
if col == 0 or col == row:
return 1 # the edges of the triangle
return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)
def generate(numRows):
triangle = []
for row in range(numRows):
triangle.append([pascalEntry(row, col) for col in range(row + 1)])
return triangleHer satırı bir üstündeki satırdan oluşturun
Sezgi
Özyineleme, önceki satırlardaki girdileri istemeye devam eder ve sen yine de bu satırları oluşturursun. Bu yüzden satırları yukarıdan aşağıya hesapla ve r satırını doldururken, zaten hesaplanmış olan r-1 satırını oku. Her girdi bir toplama işlemi gerektirir: daha küçük yanıtların tablosu çıktının kendisidir.
Her satıra r + 1 tane bir ile başlamak iki kenarı da belirler; bu nedenle iç konumu olmayan 0. ve 1. satırlar için özel bir duruma gerek yoktur. Üçgende 1 + 2 + ... + n, yani yaklaşık n²/2 girdi bulunur; dolayısıyla çıktı dışında bellek kullanmadan yapılan işlem O(n²) olur: 30 satır için iki milyar çağrı yerine 465 girdi.
Algoritma
- Boş satırlar listesiyle başla.
- 0'dan
numRows-1değerine kadar herrowiçinrow + 1tane 1 oluştur. - 1'den
row-1değerine kadar hercoliçin, değerini önceki satırdakicol-1vecolkonumlarının toplamı olarak ayarla. - Satırı ekle ve devam et. Listeyi döndür.
def generate(numRows):
triangle = [[1]]
for row in range(1, numRows):
above = triangle[-1]
values = [1] * (row + 1) # both edges are 1
for col in range(1, row):
values[col] = above[col - 1] + above[col]
triangle.append(values)
return triangle
Tuzaklar ve uç durumlar
numRows + 1satır döndürmek. 0'dan numaralandırıldığında, ihtiyacın olan son satırnumRows-1olur.- İç döngüyü kenarlar üzerinde çalıştırmak. 0 konumunun sol ebeveyni,
rowkonumunun ise sağ ebeveyni yoktur; bu nedenle bunları okumak sınırların dışına çıkar. - Küçük satırlarda hata veren bir aralık kullanmak. Swift'te
1..<row,row0 olduğunda çöker; R'de2:(row-1),row2 olduğunda 1'e kadar geri sayar. - Girişleri faktöriyellerle hesaplamak.
C(29, 14)bir int içine sığar, ancak29!64 bitlik bir tam sayıda bile taşmaya neden olur. - Her satır için aynı diziyi ekleyip sonra değiştirmek. Yanıttaki her satır son satırla aynı olur.
Sıkça sorulan sorular3
Pascal üçgenini oluşturmanın zaman karmaşıklığı nedir?
n satır için O(n²): üçgende yaklaşık n²/2 eleman vardır ve her biri bir toplama işlemidir. Bu en iyi çözümdür, çünkü çıktının her elemanını yazmanız gerekir. Çıktı dışında kullanılan ek alan O(1)'dir.
Pascal üçgeni binom katsayılarıyla nasıl ilişkilidir?
r satırının 0'dan başlayarak sayılan k. elemanı, r öğe arasından k öğe seçmenin yol sayısı olan C(r, k)'dir. Toplama kuralı, C(r, k) = C(r-1, k-1) + C(r-1, k) özdeşliğidir ve r. satırın toplamı, r öğenin alt kümelerinin sayısı olan 2^r'dir.
Üstündeki satırları oluşturmadan tek bir satırı hesaplayabilir misin?
Evet. 1 ile başlayın ve sonraki her girdiyi bir öncekinden elde edin: C(r, k) = C(r, k-1) × (r-k+1) / k. Bölme işleminin tam sonuç vermesi için önce çarpın ve çarpımda 64 bitlik bir tamsayı kullanın. Böylece r satırı O(r) zaman alır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def generate(numRows):
# Kodu buraya yazınTest #1
Test #2
Argüman
numRows = 5
Beklenen Çıktı
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]