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

בעיות בסגנון בגרות שיטת עבודה שמחזיקה בלחץ

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

1

הרעיון

לכל שאלה עובדים באותם חמישה צעדים:

  1. קוראים את הדרישה
  2. כותבים דוגמאות
  3. מתכננים
  4. כותבים קוד
  5. עוקבים

קוראים ומבינים

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

מתכננים וכותבים

במשפט אחד: "עוברים על כל איבר, ובודקים…". רק אחר כך קוד. שמות משתנים ברורים, הזחה מסודרת, ו-return בסוף כל מסלול.

עוקבים ובודקים

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

לזכור: טבלת מעקב היא הכלי הכי חזק בבחינה. היא תופסת טעויות של אחד מעבר לגבול (off-by-one), לולאות שלא נגמרות ו-return במקום הלא נכון.
2

מעבדה: ארבע בעיות, צעד אחרי צעד

בחרו בעיה במחוון הראשון ואת הקלט במחוון השני. קראו את הדרישה, נחשו את התשובה, ורק אז הריצו את הפתרון לדוגמה שורה אחרי שורה.

נסו את אלה:

הריצו בעצמכם

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







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

  

    

      
מדפיסים במקום להחזיר

      
"כתבו פונקציה שמחזירה" פירושו return. פונקציה שמדפיסה מחזירה None, ומי שקרא לה לא יכול להשתמש בתוצאה.

      
✗ לא נכון
print(count)
✓ נכון
return count

    

    

      
חורגים מהרשימה

      
כשבודקים שכנים nums[i + 1], הלולאה חייבת לעצור איבר אחד לפני הסוף.

      
✗ לא נכון
for i in range(len(nums)):
✓ נכון
for i in range(len(nums) - 1):

    

    

      
return בתוך הלולאה, מוקדם מדי

      
"אם לא מצאנו, החזירו False" צריך לבוא אחרי הלולאה. בתוך הלולאה הוא עוצר כבר באיבר הראשון.

      
✗ לא נכון
for x in nums:
    if x == t:
        return True
    else:
        return False
✓ נכון
for x in nums:
    if x == t:
        return True
return False

    

    

      
pop ממחסנית ריקה

      
לפני pop() בודקים שהמחסנית לא ריקה. אחרת התוכנית נעצרת בשגיאה.

      
✗ לא נכון
stack.pop()
✓ נכון
if len(stack) == 0:
    return False
stack.pop()

    

  






  
4
דוגמה פתורה: חמשת הצעדים

  

    
  1. קוראים את הדרישה
  2. כותבים דוגמאות
  3. מתכננים
  4. כותבים קוד
  5. עוקבים

    

    

    

  






  
5
תרגול: מעקב אחרי קוד

  

  

  

    
    
    

    

    

  






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

  

    
איך מתכוננים לבגרות במדעי המחשב?

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

    
איך עושים טבלת מעקב?

    
פותחים עמודה לכל משתנה ועמודה לפלט. בכל פעם ששורה משנה משתנה, כותבים את הערך החדש בשורה חדשה בטבלה. בלולאות כותבים גם את תנאי הלולאה ואם הוא נכון. בסוף, הערך האחרון בכל עמודה הוא הערך הסופי.

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

    
סופרים כמה פעמים השורה הפנימית ביותר רצה, כפונקציה של גודל הקלט n. לולאה אחת על n איברים היא O(n). לולאה בתוך לולאה היא בדרך כלל O(n²). לולאה שחוצה את n בכל סיבוב היא O(log n). תרגלו למטה.

  






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