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 .

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

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

Q: لماذا تُعَدّ مثلث باسكال مسألةً في البرمجة الديناميكية؟

يعتمد كل عنصر على مسألتين فرعيتين أصغر منه، وهما العنصران اللذان فوقه، وتتداخل هذه المسائل الفرعية بدرجة كبيرة: إذ تعيد العودية البسيطة حسابها مرارًا وتكرارًا. يتيح بناء الصفوف بالترتيب تخزين كل مسألة فرعية مرة واحدة وإعادة استخدامها، ما يحوّل العمل الأُسّي إلى O(n²) .

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

+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].

+13 اختبارات مخفية عند الإرسال

سؤال إضافي

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

تلميحات

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

فُتح 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، لذا تحتاج الصفوف الثلاثون معًا إلى نحو 2^31 استدعاءً، أي أكثر من ملياري استدعاء. يُعاد حساب القيم الصغيرة نفسها ملايين المرات: يقع entry(2, 1) أسفل كل قيمة تقريبًا في الصفوف التي تليه.

الخوارزمية

اكتب 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 بعدد r + 1 من الواحدات، ما يحدد طرفي الصف. ثم لكل موضع داخلي c من 1 إلى r-1، اجعل قيمته above[c-1] + above[c]. لا تحتوي الصفوف 0 و1 على مواضع داخلية، لذا تبقى [1] و[1, 1] من دون حالة خاصة.

يحتوي المثلث على 1 + 2 + ... + n، أي نحو n²/2 عنصرًا، ويتطلب كل منها وقتًا ثابتًا، لذا فإن العمل يستغرق O(n²). وباستثناء الناتج، الذي عليك إرجاعه على أي حال، لا تحتاج الطريقة إلى ذاكرة إضافية. عندما تكون numRows = 30، يكون العدد 465 عنصرًا بدلًا من ملياري استدعاء.

الخوارزمية

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

أسئلة شائعة4

ما هو التعقيد الزمني لتوليد مثلث باسكال؟

يستغرق إنشاء كل صف من الصف الذي فوقه زمنًا قدره 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.

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

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

لماذا تُعَدّ مثلث باسكال مسألةً في البرمجة الديناميكية؟

يعتمد كل عنصر على مسألتين فرعيتين أصغر منه، وهما العنصران اللذان فوقه، وتتداخل هذه المسائل الفرعية بدرجة كبيرة: إذ تعيد العودية البسيطة حسابها مرارًا وتكرارًا. يتيح بناء الصفوف بالترتيب تخزين كل مسألة فرعية مرة واحدة وإعادة استخدامها، ما يحوّل العمل الأُسّي إلى O(n²).

Python

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

حالات الاختبار

الحالة 1

الحالة 2

المدخلات

numRows = 5

المتوقع

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