כיתה י · מבני נתונים ואלגוריתמים

רשימה דו-ממדית טבלה, לוח ושורה ועמודה

לוח של איקס עיגול, גיליון ציונים, מפה במשחק: כולם טבלאות. בפייתון טבלה היא רשימה של רשימות. כל רשימה פנימית היא שורה, ו-grid[r][c] הוא התא בשורה r ובעמודה c. כאן ניגשים לתאים, עוברים על הטבלה בלולאה כפולה ומחשבים סכומים. כדאי להכיר קודם רשימות ולולאות. גם מילונים עוזרים לשמור מידע על לוח.

הרעיון

grid = [
    [3, 1, 4],     # row 0
    [1, 5, 9],     # row 1
]
print(grid[1])      # [1, 5, 9]
print(grid[1][2])   # 9
print(len(grid), len(grid[0]))   # 2 3

קודם שורה, אחר כך עמודה

grid[1] הוא שורה שלמה: רשימה. grid[1][2] לוקח מהשורה הזו את המקום 2. גם השורות וגם העמודות מתחילות מ-0.

גודל הטבלה

len(grid) הוא מספר השורות. len(grid[0]) הוא מספר העמודות, כלומר האורך של שורה אחת.

לולאה כפולה

הלולאה החיצונית עוברת על השורות, והפנימית על התאים בכל שורה. בטבלה של 3 שורות ו-4 עמודות, השורה הפנימית רצה 3 כפול 4, כלומר 12 פעמים.

לזכור: grid[row][col], שורה ראשונה ועמודה שנייה. השורה האחרונה היא len(grid) - 1, לא len(grid).

מעבדה: עוברים על הטבלה תא אחרי תא

בחרו גודל לטבלה ותא מטרה. התוכנית מדפיסה את תא המטרה, מחשבת סכום לכל שורה בלולאה כפולה, ואז סכום של עמודת המטרה. לחצו "שורה הבאה": התא שהתוכנית קוראת עכשיו נצבע בצהוב.

שורות עמודות שורת המטרה r עמודת המטרה c

נסו את אלה:

צהוב: התא שנקרא עכשיו · מסגרת כחולה: תא המטרה grid[r][c] · בצד: סכומי השורות שכבר חושבו

הריצו בעצמכם

אפשר לשנות את הקוד ולהריץ פייתון אמיתי. בפעם הראשונה הטעינה לוקחת כמה שניות.

טעויות שכולם עושים

הפכו שורה ועמודה

הסדר הוא תמיד שורה ואז עמודה. בטבלה של 2 שורות ו-3 עמודות, grid[2][1] כבר מחוץ לטבלה.

✗ IndexError

grid = [[3, 1, 4], [1, 5, 9]]
print(grid[2][1])

✓ שורה 1, עמודה 2: 9

grid = [[3, 1, 4], [1, 5, 9]]
print(grid[1][2])

אחד יותר מדי

יש len(grid) שורות, ממוספרות מ-0. לכן range(len(grid)) מספיק בדיוק. עוד 1 יוצא מהטבלה.

✗ IndexError

for i in range(len(grid) + 1):
    print(grid[i])

✓ נכון

for i in range(len(grid)):
    print(grid[i])

שורות מועתקות

[[0] * 3] * 2 לא יוצר שתי שורות. הוא יוצר שורה אחת, ושני שמות שמצביעים עליה. שינוי אחד משנה "את שתיהן".

✗ [[5, 0, 0], [5, 0, 0]]

g = [[0] * 3] * 2
g[0][0] = 5
print(g)

✓ [[5, 0, 0], [0, 0, 0]]

g = [[0] * 3 for i in range(2)]
g[0][0] = 5
print(g)

הסכום מתאפס במקום הלא נכון

לסכום של כל שורה, מאפסים את s בתוך הלולאה החיצונית, לפני הפנימית. אם מאפסים פעם אחת בחוץ, כל "סכום שורה" כולל גם את השורות שלפניה.

✗ סכום מצטבר

s = 0
for row in grid:
    for x in row:
        s = s + x
    print(s)

✓ סכום לכל שורה

for row in grid:
    s = 0
    for x in row:
        s = s + x
    print(s)

דוגמה פתורה: לוח איקס עיגול

הלוח הוא 3 שורות של 3 תאים. התוכנית שמה O בתא אחד, מדפיסה את הלוח שורה אחרי שורה, ובודקת אם יש ל-X אלכסון מלא.

תרגול

שאלות שכולם שואלים

מה זה רשימה דו-ממדית בפייתון?

רשימה שכל איבר בה הוא רשימה בעצמו. כל רשימה פנימית היא שורה, וביחד הן טבלה. ניגשים לתא עם שני אינדקסים: grid[שורה][עמודה]. נסו במעבדה.

איך מחשבים סכום של עמודה?

עמודה היא לא רשימה אחת, אלא תא אחד מכל שורה. לכן עוברים על השורות ומוסיפים מכל אחת את התא באותה עמודה: col_sum = col_sum + grid[i][c].

כמה פעמים רצה לולאה כפולה?

מספר השורות כפול מספר העמודות. בטבלה של 10 על 10 זה 100 פעמים, ובלוח של 1000 על 1000 זה מיליון. בגלל זה לולאה כפולה היא דוגמה ל-O(n²) בסיבוכיות. תרגלו למטה.