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
כל ערך ב-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, כך שחישוב 30 השורות מצריך יחד בערך 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.
כתיבת טווח שנכשל בשורות הקטנות. 1..<row של Swift גורם לקריסה כאשר 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]]