מחשבון קרב במיון: איך עובד המודול ואיך פותרים אותו בטבלת מעקב

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

מה זה מחשבון קרב ואיפה הוא מופיע

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

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

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

מה נותנים לכם ומה שואלים

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

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

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

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

SET  X, n      ; X = n
ADD  X, Y      ; X = X + Y
SUB  X, Y      ; X = X - Y
DEC  X         ; X = X - 1
JNZ  X, label  ; jump to label if X is not 0, else continue
HALT           ; stop

שיטת טבלת המעקב, צעד אחר צעד

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

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

נתחיל מתוכנית של תשע שורות, בשפה שהוגדרה למעלה. שאלה: מה הערך ב-A אחרי ההרצה, וכמה פעמים התבצעה שורה 4?

1       SET  A, 0
2       SET  B, 3
3       SET  C, 6
4 loop: ADD  A, C
5       SUB  C, B
6       DEC  B
7       JNZ  B, loop
8       ADD  A, C
9       HALT

התשובה: A שווה 10, ושורה 4 התבצעה שלוש פעמים. שימו לב לשני רגעים בטבלה. בביצוע 15 הערך של B הוא 0, ולכן JNZ לא קופצת והביצוע נופל לשורה 8. ובביצוע 16, שורה 8 מוסיפה 0, כך ש-A נשאר 10. מי שמדלג על שורה 8 כי "היא כבר לא משנה" מקבל את אותה תשובה במקרה הזה, אבל בתוכנית אחרת הדילוג הזה יעלה לו בשאלה.

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

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

1       SET  A, 2
2       SET  B, 3
3 loop: ADD  A, A
4       DEC  B
5       JNZ  B, loop
6       DEC  A
7       HALT

השאלה: מה הערך ב-A בסוף? הטבלה מציגה את המעקב הנכון מול מעקב של פותר שקורא את הקפיצה בקצרה:

התשובה הנכונה היא 15, והשגויה היא 7. ההבדל לא נובע מחישוב שגוי אלא ממשפט אחד: ההגדרה אומרת ש-JNZ קופצת בכל פעם ש-B אינו 0, ו-B הוא 1 אחרי הסיבוב השני, כלומר עדיין לא אפס. מי שרשם את הערך של B בשורת הקפיצה ראה את זה מיד. מי שעבד בראש הרגיש שהם כבר כמעט סיימו. יש גם טעות שנייה מאותה משפחה, והיא לעצור בסוף הלולאה ולשכוח את DEC A שבשורה 6: זה נותן 16 במקום 15.

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

אסטרטגיית זמן

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

איך מתרגלים

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

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

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