בחירה וסיבובים

מדעי מחשב A - AP · נושא 2

הצגת שקפים אימון

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

2.1

בחירה וחזרה באלגוריתמים

סיילבוס

מטרות למידה 2.1.A: ייצוג דפוסים ואלגוריתמים המכילים בחירה וחזרה הנמצאים בחיי היומיום באמצעות כתיבה או דיאגרמות.

2.1.A.1 בלוקי הבניין של אלגוריתמים כוללים סדריות, בחירה וחזרה.
2.1.A.2 אלגוריתמים יכולים להכיל בחירה, דרך קבלת החלטות, וחזרה, באמצעות לולאות.
2.1.A.3 בחירה מתרחשת כאשר בחירת הכיוון בו תמשיך ביצוע האלגוריתם מבוססת על החלטה נכונה או שגויה.
2.1.A.4 חזרה היא מצב שבו תהליך חוזר על עצמו עד להשגת התוצאה הרצויה.
2.1.A.5 הסדר שבו משתמשים בסדריות, בחירה וחזרה תורם לתוצאת האלגוריתם.

מקור: תיאור הקורס והמבחן של College Board AP

תרשים זרימה עם יהלום החלטה: בחירה קובעת איזה מסלול האלגוריתם לוקח

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

שלושת מבני הבקרה: רצף, בחירה וחזרה

מילון מונחים אימון

English	עברית
control structures/kənˈtrəʊl ˈstrʌktʃəz/	מבני בקרה
selection/sɪˈlekʃn/	בחירה
iteration/ˌɪtəˈreɪʃn/	איטרציה
boolean expression/ˈbuːlɪən ekˈspreʃn/	ביטוי בוליאני
relational operators/rɪˈleɪʃənl ˈɒpəreɪtəz/	אופרטורים יחסים
if statement/ɪf ˈsteɪtmənt/	הבעת if
Logical operators/ˈlɒdʒɪkl ˈɒpəreɪtəz/	מפעילים לוגיים
short-circuit evaluation/ʃɔːt ˈsɜːkɪt ɪˌvæljuːˈeɪʃn/	הערכת קיצור מסלול
De Morgan's laws/də ˈmɔːɡənz lɔːz/	חוקי דה מורגן
while loop/waɪl luːp/	לולאת while
infinite loop/ˈɪnfɪnət luːp/	לולאת אינסוף
flag/flæɡ/	דגל
nested loop/ˈnestɪd luːp/	לולאה מקושרת
Run-time analysis/rʌn taɪm əˈnæləsɪs/	ניתוח בזמן הרצה

2.2

ביטויים בוליאניים

סיילבוס

מטרת הלמידה 2.2.A: פיתוח קוד ליצירת ביטויים בוליאניים עם אופרטורים יחסיים והחלטת תוצאת הביטויים האלו.

2.2.A.1 ערכים ניתן להשוות באמצעות אופרטורים יחסים == ו-!= כדי לקבוע האם הערכים זהים. עבור סוגים פרמיטיביים, השוואה זו מבצעת השוואה בין הערכים הפרמיטיביים עצמם. עבור סוגי ייחוס (Reference Types), ההשוואה היא בין הייחוסים של האובייקטים.
2.2.A.2 ערכים מספריים ניתן להשוות באמצעות האופרטורים היחסיים <, >, <= ו->= כדי לקבוע את הקשר בין הערכים.
2.2.A.3 ביטוי המכיל אופרטורים יחסים מתערך לתוצאה בוליאנית.

מקור: תיאור הקורס והמבחן של College Board AP

שערי לוגיקה ומחבר חצי

ביטוי בוליאני מחזיר ערך של true או false, תוך שימוש ב-מפעילי יחס: == (שווה), != (לא שווה), <, >, <=, >=. שימו לב ש-== משווה ערכים גולמיים אך הפניות לעצמים (object references) עבור עצמים, ולכן יש להשתמש ב-.equals עבור Strings.

שלושת משפחות המפעילים: אריתמטי, יחסי ולוגי

חקור

חקרו טבלת אמת AND

ביטוי בוליאני מעריך לתוצאת true או false. AND נכון רק כאשר שניהם המקדמים נכונים; הופעים את הקלטות כדי לראות את ארבע המקרים.

2.3

פקודת if

סיילבוס

מטרת הלמידה 2.3.A: פיתוח קוד לייצוג תהליכים לוגיים ענפים באמצעות הוראות בחירה והחלטת תוצאת תהליכים אלו.

2.3.A.1 הוראות בחירה משנות את ביצוע ההוראות ברצף.
2.3.A.2 הוראת if היא סוג של הוראת בחירה המשפיעה על זרימת הבקרה על ידי ביצוע חלקי קוד שונים בהתבסס על ערך הביטוי הبولיאני.
2.3.A.3 בחירה חד-כיוונית (הוראת if) משמשת כאשר יש חלק קוד לביצוע בתנאי מסוים. במקרה זה, הגוף יופעל רק כאשר הביטוי הبولיאני הוא true.
2.3.A.4 בחירה דו-כיוונית (הוראת if-else) משמשת כאשר ישנם שני חלקי קוד – אחד לביצוע כאשר הביטוי הبولיאני הוא true ואחד נוסף לביצוע כאשר הביטוי הبولיאני הוא false. במקרה זה, גוף ה-if יופעל כאשר הביטוי הبولיאני הוא true, וגוף ה-else יופעל כאשר הביטוי הبولיאני הוא false.

מקור: תיאור הקורס והמבחן של College Board AP

הביטוי if מפעיל בלוק רק כאשר התנאי שלו נכון; else אופציונלי מספק חלופה:

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

אורות תנועה: בחירה קובעת איזה ערוץ יתבצע, בדיוק כמו שפקודות if בוחרות דרכי קוד

חקור

ראו איזה ענף if בוחר

הצהרת if מنفذת את הגוף שלה רק כאשר התנאי נכון, אחרת היא דורשת לelse. החליקו את הציון על פני הגבולות וצפו כיצד הציון משתנה.

2.4

פקודות if משובצות

סיילבוס

מטרת הלמידה 2.4.A: פיתוח קוד לייצוג תהליכים לוגיים ענפים מקוננים והחלטת תוצאת תהליכים אלו.

2.4.A.1 הוראות if מקוננות מכילות בתוכם הוראות if, if-else או if-else-if בתוך הוראות if, if-else או if-else-if.
2.4.A.2 הביטוי הبولיאני של ה-if המקוננת הפנימית מתערך רק אם הביטוי הبولיאני של ה-if החיצוני מתערך לתוצאה true.
2.4.A.3 בחירה רב-דרכית (if-else-if) משמשת כאשר יש סדרה של ביטויים עם חלקי קוד שונים לכל תנאי. בחירה רב-דרכית מתבצעת כך שאין יותר מחלקת קוד אחת שתופעל, בהתבסס על הביטוי הראשון שמעריך לתוצאת true. אם אין ביטוי שמעריך לתוצאת true ויש statement else בסוף, אז גוף ה-else יופעל.

מקור: תיאור הקורס והמבחן של College Board AP

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

if (g >= 90) grade = 'A';
else if (g >= 80) grade = 'B';
else grade = 'C';

2.5

ביטויים בוליאניים מורכבים

סיילבוס

מטרת הלמידה 2.5.A: פיתוח קוד לייצוג ביטויים בוליאניים מורכבים והחלטת תוצאת הביטויים האלו.

2.5.A.1 מפעילים לוגיים ! (לא), && (ו) ו|| (או) משמשים עם ביטויים בוליאניים. הביטוי !a מחזיר true אם a הוא false ומחזיר false אחרת. הביטוי a && b מחזיר true אם גם a וגם b הם true ומחזיר false אחרת. הביטוי a || b מחזיר true אם a הוא true, b הוא true או שניהם, ומחזיר false אחרת. סדר העדיפות בהערכת מפעילים לוגיים הוא ! (לא), && (ו), ולאחר מכן || (או). ביטוי המכיל מפעילים לוגיים מחזיר ערך בוליאני.
2.5.A.2 הערכה מקוצרת מתרחשת כאשר תוצאה של פעולה לוגית המשתמשת ב&& או || יכולה להיקבע על ידי הערכת הביטוי הבוליאני הראשון בלבד. במקרה זה, הביטוי הבוליאני השני אינו מוערך.

מקור: תיאור הקורס והמבחן של College Board AP

ביצוע קצר-מעגל

מפעילים לוגיים משלבים תנאים: && (and – שניהם נכונים), || (or – אחד לפחות נכון), ! (not – הפוך). Java משתמשת בביצוע קצר-מעגל: && עצור אם הצד השמאלי לא נכון, ו|| עצור אם הצד השמאלי נכון – שימושי למניעת שגיאות, למשל if (n != 0 && total / n > 5).

2.6

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

סיילבוס

מטרת למידה 2.6.A: השוו בין ביטויים בוליאניים שוויונים.

2.6.A.1 שני ביטויים בוליאניים הם שוויונים אם הם מעריכים לערך זהה בכל המקרים. טבלאות אמת יכולות לשמש להוכחת שוויון ביטויים בוליאניים.
2.6.A.2 ניתן להחיל את חוק דה מורגן על ביטויים בוליאניים כדי ליצור ביטויים בוליאניים שוויונים. לפי חוק דה מורגן, הביטוי הבוליאני !(a && b) הוא שווה ל!a || !b והביטוי הבוליאני !(a || b) הוא שווה ל!a && !b.

מטרת למידה 2.6.B: פתח קוד להשוואת רפרנסים לאובייקטים באמצעות ביטויים בוליאניים וקבע את התוצאה של ביטויים אלו.

2.6.B.1 שני משתנים שונים יכולים להכיל רפרנסים לאותו אובייקט. רפרנסים לאובייקטים ניתנים להשוואה באמצעות == ו!=.
2.6.B.2 רפרנס לאובייקט יכול להיות מושווה לnull, באמצעות == או !=, כדי לקבוע האם הרפרנס מתייחס באמת לאובייקט.
2.6.B.3 מחלקות מגדירות לעיתים קרובות את שיטת equals שלהן, שהיא יכולה לשמש לציין הקריטריונים לשוויון בין שני אובייקטים מהמחלקה. השוויון בין שני אובייקטים נקבע ברוב המקרים באמצעות מאפיינים משני האובייקטים.
- הצהרת בלעדיות: החלפת שיטת equals היא מחוץ לתחום הלימודים בקורס ובמבחן AP Computer Science A.

מקור: תיאור הקורס והמבחן של College Board AP

חוקי דה מורגן כותבים מחדש שליליות: !(a && b) שווה ל!a || !b, ו!(a || b) שווה ל!a && !b. שני ביטויים בוליאניים הם שווים ערך אם הם נותנים את אותה תוצאה לכל קלט – טבלת אמת מוכיחה זאת. פישוט תנאים באופן זה הוא משימה נפוצה בבחינות.

2.7

לולאות while

סיילבוס

מטרת למידה 2.7.A: זיהוי מתי נדרש תהליך איטרטיבי (איטרציה) כדי להשיג תוצאה רצויה.

2.7.A.1 איטרציה היא סוג של חזרה. פקודות איטרציה משנות את זרימת הבקרה על ידי חזרה על קטע קוד מספר אפס או יותר כל עוד הביטוי הבוליאני השולט בלולאה מעריך לtrue.
2.7.A.2 לולאת אינסוף מתרחשת כאשר הביטוי הבוליאני בפקודת איטרציה מעריך תמיד לtrue.
2.7.A.3 גוף הלולאה של פקודת איטרציה לא יופעל אם הביטוי הבוליאני מעריך בהתחלה לfalse.
2.7.A.4 טעאות Off by one מתרחשות כאשר פקודת האיטרציה לולאת פעם אחת יותר מדי או פעם אחת פחות מדי.

מטרת למידה 2.7.B: פתח קוד לייצוג תהליכים איטרטיביים באמצעות לולאות while וקבע את תוצאת תהליכים אלו.

2.7.B.1 לולאת while היא סוג של פקודת איטרציה. בלולאות while, הביטוי הבוליאני מעריך לפני כל איטרציה בגוף הלולאה, כולל הראשונה. כאשר הביטוי מעריך לtrue, גוף הלולאה מופעל. הדבר נמשך עד שהביטוי הבוליאני מעריך לfalse, עתה האיטרציה מסתיימת.

מקור: תיאור הקורס והמבחן של College Board AP

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

שלושת סוגי הלולאות שונות במקום שבו התנאי נבדק

int i = 0;
while (i < 5) {
    System.out.println(i);
    i++;
}

חקור

עקוב אחר לולאת while

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

2.8

לולאות for

סיילבוס

מטרת למידה 2.8.A: פתח קוד לייצוג תהליכים איטרטיביים באמצעות לולאות for וקבע את תוצאת תהליכים אלו.

2.8.A.1 לולאת for היא סוג של פקודה איטרטיבית. בראש לולאת for ישנם שלושה חלקים: ההתחלה, הביטוי הבוליאני, והעדכון.
2.8.A.2 בלולאת for, פקודת ההתחלה מופעלת רק פעם אחת לפני הערכת הביטוי הבוליאני הראשונה. המשתנה הנאפס הוא משתנה בקרת הלולאה. הביטוי הבוליאני מוערך מיד לאחר אפסת משתנה בקרת הלולאה ולאחר מכן לאחר כל ביצוע של פקודת ההגברה עד שהוא false. בכל איטרציה, העדכון מתבצע לאחר ביצוע גוף הלולאה כולו ולפני הערכת הביטוי הבוליאני שוב.
2.8.A.3 לולאת for ניתן להפוך ללולאת while שקולה (ולהפך).

מקור: תיאור הקורס והמבחן של College Board AP

לולאת for מאגדת יזום, תנאי ועדכון בשורה אחת – הטובה ביותר כאשר יודעים את הספירה:

for (int i = 0; i < n; i++) {
    // runs n times, i = 0..n-1
}

קורס for וקורס equivalent ל-while מבצעים אותה עבודה; יכולים להמיר ביניהם.

קו הרכבה: לופים חוזרים על תהליך לכל פריט, כמו for ו-while

חקור

עקוב אחר לולאת for

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

2.9

בניית אלגוריתמי בחירה ואיטרציה שלמים

סיילבוס

מטרות למידה 2.9.A: פיתוח קוד עבור אלגוריתמים סטנדרטיים וחדשים (ללא מבני נתונים) וקביעת התוצאה של אלגוריתמים אלו.

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

מקור: תיאור הקורס והמבחן של College Board AP

שלב לופים ותנאים כדי לפתור בעיות אמיתיות – ספירה, סיכום, מציאת מקסימום או בדיקת מאפיין:

int max = arr[0];
for (int k = 1; k < arr.length; k++) {
    if (arr[k] > max) max = arr[k];
}

שני דפוסי שלמים שהמבחן בודק ישירות הם % ו/. כדי לקרוא את ספרותיו של מספר שלם אחד אחר השני, לקחת שוב ושוב n % 10 (הספרה האחרונה) ולאחר מכן n = n / 10 (להסיר אותה). לבדיקת חלוקיות, n % d == 0 פירושו שn מתחלק במספר שווה על ידי d. לשלב אותם עם סופר כדי למצוא את התדירות בה קריטריון מסוים מתקיים.

דפוסים סטנדרטיים כמו סכום רץ, נמדד או דגל (בווליאני שמקליט אם משהו קרה) חוזרים לאורך הקורס.

2.10

אלגוריתמים על מחרוזות

סיילבוס

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

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

מקור: תיאור הקורס והמבחן של College Board AP

חזור על מחרוזת על פי אינדקס כדי לעבד כל תווית:

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // count vowels, reverse, check for a substring, ...
}

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

2.11

איטרציה מקוננת

סיילבוס

מטרות למידה 2.11.A: פיתוח קוד ליצוג תהליכי איטרציה משובצים וקביעת תוצאת תהליכים אלו.

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

מקור: תיאור הקורס והמבחן של College Board AP

לופ תלוי מכיל לופ אחד בתוך השני; הלופ הפנימי מסתיים במלואו עבור כל מעבר של החיצוני. אם החיצוני רץ $n$ פעמים והפנימי $m$ פעמים, הגוף יעבוד $n\times m$ פעמים – הבסיס לעיבוד טבלאות ולהשוואת כל הזוגות.

2.12

ניתוח זמן ביצוע לא-פורמלי

סיילבוס

מטרות למידה 2.12.A: חישוב ספירות ביצוע פקודות והשוואה אי-פורמלית בזמן ריצה של פקודות איטרציה.

2.12.A.1 מניית ביצועי הוראה מציינת את מספר הפעמים שבהן הוראה מופעלת על ידי התוכנית. לעיתים קרובות נחשב מניית ביצועים באופן לא רשמי באמצעות עקב וניתוח של הוראות איטרטיביות.

מקור: תיאור הקורס והמבחן של College Board AP

קצבי גידול Big-O

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

כיצד זמן הביצוע גדל בהתאם למספר האלמנטים n — איך זמן הריצה גדל עם מספר האלמנטים n

מיומנות למבחן: עבור לופ תלוי, ניתן לנסח כמה פעמים ההצהרה הפנימית עוברת בהתבסס על גבולות הלופים – שאלת ריבוי נפוצה.

דוגמה מפורטת. כמה כוכבים הדפסה זו?

for (int i = 0; i < 4; i++)
    for (int j = 0; j < i; j++)
        System.out.print("*");

הלולאה הפנימית רצה i פעמים עבור כל לולאה חיצונית i: 0 + 1 + 2 + 3 = 6 כוכבים. כאשר הגבול הפנימי הוא המשתנה החיצוני, הסכום הכולל הוא סכום משולש $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ – כאן $\dfrac{4\times3}{2}=6$ – ולא הסכום המלא $n^2=16$ של לולאה מצומצבת מלבנית.

חקור

השווו כיצד אלגוריתמים גדלים

זמן ביצוע מתאר כיצד מספר הפעולות גדל עם גודל הקלט $n$. הגדילו את $n$ וצפו כיצד אלגוריתם ליניארי $O(n)$ מרחיק מאלגוריתם ריבועי $O(n^2)$.

2.12

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

ודאו תנאי גבון נכונים: השתמשו ב-< מול <= במתכוונות, ועקבו אחר האיטרציה הראשונה והאחרונה בכל לולאה (שגיאת off-by-one היא באג קלאסי).
בנו תנאים מורכבים עם &&, ||, ! וזכרו הערכת short-circuit (הניחו את בדיקת null ראשונה).
עקבו אחרי לולאות מצומצבות על ידי ספירה כמה פעמים הגוף הפנימי רץ בסך הכל.
בחרו במבנה הנכון – if/else if לטווחים, לולאה לחזרה – והימנעו מלולאה אינסופית על ידי עדכון משתנה הלולאה.
יישמו חוקי דה מורגן כאשר אתם פשוטים או מכחישים תנאי בוליאני.

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

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

מבחני עבר

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

אוספי נתונים