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
כל איבר ב־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 או שווה ל־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) נכנס למספר שלם, אבל 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]]