סימונים, התפתחות שלבית ולוגיקה
הוצג| English | משמעות |
|---|---|
| notation/nəʊˈteɪʃn/ | סימונים |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | אנגלית מבנית |
| pseudocode/ˈsuːdəʊkəʊd/ | קוד מדומה |
| flowchart/ˈfləʊtʃɑːt/ | תרשים זרימה |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | התמקדות הדרגתית |
| logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ | ביטוי לוגי |
| Boolean/ˈbuːlɪən/ | בוליאני |
| precedence/ˈpresɪdəns/ | עדיפות |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | חוקי דה מורגן |
לאלגוריתם הראשון לא הייתה שפה לכתיבה בה
- בשנת 1843 אדה לEventListener פרסמה את הצעדים לחישוב מספרי ברנולי על מכונת האנליטית של באבע', מכונה שלא נבנתה לעולם.
- לא הייתה שפת תכנות, ולכן היא כתבה את האלגוריתם כטבלה ממוספרת של פעולות: סימנוּת משלו.
- כל אלגוריתם עדיין מתחיל כך. כותבים אותו בסימנוּת כלשהי, בודקים אותו, ואז רק אז הופכים אותו לקוד.
- שיעור זה עוסק בשלושת הסימנויות הבחינה משתמש בהן, כיצד מעברים ביניהן, וכיצד כותבים את התנאים בתוך它们.
שלושה סימנויות
- אנגלית מובנית: משפט רגילים, מרווחים פנימה, עם מעט מילים קבועות כמו
IF,FOR EACH,REPEAT. טוב לתוכנית אב ראשונית. - פסאודוקוד: סימנוּת המילות-מפתח (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), הקרובה ביותר לקוד אמיתי ומסומנת לפי מדריך קיימברידג' - גרף זרימה: דיאגרמה של צורות סטנדרטיות. מלבן מעוגל עבור
START/STOP, מקבילית עבור קלט ותפוקה, מלבן עבור תהליך, יהלום עבור החלטה, חצים לזרימה.
גרף זרימה לחישוב ממוצע של רשימת מספרים, מצויר בצורות הסטנדרטיות
בדיאגרמת זרימה, איזה צורה מייצגת החלטה?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מעוין הוא החלטה; מלבן מעוגל = התחלה/סיום, מקבילית = קלט/פלט, מלבן = תהליך.
התאימו כל צורת בדיאגרמת זרימה למשמעות שלה.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
פראללוגרם = כניסה/יציאה, מלבן = תהליך, מלבן מעוגל = התחלה/עצירה, יהלום = החלטה.
התאם כל סממן לתיאור המתאים לו.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
שלושת התיאורים מתארים את אותו אלגוריתם ברמות שונות של קרבה לקוד.
דוגמא פותרת: מאנגלית מובנית לפסאודוקוד
- אנגלית מובנית: הגדר את הסכום לאפס. לכל אחד מה-N מספרים, הוסף אותו לסכום. חלק את הסכום ב-N והוצא את התוצאה.
- כל משפט הופך לבנייה אחת: הטלת ערך, לולאת
FORעם הטלת ערך בתוכה, ולאחר מכן הטלת ערך והוצאה.
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- הסדר של המשפטים הוא סדר ההצהרות. אין תוספות ואין חסר.
באלגוריתם הממוצע, לולאת FOR שמוסיפה כל מספר לסכום היא דוגמה לבניית ה-____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
חזרה על בלוק עבור כל מספר היא איטרציה. ההקצה בתוכו מאחסן את הסכום הצובר.
דוגמה מופת: פסאודוקוד לדיאגרמת זרימה
- לקחת את אותו אלגוריתם.
STARTנכנס למלבן מעוגל, ו-Total ← 0ו-Index ← 1במלבנות רגילים. - לולאת ה-
FORהופכת ליהבום ששואלIndex <= N?. יציאת כן מובילה למלבןTotal ← Total + Number[Index], אחר כך ל-Index ← Index + 1, ולחץ חזרה למעלה ליהבום. - יציאת לא ממשיכה ל-
Average ← Total / N, מקבילית תפוקה, ול-STOP. - לתווות שתי יציאות בכל יהבום. יהבום עם יציאה אחת בלתי-תוויית אינו החלטה.
פישוט הדרגתי
- הדק הדורגות (Stepwise refinement) פירונו כתיבת אלגוריתם כתוכנית ערוכים קצרה, ולאחר מכן הרחבת כל צעד לתת-צעדים מפורטים יותר, וחזרה על פעולה זו עד שכל צעד ניתן לקידוד ישיר.
- כל רמה שומרת על המבנה של הרמה שעליה ומוסיפה פרטים. התוכנית הערוכים לא מושלכת: היא הופכת למבנה התוכנה.
- העיצוב נעצר כאשר צעד הוא שורת פסאודוקוד אחת או מודול שיש כבר.
הדק הדורגות מרחיב כל צעד עד שהוא ניתן לקידוד
שיפור צעד אחר צעד הוא הטכניקה של:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אתה משפר מבנה גבוה-רמת צעד אחר צעד, מוסיף פרטים תוך שמירה על המבנה.
דוגמה מופת: שלושה רמות
- רמה 1: עיבוד תוצאות המבחן.
- רמה 2: הקלטת כל ציון. חישוב הממוצע. ספירת מספר הנמצאים. הפקת הדוח.
- רמה 3, פירוט "ספירת מספר הנמצאים":
Passes ← 0, אחר כךFORלכל ציון,IF Mark >= 40 THEN Passes ← Passes + 1. - כאשר מבקשים "לתאר הדק הדורגות", נתנו את שלוש הרעיונות: להתחיל מתוכנית ערוכים, להרחיב כל צעד לצעדים קטנים יותר, לעצור כאשר כל צעד ניתן לתכנות.
התפתחות שלבית: מתוכנית עיקר לקוד
ירידה ברמות. מתחילים עם המשימה כולה בשורה אחת וממשיכים לפצל כל צעד לתתי-צעדים קטנים יותר — עד שכל צעד פשוט מספיק כדי לקודד ישירות.
בשיפור צעד אחר צעד, כל רמה חדשה מחליפה את הרמה שמעליה, ולכן המבנה המקורי נזרק.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
כל רמה שומרת על המבנה של הרמה שמעליה ומוסיפה פרטים. המבנה הופך לצורת התוכנה המוגמרת.
פקודות לוגיקה
- הצהרת לוגיקה היא תנאי בוליאני: היא או
TRUEאוFALSE, והיא שולטת ב-IF, ב-WHILEאו ב-UNTIL. - היא בנויה מהשוואות (
=,<>,<,>,<=,>=) המחוברות על ידיAND,ORו-NOT. Mark >= 0 AND Mark <= 100נכון רק עבור ציונים בטווח.Age < 12 OR Age >= 65נכון עבור ילדים וקצינים.
השוואות המחוברות על ידי AND, OR ו-NOT יוצרות תנאי אחד
עדיפות סמנים וסוגריים
- סמנים מופעלים בסדר עדיפות קבוע:
NOTראשון, לאחר מכןAND, ואזOR. - לכן
A OR B AND CפירושוA OR (B AND C), ולא(A OR B) AND C. עםA = TRUE,B = FALSE,C = FALSEהראשון הואTRUEוהשני הואFALSE. - השתמש בסוגריים כשהתנאי מעורב
ANDו-OR. הם אינם גורמים לעלות נוספת ומסירים את החסרונות.
סדר את פעולות הלוגיקה לפי עדיפות, מהגבוהה (מוערכת ראשונה) לנמוכה.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
NOT מחייב הכי חזק, אחר כך AND, ואז OR — השתמש בסוגריים כשאתה ספק.
ללא סוגריים, מה משמעות A OR B AND C?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
AND יש לו עדיפות גבוהה יותר מ-OR, ולכן הוא מוערך ראשון. סגור את התנאי בסוגריים בכל מקרה, כדי שאף אחד לא יצטרך לזכור.
חוקי דה מורגן
- חוק דה מורגן:
NOT (A AND B)זהה ל-(NOT A) OR (NOT B), ו-NOT (A OR B)זהה ל-(NOT A) AND (NOT B). - במילים: "לא (נסחר ושלם)" פירושו "לא נסחר, או לא שלם".
- השתמש בחוק כדי לפשט תנאי, או לבדוק אותו: בחר ערכים עבור
Aו-B, חשב את שני האגפים, והם חייבים להתאים זה לזה בכל מקרה.
על פי חוק דה מורגן, NOT (A AND B) זהה ל(NOT A) OR (NOT B).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
NOT מתפשט על הסוגריים ומפנה AND↔OR; באופן דומה NOT (A OR B) = (NOT A) AND (NOT B).
דוגמה מפורטת: תנאי מתוך טקסט
- כלל: סטודנט רשאי לשבת במבחן אם הוא נרשם וגם שילם או זוכה למענק, אך אם לא הושעה.
- קרא למשתנים הבוליאיים:
Registered,Paid,Bursary,Suspended. - הביטוי:
Registered AND (Paid OR Bursary) AND NOT Suspended. - הסוגריים סביב
Paid OR Bursaryהם קריטיים. ללאם,ANDיתפעל ראשון, וסטודנט עם מענק אך ללא הרשמה ייכנס.
אילו תנאים שקולים לNOT (Registered AND Paid)? בחר כל האפשרויות החלות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
דה מורגן הופך NOT של AND ל-OR של NOTs. הגרסה עם AND קשה מדי: תלמיד שנרשם אך טרם שילם אמור להפעיל את התנאי המקורי TRUE, והוא הופך את הגרסת AND FALSE.
סימונים נופלים מהיד
a = 1 OR 2אינו תנאי. כתובa = 1 OR a = 2: כל צד שלORחייב להיות השוואה מלאה.NOTחל רק על מה שמגיע אחריו.NOT A AND Bפירושו(NOT A) AND B.- יהלום זקוק לשתי יציאות מסומנות, ולולאה זקוק לחץ המוביל חזרה למעלה. סכימת זרימה ללא חץ חוזר אינה לולאה.
- אנגלית מבנית היא עדיין מדויקת. "טפל בציונים" אינו שלב; "הוסף את הציון לסך הכללי" כן.
לבדוק אם a הוא 1 או 2, התנאי הנכון הוא:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לכל צד של OR חייב להיות ביצוע השוואה מלא: a = 1 OR a = 2. כתיבת a = 1 OR 2 היא שגיאה נפוצה.
הבנתך מושלמת
- שלושה סמנויות לאלגוריתם אחד: אנגלית מבנית, פסודוקוד, סכימת זרימה (יהלום = החלטה, חץ חוזר = לולאה)
- פיצול צעד אחר צעד: תוסיף → הרחב כל שלב → עצור כאשר ניתן לקודד שלב
- ביטוי לוגי הוא תנאי בוליאני; עדיפות NOT → AND → OR, לכן סוגריו כל מה שמערב ביניהם
- דמורגן:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B