דלג לתוכן

עיצוב אלגוריתמים ופתיחת בעיות

מדעי המחשב A-Level · נושא 9

שיעור וידאו לנושא זה פתח את עמוד הוידאו
14:30

חשיבה מחושבת

הנה משימה: לבנות מערכת להפעלת מלאי כל חנות – כל מוצר, כל מכירה, כל משלוח, כל דוח. כבעיה אחת גדולה, זה מדי גדול כדי…

קריינות באנגלית · כתוביות באנגלית ובסינית 中文 שאפשר להחליף ביניהן

9.1

חשיבה מחושבת

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

מקור: הסיילבוס הבינלאומי של קמבריד'ג'

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

חלקי תמונת פאזל לא גמורים
חשיבה מחושבת מפצלת בעיה גדולה לחלקים קטנים וקלים יותר — כמו פתירת פאזל

אבסטרקציה

אבסטרקציה משמעותה שמירה על התכונות המהותיות של בעיה ו-התעלמות מהפרטים הלא רלוונטיים, ומספקת מודל פשוט יותר.

דוגמאות:

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

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

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

ה abstraction ממירה גיאוגרפיה אמיתית מבולגנת (מסלול מתעגל עם מבנים מפוזרים) למפת מתרו נקייה - מעגלי תחנות מרווחים באופן שווה בקו ישר, שמירה על התחנות והקווים והתעלמות מהגיאוגרפיה
אבסטרקציה שומרת על המהות (תחנות וקווים) ומסירה פרטים לא רלוונטיים (הגיאוגרפיה)

פירוק

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

  1. מציאת החלקים הראשיים של המשימה.
  2. פיצול כל אחד לחלקים תת-משימתיים קטנים יותר.
  3. המשך עד שכל חלק יהיה קטן מספיק לעיצוב ישיר.
  4. פתור את המשימות הקטנות ואחד אותן.

למניעת מלאי: "ניהול מלאי" → "רישום מכירות", "רישום אספקות", "יצירת דוחות" → ("רישום מכירות") "חיפוש מוצר", "הפחתת ספירת מלאי", "שמירת העסקה". פירוק הופך בעיות גדולות לניתנות להנהלה, מאפשר לצוות לחלק את העבודה ומספק קוד מודולרי — כל מודול הופך ל-פרוצדורה או פונקציה.

"הסבר מדוע משתמשים בפירוק" היא שאלה בעלת 3 נקודות עם צורה קבועה. תן three separate benefits: כל תת-בעיה קטנה מספיק כדי לעצב, לקודד ולבדוק את עצמה; מתפתחים שונים יכולים לעבוד על מודולים שונים בו-זמנית; מודול קיים (או פונקציית ספרייה) ניתן להשבה, וטעות קלה יותר לאיתור כי היא נמצאת בתוך מודול אחד. דיאגרמת מבנה (נושא 12) היא הדיאגרמה של הפירוק: התוכנית בחלק העליון, המודולים מתחתיה, והנתונים שעוברים ביניהם.

עץ עם "ניהול מלאי" בחלק העליון המסתעף למודולים "רישום מכירות", "רישום אספקות" ו"הפקת דוחות", כאשר "רישום מכירות" מתפצל לתתי-משימות "חיפוש מוצר", "הפחתת ספירת מלאי" ו"שמירת העסקה"
פירוק תוכנית למודולים ותת-מודולים
חקור

פתרון בעיה באמצעות גישה מחושבת

עבור על ארבעת העמודים בסיסמא בשורה שבהם היית משתמש בהם — פצל את הבעיה, זיהה מה חוזר, סירב למידע מיותר, ולאחר מכן כתוב את השלבים.

מילון מונחים אימון
English עברית
computational thinking/ˌkɒmpjuːˈteɪʃənl ˈθɪŋkɪŋ/ חשיבה מחושבת
abstraction/əbˈstrækʃn/ השגת מושג
decomposition/ˌdiːkɒmpəˈzɪʃn/ פירוק
sub-problem/sʌb ˈprɒbləm/ תת-בעיה
procedure/prəˈsiːdʒə/ פרוצדורה
modules/ˈmɒdjuːlz/ מודולים
algorithm/ˈælɡərɪθəm/ אלגוריתם
9.2

אלגוריתמים

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

מקור: הסיילבוס הבינלאומי של קמבריד'ג'

מיון בועות, מעבר אחר מעבר

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

חקור

בחירה: עקבו אחר הענפים של IF / ELSE

גררו את הציון וצפו באיזה ענף מתבצע. מבנה בחירה בודק כל תנאי בתורו ובוחר בתנאי הראשון שמתקיים — כך פועל IF … ELSE IF … ELSE.

צפה בשיעור
9.2

טבלת זיהוי

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

זהה סוג מידע הסבר
Category STRING קטגוריית המוצר
SaleDate DATE מתי הפריט נמכר
ItemCost REAL עלות הפריט
InStock BOOLEAN TRUE אם במלאי
Sales ARRAY[1:30] OF REAL סך המכירות היומיות האחרונים ל-30

השתמש בשמות תיאוריים (ItemCost, לא x): הזהה מתחיל באות, אינו מכיל רווחים, וכתוב באותה צורה בכל פעם שהוא מופיע. סוגים נפוצים הם INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE, בנוסף למערכים. הטבלה מחייבת לקרוא לכל פרט מידע לפני כתיבת הקוד, ושאלת "השלם את טבלת הזיהוי" נותנת נקודה אחת עבור כל סוג מידע או הסבר נכון, לכן כתוב את הסוג בדיוק כפי שהמדריך לפסאודוקוד עושה.

טבלת זיהוי המפרטת כל משתנה עם שמו, סוג המידע וההסבר שלה, לדוגמה ItemCost כREAL עבור עלות הפריט
טבלת מזהים מיישמת את שם כל חלק נתונים לפני שכתבים קוד
מילון מונחים אימון
English עברית
identifier table/aɪˈdentɪfaɪə ˈteɪbl/ טבלת מזהים
identifier/aɪˈdentɪfaɪə/ מזהה
Boolean/ˈbuːlɪən/ בוליאני
9.2

פסאודוקוד — שלושת הבניינים הבסיסיים

פסאודוקוד הוא אופן מובנה, ניטרלי לשפה, לתיאור אלגוריתמים.

שלושת הבניינים הבסיסיים כתרשימי זרימה מינימליים: רצף מפעיל צעד A ולאחר מכן B ולאחר מכן C; בחירה בודקת תנאי ועושה X או Y; איטרציה חוזרת גוף בעוד תנאי מתקיים, חוזרת לאחור
שלושת המרכיבים הבסיסיים בכל אלגוריתם: רצף, בחירה ואיטרציה

1. רצף

שלבים פועלים אחד אחרי השני (רצף):

INPUT Name
INPUT Age
OUTPUT "Hello", Name

2. בחירה

בחירה של אילו שלבים יפעלו, על בסיס תנאי (בחירה):

IF Age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

עבור אפשרויות נוספות, השתמש ב-CASE OF ... ENDCASE.

3. איטרציה

חזרה על בלוק (איטרציה, לולאה):

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

לולאת WHILE בודקת את התנאי לפני כל עבר (יכולה להתבצע אפס פעמים); לולאת REPEAT...UNTIL בודקת אחרי כל עבר (תתבצע לפחות פעם אחת).

WHILE Total < 100 DO
    INPUT Value
    Total ← Total + Value
ENDWHILE

REPEAT
    INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100
שני גרפי זרימה לצד זה. WHILE בודקת את התנאי קודם, כך שהגוף לא יתבצע לעולם: הצימרון נמצא מעל הגוף והענף No יוצא מהלולאה. REPEAT UNTIL מבצעת את הגוף קודם ובוחנת אחריו, כך שהגוף מתבצע לפחות פעם אחת: הגוף נמצא מעל הצימרון וענף No חוזר אליו
לולאת WHILE בודקת לפני ביצוע הגוף; לולאת REPEAT ... UNTIL בודקת אחריו, ולכן הגוף שלה מתבצע תמיד לפחות פעם אחת

בחירת סוג הלולאה היא נקודה במבחן: FOR כשיודעים כמה פעמים (לולאת בקרת מונה); WHILE כשהלולאה עשויה לא להתבצע כלל (לולאת תנאי מקדימה); REPEAT ... UNTIL כשהיא חייבת להתבצע לפחות פעם אחת, כמו באישור קלט (לולאת תנאי בלאדי). תשובה "תאר את מבנה האיטרציה" צריכה לנקות את שם המבנה, לומר היכן נבדק התנאי, ולתאר את ההש consequences (אפס פעמים או לפחות פעם אחת).

פעולות נפוצות

  • הטלה: x ← 5 (חץ; = משמש להשוואה).
  • קלט/פלט: INPUT variable, OUTPUT expression.
  • השוואות =, <>, <, >, <=, >=; לוגיקה AND, OR, NOT.
  • אריתמטיקה + - * /, פלוס DIV (חילוק שלם) וMOD (שארית).
  • מחרוזות: LENGTH, LEFT, RIGHT, MID, ו& עבור הצמדה (חיבור).

הפסאודוקוד הנדרש במבחן

כל תשובה בפסאודוקוד מסומנת בהתאם למדריך הפסאודוקוד המתפרסם של Cambridge. כתוב את הצורות הללו בדיוק:

מבנה פסאודו-קוד
משתנה DECLARE Total : INTEGER
מערך DECLARE Marks : ARRAY[1:30] OF REAL
קבוע CONSTANT MaxTries = 3
הזמנה Total ← Total + Value
כניסה / יציאה INPUT Name
OUTPUT "Hello ", Name
בחירה CASE OF Choice
1 : OUTPUT "Add"
OTHERWISE OUTPUT "Error"
ENDCASE
לולאת FOR FOR i ← 1 TO 10 STEP 2 ... NEXT i
לולאת WHILE WHILE Total < 100 DO ... ENDWHILE
לולאת REPEAT REPEAT ... UNTIL Mark >= 0
אריתמטיקה של שלמים 17 DIV 5 = 3
17 MOD 5 = 2
מחרוזות LENGTH(S), LEFT(S, 3), RIGHT(S, 2)
MID(S, 2, 4), TO_UPPER(S), TO_LOWER(S)
המרות INT(3.7) = 3, NUM_TO_STR(12)
STR_TO_NUM("4.5"), ASC('A') = 65, CHR(66) = 'B'
מקרי RAND(100)
INT(RAND(100)) + 1

RAND(100) נותן מספר אמיתי מ-0 ועד (לא כלול) 100. INT(RAND(100)) + 1 נותן שלם מ-1 עד 100.

שתי הרגליים מביאות ציון בכל שאלה: להכריז על כל משתנה שמשתמשים בו, עם הסוג מטבלת המזהים שלך, ולהתחיל כל מונה וסך (Count ← 0, Total ← 0) לפני הלולאה שמעריכה אותו.

כניסה → עיבוד → יציאה

כל תוכנית עוקבת אחרי צורה זו:

INPUT Length
INPUT Width
Area ← Length * Width
OUTPUT "Area = ", Area

רשימת הכניסות והיציאות קודם מכנה את האלגוריתמה נקייה יותר.

דוגמה מפורטת. כתוב פסאודו-קוד שמכניס 100 שלמים ומפיק כמה מהם, ואת סכומם, הנמצאים בין 10 ל-20 כולל.

טבלת מזהים: Count : INTEGER (ספן מחזור), Value : INTEGER (המספר השלם שנכנס זה עתה), InRange : INTEGER (כמה מהם היו בטווח), Total : INTEGER (סכומם).

DECLARE Count, Value, InRange, Total : INTEGER
InRange ← 0
Total ← 0
FOR Count ← 1 TO 100
    INPUT Value
    IF Value >= 10 AND Value <= 20 THEN
        InRange ← InRange + 1
        Total ← Total + Value
    ENDIF
NEXT Count
OUTPUT InRange, Total

אם השאלה מבקשת ממך ל"זיהוי שני מבנים וליישר כיצד כל אחד מהם משמש", ענה באותה צורה: איטרציה, מחזור ה-FOR, חוזר על הכניסה 100 פעמים; בחירה, פקודת ה-IF, מוסיפה ערך רק כאשר הוא נמצא בטווח.

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

טבלת מזהים: Secret : INTEGER (המספר להנחש), Guess : INTEGER (הכניסה של המשתמש), Tries : INTEGER (כמה ניחושים היו עד כה).

DECLARE Secret, Guess, Tries : INTEGER
Secret ← INT(RAND(100)) + 1
Tries ← 0
REPEAT
    INPUT Guess
    Tries ← Tries + 1
    IF Guess < Secret THEN
        OUTPUT "Too low"
    ELSE
        IF Guess > Secret THEN
            OUTPUT "Too high"
        ENDIF
    ENDIF
UNTIL Guess = Secret
OUTPUT "You took ", Tries, " guesses"

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

תרשים זרימה של משחק הניחוש: התחלה, ולאחר מכן הגדר Secret כמספר שלם אקראי מ1 עד 100 והגדר Tries ל0, ולאחר מכן הקלד ניחוש, הוסף 1 ל-Tries, בדוק אם הניחוש שווה לסוד (Yes מוביל ליציאת Tries ועצירה), אחרת בדוק אם הניחוש קטן (Yes מוציא Too low, No מוציא Too high), ושתי היציאות מחזור לחזרה להקלט
אותו משחק הנחשות כתרשים זרימה: שני יהלומי ההחלטה הם שתי פקודות ה-IF, וחץ החזרה הוא מחזור ה-REPEAT ... UNTIL

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

ישנם 21 ערכים אפשריים, ולכן INT(RAND(21)) נותן 0 עד 20 והחסרת 10 מזיזה אותו לטווח $-10$ ל-$10$. המספר השני חייב להיות מיוצר שוב עד שהוא שונה מהראשון:

DECLARE First, Second : INTEGER
First ← INT(RAND(21)) - 10
REPEAT
    Second ← INT(RAND(21)) - 10
UNTIL Second <> First
OUTPUT First, Second
כל תוכנית עוקבת אחר הצורה כניסה, followed by עיבוד, followed by הוצאה, מוצג עם דוגמת השטח: הכנס את האורך והרוחב, עיבוד על ידי כפל, הוצאת השטח
כל תוכנית עוקבת אחר צורת הכניסה, העיבוד, ההוצאה
חקור

בחירה IF … ELSE

שנה את הערך והצפה איזה ערוץ יופעל – כיצד תוכנית מקבלת החלטה.

מילון מונחים אימון
English עברית
sequence/ˈsiːkwəns/ רצף
unambiguous/ʌnæmˈbɪɡjuːəs/ בלתי-מסוכן
deterministic/dɪˌtɜːmɪˈnɪstɪk/ דיטמיניסטיבי
variable/ˈveərɪəbl/ משתנה
data type/ˈdeɪtə taɪp/ סוג נתונים
pseudocode/ˈsuːdəʊkəʊd/ קוד מדומה
flowchart/ˈfləʊtʃɑːt/ תרשים זרימה
selection/sɪˈlekʃn/ בחירה
iteration/ˌɪtəˈreɪʃn/ חזרה
loop/luːp/ לולאה
count-controlled loop/kaʊnt kənˈtrəʊld luːp/ לולאת שליטה במניין
pre-condition loop/priː kənˈdɪʃn luːp/ לולאת תנאי מקדים
post-condition loop/pəʊst kənˈdɪʃn luːp/ לולאת תנאי מאוחר
assignment/əˈsaɪnmənt/ הערכה
concatenation/kənˌkætəˈneɪʃn/ התאמה
initialise/ɪˈnɪʃəlaɪz/ התחלה
counter/ˈkaʊntə/ מונה
structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ אנגלית מבנית
stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ התמקדות הדרגתית
logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ ביטוי לוגי
precedence/ˈpresɪdəns/ עדיפות
De Morgan's law/də ˈmɔːɡənz lɔː/ חוקי דה מורגן
9.2

שלושה סמנויות

אותו אלגוריתם יכול להיות כתוב בשלושה אופנים.

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

חובה להיות מסוגל להמיר בין כל זוג: כל IF הוא יהלום החלטה, כל לולאה היא חזרה בחץ, וכל רצף הוא מלבנים ערוכים על גבי זה.

אם ... אז ... אלא אם כן ... סוף-אם

תרשים זרימה לחישוב ממוצע: מקטעים מעגלים "התחל" ו"עצור", משולשים "כניסה/יציאה", מלבני תהליך ויהלום החלטה "count < n?" שבענף כן חוזר לקרוא את הערך הבא
תרשים זרימה לחישוב ממוצע של רשימת מספרים, בשימוש בצורות הסטנדרטיות
9.2

פישוט צעד-בצעד

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

רמה 1:

Read in the numbers
Compute the average
Output the average

רמה 2:

INPUT n
total ← 0
FOR i ← 1 TO n
    INPUT value
    total ← total + value
NEXT i
average ← total / n
OUTPUT average

כל פישוט שומר על המבנה הקודם ומוסיף פרטים.

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

פישוט צעד-בצעד: תוכנית רמה 1 (קרא את המספרים, חשב את הממוצע, הדפס את הממוצע) מורחבת לתוכנית פסאודוקוד רמה 2 מפורטת עם לולאת הכניסה וחילוק
פישוט צעד-בצעד: הרחב כל צעד גבוה לתוכנית פסאודוקוד מפורטת
חקור

התפתחות שלבית: מתוכנית עיקר לקוד

ירידה ברמות. מתחילים עם המשימה כולה בשורה אחת וממשיכים לפצל כל צעד לתתי-צעדים קטנים יותר — עד שכל צעד פשוט מספיק כדי לקודד ישירות.

9.2

ביטויים לוגיים

ביטוי לוגי הוא תנאי בוליאני השולט בהסתעפות, המיוצר ממשוויות (x > 10), מחברים (AND, OR, NOT) ובסוגריים. השתמש בו כתנאי של IF, WHILE או REPEAT...UNTIL:

WHILE attempts < 3 AND NOT loggedIn DO
    INPUT password
    IF password = correctPassword THEN
        loggedIn ← TRUE
    ELSE
        attempts ← attempts + 1
    ENDIF
ENDWHILE

עדיפות (גבוהה לנמוכה): NOT, לאחר מכן AND, לאחר מכן OR. השתמש בסוגריים כשאתה לא בטוח. טעויות נפוצות:

  • a = 1 OR 2 שגוי — כתוב a = 1 OR a = 2.
  • NOT a > 5 פירושו NOT (a > 5), כלומר a <= 5.
  • NOT (A AND B) זהה ל(NOT A) OR (NOT B) (חוקי דה מורגן) — שימושי לפישוט תנאים.

המרת משפט לתנאי לוגיקה היא מיומנות שנבדקת ישירות במבחנים. "כרטיס חינם לכל אחד מתחת לגיל 5 או מעל גיל 65" הופך לAge < 5 OR Age > 65. "ציון תקף אם הוא מספר שלם בין 0 ל-100" הופך לMark >= 0 AND Mark <= 100. "הלולאה נעצרת כאשר הקובץ נגמר או שנקראו עשר רשומות" הופך לUNTIL EOF(File) OR Count = 10. כתוב כל השוואה במלואה: Age > 65 וAge < 5, לעולם לא Age > 65 OR < 5.

עץ פירוק עבור "attempts < 3 AND NOT loggedIn": NOT חל על loggedIn קודם, ואז AND מחבר זאת עם attempts < 3
עדיפות: NOT נקשר ל-loggedIn קודם, ואז AND משלב את שני הצדדים

דוגמה פתורה. כתבו טבלת מזהירים ופסודוקוד לקריאת 10 מספרים ולהוצאת הגדול ביותר. טבלת המזהירים מיימנת כל משתנה עם סוג הנתונים והמטרה שלה: Count : INTEGER (סופר לולאה), Num : REAL (המספר שקראנו זה עתה), Max : REAL (הגדול עד כה).

Max ← -999999
FOR Count ← 1 TO 10
    INPUT Num
    IF Num > Max THEN
        Max ← Num
    ENDIF
NEXT Count
OUTPUT Max

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

דרישות תכנות לשאלות אלגוריתם

לפני כתיבה או מעקב אחרי אלגוריתמים, השתמש בשיטות הביטוי והפונקציה המובנית בדפים 11.1.1–11.1.2. TO_UPPER ו-TO_LOWER מקבלים מילים שלמות; UCASE ו-LCASE במדריך פועלים על תווה בודד. עקוב אחרי ההכנסה של השאלה.

חבר מילים עם &; המer מספר עם NUM_TO_STR לפני שחיבור אותו. קרא פרוצדורה עם CALL Name(arguments); השתמש בפונקציה כארגון. SETDATE(day, month, year) בונה ערך DATE. בדוק סוגים לפני הערכה: ביטוי לא תקין הוא ERROR, לא המרה מוערכת.

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

9.2

הגדרות מקובלות בקורס

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

מונח הגדרה
אבסטרקציה שמירה על הפרטים החיוניים של בעיה ושליטה בפרטים שאינם נדרשים
פירוק שבירת בעיה למשאלות משנה קטנות יותר, שכל אחת מהן ניתן לפתור בנפרד
אלגוריתם פתרון לבעיה המבוטא בסדרה של צעדים מוגדרים
טבלת זיהויים טבלה המפרטת כל זיהוי (משתנה) המשמש באלגוריתם עם סוג הנתונים ותיאור המטרה שלו
פסאודוקוד דרך מבנית, בלתי תלויה בשפה, לכתיבת צעדי האלגוריתם
דיאגרמת זרימה דיאגרמה המראה את צעדי ההחלטות והשלבים של אלגוריתם באמצעות סמלים סטנדרטיים המחוברים בחצים
רצף ביצוע הודעות אחת לאחר השנייה בסדר הכתיבה
בחירה בחירת אילו הודעות לבצע בהתאם לתנאי
איטרציה חזרה על קבוצת הודעות בזמן או עד שהתנאי מתקיים
פישוט צעד-בצעד שבירת כל צעד בתוכנית גסה לצעדים קטנים יותר, שוב ושוב, עד שכל צעד ניתן לקוד ישירות
תנאי לוגיקה תנאי המ בנוי מהשוואות ומפעילים AND, OR ו-NOT שמציבים TRUE או FALSE
9.2

טיפים לבחינות

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

טעויות נפוצות

  • השתמש ב = להערכה. הערכה היא ←; = הוא השוואה.
  • שכחת ENDIF, ENDWHILE, ENDCASE או NEXT. כל מבנה נסגר, והמילה המסתיימת היא בה מופקד הניקוד על המבנה.
  • לא ייזמת סך כולל או ספן לפני הלולאה, כך שהאלגוריתם מוסיף ערך שלא קיים לעולם.
  • שימוש במעגל FOR כאשר מספר החזרות אינו ידוע. קריאה עד לקבלת ערך סיום או ניחוש נכון דורשים WHILE או REPEAT ... UNTIL.
  • כתבת Age > 65 OR < 5. צד אחד של OR ו AND חייב להיות השוואה מלאה.
  • ענה "הסבר מדוע משתמשים בפירוק" עם תועלת אחת שנכתבה בשלושה אופנים. שלושה נקודות דורשות שלוש תועלות שונות.

שיעורים אינטראקטיביים בנושא זה

לעבור על הדברים צעד אחר צעד, עם תרגילים לבדיקה מיידית.

מבחני עבר

נושאים נוספים במדעי המחשב A-Level

היכנס או צור חשבון

IGCSE, A-Level & AP