مثلث باسكال

طريقان إلى نفس الفكرة

المتطلبات قبل البداية

المفاهيم الأساسية

مثلث باسكال مثلث من الأعداد يبدأ بـ 1 في القمة، وكل رقم بعد ذلك هو مجموع الرقمين اللذين فوقه مباشرة. الرقم الذي ما فوقه إلا رقم واحد (أي طرف الصف) يكون دائمًا 1‏.

1القاعدة في سطر واحد

لو سمّينا الصف السابق previous والصف الجديد row‏، فالقاعدة هي:

row[i] = previous[i - 1] + previous[i]

وهذه هي كل الخوارزمية. الباقي مجرد ترتيب للحلقات والحدود.

2خصائص تساعدك تتأكد أن حلك صحيح

3الحدود: من أين تأتي أخطاء الواحد الزائد

أشهر خطأ في هذا المشروع هو حلقة داخلية بحدود غلط. تأمّل الصف رقم 4 (الصف الرابع، طوله 5): العنصر الأول والأخير ثابتان 1‏، والعناصر الوسطى هي ثلاثة فقط: المواضع 1 و2 و3‏. لهذا الحلقة الداخلية تمشي range(1, row_index)، تبدأ من 1 وتنتهي قبل row_index‏.

4الحالات الحدّية

5التعقيد

المخرج نفسه فيه n(n+1)/2 رقمًا تقريبًا، أي O(n²)‏. فمهما كان حلك ذكيًا، لا تستطيع تنزل عن O(n²) زمنًا ولا O(n²) ذاكرة، لأنك مطلوب منك تُرجع كل هذه الأرقام. هذه نقطة مهمة: حد التعقيد الأدنى يحدده حجم المخرج، لا ذكاء الخوارزمية.

كيف يعمل؟

شكلان: الأول مسار الكود من الشرط الحدّي إلى آخر صف، والثاني من أين تأتي أرقام الصف الجديد بالضبط.

شكل 1، مسار البناء: الشرط الحدّي أولًا، ثم صف جديد لكل دورة، أطرافه ثابتة ووسطه محسوب من الصف السابق.

شكل 2، من أين تأتي أرقام الصف: كل رقم وسطي له سهمان من الصف السابق، والطرفان ما لهما إلا سهم واحد فصارا 1.

الحل خطوة بخطوة

نبني الحل ثم نشغّله فعليًا. كل مخرج تحت هو مخرج حقيقي من تشغيل الكود.

الخطوة 1، الحل

#!/usr/bin/python3
"""0-pascal_triangle"""


def pascal_triangle(n):
    """Return the first n rows of Pascal's triangle as a list of lists."""
    if n <= 0:
        return []

    triangle = [[1]]
    for row_index in range(1, n):
        previous = triangle[-1]
        row = [1]
        for i in range(1, row_index):
            row.append(previous[i - 1] + previous[i])
        row.append(1)
        triangle.append(row)
    return triangle

الخطوة 2، التشغيل

$ cat 0-main.py
#!/usr/bin/python3
pascal_triangle = __import__('0-pascal_triangle').pascal_triangle


def print_triangle(triangle):
    for row in triangle:
        print("[{}]".format(",".join([str(x) for x in row])))


if __name__ == "__main__":
    print_triangle(pascal_triangle(5))

$ ./0-main.py
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]

الخطوة 3، الحدود

>>> pascal_triangle(0)
[]
>>> pascal_triangle(-3)
[]
>>> pascal_triangle(1)
[[1]]
>>> len(pascal_triangle(10)[-1])
10
>>> sum(pascal_triangle(10)[-1])
512

آخر سطرين هما اختبارك الذاتي: الصف العاشر (فهرس 9) طوله 10، ومجموعه 512 وهو 2**9 بالضبط. لو ظهر عندك غير ذلك فعندك خطأ في الحدود.

الخطوة 4، امشِ معها صفًّا صفًّا

اعتقاد شائع × الحقيقة

أين نستخدمه فعليًا؟

جرّب بنفسك

بطاقات مراجعة سريعة

تحقّق من فهمك