Pascal's Triangle
Pascal üçgeninde ilk satır [1] şeklindedir. Sonraki her satır bir eleman daha uzundur, 1 ile başlar ve biter; aradaki her eleman ise hemen üstündeki iki elemanın toplamıdır. Bir tamsayı olan numRows verilir. Üçgenin ilk numRows satırını, en üst satır önce olacak şekilde ve her satır bir tamsayı dizisi olarak döndür.
Fonksiyon
- numRowsinteger
- üçgenin kaç satırının oluşturulacağı
- Döndürürinteger-2d-array
- ilk numRows satır, en üst satır önce
Kısıtlar
1 ≤ numRows ≤ 30- İlk 30 satırdaki her değer, 32 bitlik işaretli bir tamsayıya sığar. En büyük değer 77558760'tır ve 30. satırın ortasındadır.
Ö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ş, üstündeki iki girdiyi toplar. Dördüncü satırda 3 = 1 + 2 ve 3 = 2 + 1. Beşinci satırda 4 = 1 + 3, 6 = 3 + 3 ve 4 = 3 + 1.
- Girdi
- numRows = 1
- Çıktı
- [[1]]
- Açıklama
- Tek bir satırla üçgen yalnızca tepesinden,
[1], oluşur.
Gönderirken +13 gizli test
Ek soru
Yukarıdaki satırları tutmak yerine, satır satır yerinde güncelleyerek tek bir dizide yalnızca son satırı oluşturabilir misin? İç döngü hangi yönde çalışmalı 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 öğeleri nelerdir?Her iç girdi için yalnızca doğrudan üstündeki satırdan iki değer gerekir. Satırları sırayla oluşturursan, o satıra ihtiyaç duymadan önce 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
Üçgeni tanımlayan kural özyinelemelidir: Bir öğe, üst sıradaki iki öğenin toplamıdır. Bu kuralı her öğe için baştan değerlendirmek aynı değerleri tekrar tekrar hesaplar ve iş miktarı her sırada iki katına çıkar. Döndürmeniz istenen sıralar, bu daha küçük problemlerin kaydedilmiş yanıtlarıdır; bu nedenle üçgeni yukarıdan aşağıya oluşturun ve her sırayı, ondan önce oluşturduğunuz sıradan alın.
Her girdiyi özyinelemeli olarak hesapla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Satırları ve bir satırın içindeki konumları 0'dan başlayarak numaralandırın. Üçgenin tanımı bir fonksiyona dönüşür: entry(row, col), col 0 olduğunda veya row'a eşit olduğunda, yani iki kenarda 1'dir; diğer durumlarda ise entry(row-1, col-1) + entry(row-1, col) değerini alır. Her satırın her konumu için bu fonksiyonu çağırdığınızda üçgeni elde edersiniz. Bu doğrudur çünkü tanımın kelimesi kelimesine kendisidir.
Sorun, yaptığı çağrıların sayısıdır. Özyineleme yalnızca kenarlarda durur ve burada 1 döndürür; bu yüzden değeri v olan bir girdiyi hesaplamak yaklaşık 2v çağrı gerektirir. r satırının toplamı 2^r'ye kadar çıkar; dolayısıyla 30 satırın tamamı yaklaşık 2^31 çağrı gerektirir; bu da iki milyardan fazladır. Aynı küçük girdiler milyonlarca kez yeniden hesaplanır: entry(2, 1), altındaki neredeyse her değerin hesaplanmasında yer alı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 hercoldeğeri iç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
Özyinelemeli sürüm, önceki satırlardaki girdileri istemeye devam eder ve zaten bu satırları oluşturuyorsun. Bu yüzden satırları sırayla, yukarıdan aşağıya hesapla ve r satırını doldururken ihtiyacın olan değerleri doğrudan zaten oluşturulmuş olan r-1 satırından oku. Böylece her girdi tek bir toplama gerektirir. Bu, dinamik programlamanın en yalın hâlidir: daha küçük problemlerin yanıtlarını içeren tablo, çıktının kendisidir.
r satırını r + 1 tane 1 ile başlat; böylece iki kenar da ayarlanır. Ardından 1'den r-1'e kadar her iç konum c için değeri above[c-1] + above[c] olarak ayarla. 0 ve 1 numaralı satırların iç konumu olmadığından, özel bir durum gerekmeksizin [1] ve [1, 1] olarak kalırlar.
Üçgenin 1 + 2 + ... + n, yani yaklaşık n²/2 girdisi vardır ve her biri sabit zaman aldığından, işlem miktarı O(n²)'dir. Zaten döndürmen gereken çıktı dışında, bu yöntem ek bellek gerektirmez. numRows = 30 için bu, iki milyar çağrı yerine 465 girdi demektir.
Algoritma
- Boş bir satır listesiyle başla.
- 0'dan
numRows-1'e kadar herrowiçinrow + 1tane 1 oluştur. - 1'den
row-1'e kadar hercoliçin, onu ö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
Döngüler kısa olduğundan, hatalar sınırlarla ve ilk satırlarla ilgilidir.
numRows + 1satır döndürmek. Satırları 0'dan numaralandırırsan, ihtiyacın olan son satırnumRows-1olur.- İç döngüyü kenarlar üzerinde çalıştırmak. 0 konumunun sol üst öğesi,
rowkonumunun ise sağ üst öğesi yoktur; bu nedenle buradaabove[col-1]veyaabove[col]okumak sınırların dışına çıkar. Yalnızca 1 ilerow-1arasındaki konumları doldur. - Küçük satırlarda hata veren bir aralık yazmak. Swift'te
1..<row,row0 olduğunda çöker; R'de2:(row-1),row2 olduğunda 1'e kadar geri sayar. Bunları bir koşulla koru ya da iç konumları birlerden başlat; böylece 0 ve 1. satırlar için döngü gerekmez. - Değerleri faktöriyellerle hesaplamak.
C(29, 14)bir int içine sığar, ancak29!64 bitlik bir tamsayıda bile taşmaya neden olur; bu nedenle faktöriyellere dayalı bir formül alt satırlarda yanlış sayılar yazdırır. - Her satır için aynı diziyi yeniden kullanmak. Her seferinde aynı diziyi eklersen ve sonra onu değiştirirsen, yanıttaki tüm satırlar son satırla aynı olur.
Sıkça sorulan sorular4
Pascal üçgenini oluşturmanın zaman karmaşıklığı nedir?
Her satırı üstündeki satırdan oluşturmak, n satır için O(n²) zaman alır; çünkü üçgende yaklaşık n²/2 giriş vardır ve her biri tek bir toplama işlemidir. Bu en uygun süredir, çünkü çıktının her girişini yazmanız gerekir. Çıktı dışında O(1) ek alan kullanır.
Pascal üçgeni binom katsayılarıyla nasıl ilişkilidir?
0'dan başlayarak sayıldığında, r satırının k numaralı girdisi, k öğeyi r öğe arasından seçmenin yol sayısı olan binom katsayısı C(r, k)'dir. Her girdinin üstündeki iki girdinin toplamı olması kuralı, C(r, k) = C(r-1, k-1) + C(r-1, k) özdeşliğidir. r satırının toplamının 2^r olmasının nedeni de budur.
Üstündeki satırları oluşturmadan tek bir satırı hesaplayabilir misin?
Evet. 1 ile başlayın ve sonraki her değeri bir önceki değerden elde edin: C(r, k) = C(r, k-1) × (r-k+1) / k. Bölmeden önce çarpın; böylece bölme tam olur ve çarpım için 64 bitlik bir tamsayı kullanın. Böylece r satırı O(r) zamanda ve başka hiçbir satır hesaplanmadan elde edilir.
Pascal üçgeni neden bir dinamik programlama problemidir?
Her bir giriş, kendisinden önceki iki küçük alt probleme bağlıdır ve bu alt problemler büyük ölçüde örtüşür: yalın özyineleme, bunları tekrar tekrar hesaplar. Satırları sırayla oluşturmak her alt problemi bir kez saklar ve yeniden kullanır; böylece üstel işlem miktarını O(n²) düzeyine indirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def generate(numRows):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
numRows = 5
Beklenen
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]