Pascal's Triangle

Q: ما التعقيد الزمني لإنشاء مثلث باسكال؟

O(n²) لـ n صفوف: يحتوي المثلث على نحو n²/2 من الخانات، وتتطلب كل خانة عملية جمع واحدة. وهذا هو الأمثل، إذ يجب كتابة كل خانة في الناتج. المساحة الإضافية، بخلاف الناتج، هي O(1) .

Q: ما علاقة مثلث باسكال بالمعاملات الثنائية؟

العنصر k من الصف r ، مع بدء العد من 0، هو C(r, k) ، أي عدد الطرق لاختيار k عناصر من بين r . قاعدة الجمع هي المتطابقة C(r, k) = C(r-1, k-1) + C(r-1, k) ، ومجموع عناصر الصف r يساوي 2^r ، وهو عدد المجموعات الجزئية لعناصر r .

Q: هل يمكنك حساب صف واحد دون إنشاء الصفوف التي تسبقه؟

نعم. ابدأ بـ 1 واحصل على كل حد تالٍ من الحد السابق: C(r, k) = C(r, k-1) × (r-k+1) / k . اضرب قبل القسمة لكي تكون القسمة تامة، واستخدم عددًا صحيحًا ذا 64 بت لحاصل الضرب. يستغرق الصف r حينها زمنًا قدره O(r) .

سهلالبرمجة الديناميكية

+10

في مثلث باسكال، الصف الأول هو [1]. يتكون كل صف لاحق من عنصر إضافي، ويبدأ وينتهي بالعدد 1، وكل عنصر بينهما هو مجموع العنصرين الواقعين فوقه مباشرةً. تحصل على عدد صحيح numRows. أعد أول numRows صفوف من المثلث، بدءًا من الصف العلوي، بحيث يكون كل صف مصفوفة من الأعداد الصحيحة.

الدالة

generate(numRows: integer) → integer-2d-array

numRowsinteger: كم عدد صفوف المثلث المطلوب بناؤها
تُرجعinteger-2d-array: أول numRows من الصفوف، بدءًا بالصف العلوي

القيود

1 ≤ numRows ≤ 30
كل قيمة في الصفوف الثلاثين الأولى تتسع في عدد صحيح موقّع من 32 بت. أكبرها هو 77558760، في منتصف الصف 30.

أمثلة

المدخلات: numRows = 5
المخرجات: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
الشرح: كل عنصر داخلي يجمع العددين اللذين فوقه. الصف الرابع: 3 = 1 + 2 و3 = 2 + 1. الصف الخامس: 4 = 1 + 3، 6 = 3 + 3، 4 = 3 + 1.

المدخلات: numRows = 1
المخرجات: [[1]]
الشرح: بوجود صف واحد، لا يتكوّن المثلث إلا من قمته، [1].

سؤال إضافي

هل يمكنك الاحتفاظ بمصفوفة واحدة فقط وتحديثها في مكانها، صفًا بعد صف؟ في أي اتجاه يجب أن تعمل الحلقة الداخلية، ولماذا؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

كل عنصر هو مجموع عنصرين في الصف الذي يعلوه. إن تطبيق هذه القاعدة من البداية لكل عنصر يعيد حساب القيم نفسها، ويتضاعف العمل مع كل صف. الصفوف التي تُرجعها هي الإجابات المخزّنة لتلك المسائل الأصغر، لذا ابنِ المثلث من الأعلى إلى الأسفل، بحيث يُبنى كل صف من الصف الذي يسبقه.

احسب كل مُدخل بشكل递归

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

رقّم الصفوف والمواضع بدءًا من 0. يصبح التعريف دالة: تكون entry(row, col) مساويةً لـ1 عند الحواف، حيث تكون col مساويةً لـ0 أو row، وإلا فتكون entry(row-1, col-1) + entry(row-1, col). وهذا صحيح لأنه التعريف نفسه.

يتوقف الاستدعاء الذاتي عند الحواف فقط، حيث تكون القيمة المرجعة 1، لذا يتطلب إدخال قيمته v نحو 2v استدعاءً. يصل مجموع عناصر الصف r إلى 2^r، لذا يتطلب حساب 30 صفًا نحو 2^31 استدعاءً، أي أكثر من ملياري استدعاء.

الخوارزمية

اكتب entry(row, col): أرجِع 1 إذا كانت col تساوي 0 أو كانت col مساوية لـ row.
وإلا فأرجِع entry(row-1, col-1) + entry(row-1, col).
لكل row من 0 إلى numRows-1، اجمع entry(row, col) لكل col من 0 إلى row.
أرجِع قائمة الصفوف.

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 triangle

أنشئ كل صف استنادًا إلى الصف الذي فوقه

الفكرة

يواصل الاستدعاء الذاتي طلب عناصر الصفوف السابقة، وأنت تبني تلك الصفوف على أي حال. لذا احسب الصفوف من الأعلى إلى الأسفل، وأثناء ملء الصف r، اقرأ الصف r-1 الذي اكتمل حسابه بالفعل. تتطلب كل قيمة عملية جمع واحدة: فجدول الإجابات الأصغر هو الناتج نفسه.

إن بدء كل صف بـ r + 1 من الواحدات يحدد كلا الطرفين، لذا لا تحتاج الصفوف 0 و1، التي لا تحتوي على مواضع داخلية، إلى حالة خاصة. يحتوي المثلث على 1 + 2 + ... + n، أي نحو n²/2، عنصرًا، لذا يكون العمل O(n²) من دون ذاكرة إضافية تتجاوز الناتج: 465 عنصرًا لـ 30 صفًا بدلًا من ملياري استدعاء.

الخوارزمية

ابدأ بقائمة فارغة من الصفوف.
لكل row من 0 إلى numRows-1، أنشئ row + 1 من الواحدات.
لكل col من 1 إلى row-1، عيّن قيمته إلى مجموع الموضعين col-1 وcol في الصف السابق.
ألحِق الصف وتابع. أعد القائمة.

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

أخطاء شائعة وحالات حدّية

إرجاع numRows + 1 صفوف. عند الترقيم بدءًا من 0، يكون الصف الأخير الذي تحتاج إليه هو numRows-1.
تشغيل الحلقة الداخلية على الحواف. الموضع 0 ليس له أب أيسر، والموضع row ليس له أب أيمن، لذا فإن قراءتهما تتجاوز الحدود.
نطاق يتعطل مع الصفوف الصغيرة. يتسبب 1..<row في Swift في حدوث تعطل عندما تكون row تساوي 0، ويعدّ 2:(row-1) في R تنازليًا حتى 1 عندما تكون row تساوي 2.
حساب العناصر باستخدام المضروب. إن C(29, 14) يقع ضمن نطاق int، لكن 29! يتجاوز سعة عدد صحيح ذي 64 بت.
إلحاق المصفوفة نفسها لكل صف ثم تغييرها. ينتهي الأمر بكل صف في الإجابة ليصبح الصف الأخير.

أسئلة شائعة3

ما التعقيد الزمني لإنشاء مثلث باسكال؟

O(n²) لـ n صفوف: يحتوي المثلث على نحو n²/2 من الخانات، وتتطلب كل خانة عملية جمع واحدة. وهذا هو الأمثل، إذ يجب كتابة كل خانة في الناتج. المساحة الإضافية، بخلاف الناتج، هي O(1).

ما علاقة مثلث باسكال بالمعاملات الثنائية؟

العنصر k من الصف r، مع بدء العد من 0، هو C(r, k)، أي عدد الطرق لاختيار k عناصر من بين r. قاعدة الجمع هي المتطابقة C(r, k) = C(r-1, k-1) + C(r-1, k)، ومجموع عناصر الصف r يساوي 2^r، وهو عدد المجموعات الجزئية لعناصر r.

هل يمكنك حساب صف واحد دون إنشاء الصفوف التي تسبقه؟

نعم. ابدأ بـ 1 واحصل على كل حد تالٍ من الحد السابق: C(r, k) = C(r, k-1) × (r-k+1) / k. اضرب قبل القسمة لكي تكون القسمة تامة، واستخدم عددًا صحيحًا ذا 64 بت لحاصل الضرب. يستغرق الصف r حينها زمنًا قدره O(r).

def generate(numRows):
    # اكتب الكود هنا

اختبار #1

اختبار #2

وسيط

numRows = 5

الإخراج المتوقع

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]