אלגוריתמים וקוד מדומה

הקו הרווח היקר בהיסטוריה

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

מהו אלגוריתם

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

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

דוגמה פתרה: טבלת המזהים

טבלת מזהים מיישמת את שם כל חלק נתונים לפני שכתבים קוד

שלושת הבניינים

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

• הקצהת אוצרת ערך באמצעות חץ, Total ← Total + Value; = משמש להשוואה. DIV היא חלוקה של מספר שלם וMOD שארית החלוקה, ולכן 17 MOD 5 = 2.

INPUT Age                      # sequence
IF Age >= 18 THEN
    # selection
ENDIF
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF
FOR Count <- 1 TO 10           # iteration
    OUTPUT Count
NEXT Count

שלושת בלוקי הבניין של כל אלגוריתם

איזו לולאה?

• FOR … NEXT כאשר יודעים כמה פעמים: לולאת בקרת ספירה.
• WHILE … ENDWHILE בודק את התנאי לפני כל עברת לולאה, ולכן הגוף עשוי להתבצע אפס פעמים: לולאת תנאי מקדים.
• REPEAT … UNTIL בודק את התנאי אחרי כל עברת לולאה, ולכן הגוף תמיד מתבצע לפחות פעם אחת: לולאת תנאי מאחר. אימות קלט הוא המקרה הקלאסי.
• תשובה המבקשת "לתאר את מבנה האיטרציה" מציגה את שם הלולאה, אומרת איפה נבדק התנאי, ומציגה את ההשלכה.

לולאת WHILE בודקת לפני ביצוע הגוף; לולאת REPEAT … UNTIL בודקת לאחר כך

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

DECLARE Count, Total, NextNumber : INTEGER
Total <- 0
FOR Count <- 1 TO 100
    INPUT NextNumber
    IF NextNumber > 0 THEN
        Total <- Total + NextNumber
    ENDIF
NEXT Count
OUTPUT Total

זיהוי מבנים בקטע טקסט

• שאלה פופולרית מציגה חמישה קטעי פסאודוקוד ובוקשת לסמן אילו אחד מהם משתמש ב-הקצה, בחירה או איטרציה.
• Result ← CalculateTotal() הוא הקצה. WHILE IsClosed היא איטרציה. REPEAT … INPUT Value … UNTIL Sales[4] > Value היא איטרציה וגם הקצה (INPUT מאחסן ערך). IF Sales[Current] <= 150 THEN Discount ← TRUE סוף-אם
• סקורו כל שורה בקטע, לא רק את הראשונה. ייתכן ששורה תדרוש סימון כפול.

דיאגרמת זרימה

• דיאגרמת זרימה תיעד את אותו אלגוריתם באמצעות ציור. אליפסות הן START וEND, מלבנות הן תהליכים, מקביליות הן INPUT/OUTPUT, ומעיינית היא החלטה.
• מעיינית היא מקום בו מתרחשת בחירה, וקו זרימה שמחזיר למעלה בדיאגרמה הוא לולאה.
• הבחינה שואלת בשתי הדרכים: פסאודוקוד מדיאגרמת זרימה, ודיאגרמת זרימה מפסאודוקוד או אנגלית מבנית. כל סמל שתציירו צריך להתייחס לשורה אחת בפסאודוקוד.

כל סמל במפת ח的流程 מתאים לסוג אחד של פקודת פסדוקוד

דוגמה מפורטת: משחק הניחוחות

DECLARE Target, Guess : INTEGER
Target <- INT(RAND(100)) + 1
REPEAT
    INPUT Guess
    IF Guess < Target THEN
        OUTPUT "Too low"
    ELSE
        IF Guess > Target THEN
            OUTPUT "Too high"
        ENDIF
    ENDIF
UNTIL Guess = Target
OUTPUT "Correct"

משחק הניחוחות כמפת ח流程: הלולאה חוזרת לכניסת הנתונים עד שהניחוש תואם

פישוט הדרגתי

• פישוט הדרגתי פירונו להתחיל ממבנה כללי ולהרחיב כל צעד לצעדים מפורטים יותר, שוב ושוב, עד שכל צעד ניתן לכתיבה ישירה כפקודת פסדוקוד.
• "מעבד הזמנה" → "קבלת הפריטים", "חישוב הסכום הכולל", "קבלת תשלום" → "חישוב הסכום הכולל" הופך ל"לכל פריט, הוספת מחיר × כמות; יישום הנחה כלשהי".
• כל רמה היא פישוט של הרמה שמעליה, והרמות המוגמרות יחד הן העיצוב. "תאר פישוט הדרגתי" דורש את המבנה הכללי, ההרחבה וכלל עצירת הפישוט.

פשט כל צעד עד שהוא ניתן לקידוד ישיר

פקודות לוגיקה

• חלקים מהפתרון מוגדרים על ידי פקודות לוגיקה: תנאים הבנויים מהשוואות (=, <>, <, >, <=, >=) המחוברים על ידי AND, OR וNOT.
• נקודת סימון תקפה: Mark >= 0 AND Mark <= 100. הנחה חלה אם הלקוח הוא חבר או משקיע מעל 50: IsMember OR Total > 50.
• NOT (Mark < 40) אומר את אותו דבר כמו Mark >= 40. כתוב את הפקודה, ולאחר מכן בדוק אותה עם ערך בכל צד של הגבול.

השוואות המחוברות על ידי AND, OR וNOT בונות את התנאים שהאלגוריתם זקוק להם

סימונים נופלים מהיד

הבנתך מושלמת