הנדסה לאחור של קוד מומצא
// סקירה
שיעור 12: הנדסה לאחור של קוד מומצא
שיעור זה מכין לחלק הכנס שבו קיבלת קוד מומצא ואתה צריך להבין מה הוא עושה. Dry Run שיטתי, Pattern Matching מהיר, וניהול זמן תחת לחץ — כל הכלים במקום אחד.
✓נושאי שיעור 12 — הנדסה לאחור
- Dry Run ו-Symbol Table — 4 רמות קושי בסדר עולה
- שפות: Zenith, Kova, TalonScript, AxonLang
- Pattern Matching — זיהוי אלגוריתמים: Factorial, Fibonacci, Bubble Sort, Binary Search
- Edge Cases — מקרים גבוליים שמפילים
- רקורסיה, Multi-Function, Call Stack
- ניהול זמן תחת לחץ — מתי לצייר ומתי להמשיך
// מבוא
הנדסה לאחור של קוד מומצא
כתיבת קוד = מתחיל מבעיה, כותב פתרון. הנדסה לאחור = מתחיל מקוד מוכן — מוצא מה הוא עושה. זה בדיוק מה שנדרש במחשבון קרב.
💡 אנלוגיה — Dry Run כניתוח מתכון
קיבלת עוגה ואתה רוצה לדעת מה בה. אתה לא מכין עוגה — אתה טועם, מריח, ומנסה להסיק: "יש כאן קמח, חמאה, ב-180 מעלות..." Dry Run = טעימה שיטתית של הקוד. Symbol Table = הרשימה שאתה כותב.
4 רמות קושי בשיעור
| רמה | סוג שאלה | זמן מטרה |
|---|---|---|
| ⭐ רמה 1 | לולאות פשוטות, Symbol Table בסיסי | ~2 דקות |
| ⭐⭐ רמה 2 | לולאות מקוננות, תנאים, פלטים מרובים | ~3 דקות |
| ⭐⭐⭐ רמה 3 | רקורסיה, Multi-Function, Call Stack | ~5 דקות |
| ⭐⭐⭐⭐ רמה 4 | כנס-סטייל: כל הנ"ל + Edge Cases + שאלות מרובות | 7–10 דקות |
🎯 מפרטים מהירים — 4 שפות
Zenith: LET/SET · FOR i=a TO b · WHILE · FUNC/RETURN · PRINT · MOD · ^Kova: var · x:= · @ i in a..b · @@ cond · fn/ret · >>
TalonScript: x<~ · iter# i[a:b] (inclusive) · ?! · say · fn/ret · %%
AxonLang: DECL/UPDATE · EACH OVER a->b (exclusive!) · UNTIL · WHEN/OTHERWISE · DISPLAY
⚠️ inclusive vs exclusive — ההבדל הקריטי
TalonScript iter# i [2:6] = i=2,3,4,5,6 (כולל 6!) · AxonLang EACH i OVER 2->6 = i=2,3,4,5 (לא כולל 6!) · Zenith/Kova = inclusive בשני הקצוות.
✏תרגול — מבוא3 שאלות
שאלה 1
AxonLang:
EACH i OVER 0->3 — כמה iterations?✓ תשובה: א) 3 iterations — AxonLang EACH OVER a->b = exclusive. 0->3 = i=0,1,2. לא כולל 3!
שאלה 2
TalonScript:
iter# i [2:6] — כמה iterations?✓ תשובה: ד) 5 — TalonScript inclusive: i=2,3,4,5,6. AxonLang OVER 2->6 = 4 iterations (לא 6). ← ההבדל הכי חשוב!
שאלה 3
מה Pattern Matching בהקשר של Dry Run?
✓ תשובה: ג) — Pattern Matching = לראות result *= i ולדעת: זה פקטוריאל. לא צריך Dry Run מלא — מאיץ ומכוון.
// רמה 1 — 3 קטעי קוד
רמה ⭐ — לולאות בסיסיות
מטרה: 2 דקות לקטע קוד. Symbol Table פשוט. תרגל עד שזה אוטומטי.
קוד 1.1 — Zenith: פקטוריאל
// שפת Zenith — שאלות:
// א) מה הפלט? ב) מה עושה הקוד?
LET n = 5
LET result = 1
FOR i = 1 TO n
SET result TO result * i
END FOR
PRINT resultקוד 1.2 — Kova: לולאה עם תנאי
// שפת Kova — שאלות:
// א) מה הפלט? ב) מה ערך x אחרי iteration ה-3?
var x : num
var y : num
x := 100
y := 0
@ i in 1..6 {
? x % 3 == 0 { y := y + x }
x := x - 7
}
>> yקוד 1.3 — Zenith: WHILE עם מנה כפולה
// שאלות: א) מה הפלט? ב) כמה פעמים רץ הגוף?
LET x = 1
LET count = 0
WHILE x < 100
SET x TO x * 3
SET count TO count + 1
END WHILE
PRINT x
PRINT count! Off-by-one בWHILE ›
שואלים "מה x אחרי הלולאה?" — תשובה שגויה: 81. הלולאה בודקת תנאי לפני הגוף. אחרי x=243, בדיקה: 243<100=FALSE → יוצא. x אחרי הלולאה = 243, לא 81!
✏תרגול — רמה 13 שאלות
תרגול 1.1
Zenith:
LET x=2; FOR i=1 TO 4: SET x TO x*x. PRINT x — מה הפלט?✓ תשובה: ד) 65536 — x מוכפל בעצמו: 2→4→16→256→65536. x=x*x (לא x*2!)
תרגול 1.2
Kova:
s:=0; @ i in 1..5: s := s + i*i. >> s — מה s?✓ תשובה: א) 55 — 1²+2²+3²+4²+5² = 1+4+9+16+25 = 55
תרגול 1.3 — Edge Case
Zenith:
FOR i = 5 TO 3: PRINT i. END FOR. PRINT "done" — מה הפלט?✓ תשובה: א) "done" בלבד — start=5 > end=3 → לולאה לא רצה כלל! Edge Case קלאסי.
📌 סיכום ביניים — לולאות בסיסיות
עד כאן שלושה כלים: (1) לרשום את המשתנים בטבלה לפני הסיבוב הראשון, (2) לבדוק אם הגבול כולל את הקצה, (3) לזהות את הצעד — +1 הוא לינארי, *2 או *3 מקצר את מספר הסיבובים דרמטית.
לפני שממשיכים לרמה הבאה: קחו נשימה, ובדקו שאתם יודעים לענות "כמה פעמים רץ הגוף?" בלי להריץ הכול בראש.
// רמה 2 — 3 קטעי קוד
רמה ⭐⭐ — לולאות מקוננות ותנאים
מטרה: 3 דקות לקטע. Symbol Table עם כמה עמודות. תשים לב לפלטים מרובים.
קוד 2.1 — Zenith: משולש כוכביות
// שאלות: א) מה הפלטים? ב) מהו הדפוס הכללי?
FOR i = 1 TO 5
LET line = ""
FOR j = 1 TO i
SET line TO line + "*"
END FOR
PRINT line
END FORקוד 2.2 — Kova: Inversions
// arr = [3,1,4,1,5] שאלות: א) מה total? ב) מה עושה?
var arr[5]:num
arr[0]:=3; arr[1]:=1; arr[2]:=4; arr[3]:=1; arr[4]:=5
var total:num; total:=0
@ i in 0..4 {
@ j in 0..4 {
? arr[i] > arr[j] { total := total + 1 }
}
}
>> totalקוד 2.3 — TalonScript: שפה חדשה
══ TalonScript — מפרט מקוצר ══
x <~ expr ; assignment (x = expr)
iter# var [a:b] ; for var = a to b (inclusive!)
?! cond ?> block ; if cond then block
>? cond ?> block ; while cond
say expr ; print
fn f[params] ; function def / ret expr = return
%% = modulo ^^ = power ++ = string concat
>> and << = greater/less
// שאלות: א) מה הפלט? ב) מה עושה?
n <~ 10
sum <~ 0
iter# i [1:n] ?>
?! i %% 2 == 0 ?>
sum <~ sum + i
!?
!iter
say sum✏תרגול — רמה 23 שאלות
תרגול 2.1
מה Pattern:
a<~0; b<~1; iter# i [1:n]: c<~a++b; a<~b; b<~c?✓ תשובה: א) Fibonacci — a,b = b, a+b. זה ה-Pattern הקלאסי. לא צריך Dry Run מלא — ניתן לזהות ישירות!
תרגול 2.2
AxonLang:
DECL n=4; DECL total=0
EACH i OVER 1->n+1
EACH j OVER 1->i+1
total UPDATE total PLUS 1
END
END
DISPLAY total — מה total?✓ תשובה: א) 10 — i=1→j רץ 1 iter. i=2→2. i=3→3. i=4→4. סה"כ 1+2+3+4=10 = n*(n+1)/2
תרגול 2.3
Kova:
x:=5; y:=5; @@ x != y { x:=x-1 }; >> x — מה x?✓ תשובה: א) 5 — Edge Case! @@ x!=y: 5!=5=FALSE → 0 iterations מיד. x לא השתנה.
📌 סיכום ביניים — לולאות מקוננות
לולאה מקוננת = הפנימית מסתיימת במלואה בכל סיבוב של החיצונית. אם הפנימית קבועה — פשוט n × m. אם היא תלויה ב-i — סוכמים סדרה (n(n+1)/2 או n(n−1)/2), אבל רק אחרי שווידאתם את הגבולות על n = 3.
הטעות שחוזרת: להחיל נוסחה מוכרת על לולאה שהגבול שלה שונה במעט.
// רמה 3 — 3 קטעי קוד
רמה ⭐⭐⭐ — רקורסיה ו-Multi-Function
מטרה: 5 דקות. עץ קריאות + Symbol Table לכל frame. אל תנסה לעקוב "בראש".
קוד 3.1 — Zenith: היפוך מחרוזת רקורסיבי
FUNC head(s)
RETURN s[0]
END FUNC
FUNC tail(s)
RETURN s[1 TO s.SIZE - 1]
END FUNC
FUNC reverse(s)
IF s.SIZE = 0 THEN
RETURN ""
END IF
RETURN reverse(tail(s)) + head(s)
END FUNC
PRINT reverse("Hello")קוד 3.2 — TalonScript: Multi-Function Pipeline
fn square[x]
ret x * x
endfn
fn sum_squares[n]
total <~ 0
iter# i [1:n] ?>
total <~ total + square[i]
!iter
ret total
endfn
fn is_perfect_square[n]
?! n >> 0 ?>
iter# r [1:n] ?>
?! square[r] == n ?>
ret 1
!?
!iter
!?
ret 0
endfn
say sum_squares[4]
say is_perfect_square[16]
say is_perfect_square[15]קוד 3.3 — Zenith: רקורסיה עם 2 Base Cases
FUNC f(n)
IF n = 0 THEN RETURN 0 END IF
IF n = 1 THEN RETURN 1 END IF
IF n MOD 2 = 0 THEN
RETURN f(n / 2)
END IF
RETURN f(n - 1) + f(n - 2)
END FUNC
PRINT f(7)
PRINT f(8)✏תרגול — רמה 33 שאלות
תרגול 3.1
TalonScript:
fn power[base, exp]
?! exp IS 0 ?> ret 1 !?
?! exp %% 2 IS 0 ?>
half <~ power[base, exp DIV 2]
ret half * half
!?
ret base * power[base, exp MINUS 1]
endfn
say power[3,4] — מה הפלט?✓ תשובה: ג) 81 — power[3,4]: 4%2=0 → half=power[3,2]. power[3,2]: half=power[3,1]=3. power[3,2]=9. power[3,4]=81
תרגול 3.2 — Dry Run
FUNC g(n, acc)
IF n = 0 THEN RETURN acc END IF
RETURN g(n - 1, acc + n)
END FUNC
PRINT g(5, 0) — מה הפלט?✓ תשובה: א) 15 — Tail Recursion. g(5,0)→g(4,5)→g(3,9)→g(2,12)→g(1,14)→g(0,15)=15. מחשב 5+4+3+2+1.
תרגול 3.3
מה Tail Recursion? מה היתרון שלה?
✓ תשובה: ב) — Tail Recursion = הקריאה הרקורסיבית היא האחרונה. יתרון: TCO = אין Stack Overflow. Python לא מיישם TCO, אבל חשוב לדעת לגאמא.
🎯 דגש למבחן
רקורסיה תחת לחץ: אל תנסו להיות קומפיילר אנושי. אף אחד לא מחזיק בראש ארבע רמות קריאות בו-זמנית — וזה בדיוק המקום שבו נופלים על Off-by-one. במקום זה, קחו עשר שניות וציירו: בשרשרת (קריאה אחת בכל רמה) כתבו שורה-שורה עד תנאי העצירה ואז הציבו חזרה מלמטה למעלה. בקריאה כפולה (fib(n-1) + fib(n-2)) ציירו עץ קריאות קטן, ובקומבינציות ארוכות — טבלה עם עמודה לכל פרמטר. שתי נקודות שמצילות: תמיד לבדוק את תנאי העצירה על הקלט הקטן ביותר (n=0 ו-n=1), ולשים לב אם הפעולה מתבצעת לפני הקריאה הרקורסיבית או אחריה — זה משנה את סדר הפלט לגמרי.📌 סיכום ביניים — רקורסיה
פונקציה רקורסיבית = תנאי עצירה + צעד שמתקרב אליו. כל קריאה היא Stack Frame עם עותק פרטי של הפרמטרים, ולכן n של רמה אחת לא "נדרס" ברמה שמתחתיה.
אם אחרי דקה אתם לא רואים את התשובה — עברו לציור. זה מהיר יותר מלנחש.
// רמה 4 — כנס-סטייל
רמה ⭐⭐⭐⭐ — כנס-סטייל
מטרה: 7–10 דקות לכל קטע. קרא מפרט → מיפוי → Trace → ענה. שאלות מרובות לכל קטע.
קוד 4.1 — TalonScript: Bubble Sort
// arr = [9,4,7,2,6] 5 שאלות:
// 1) מה הפלט? 2) arr[2] לפני outer loop iter ה-3?
// 3) כמה swaps? 4) שם האלגוריתם? 5) Big-O?
arr[0]<~9; arr[1]<~4; arr[2]<~7; arr[3]<~2; arr[4]<~6
n <~ 5
iter# i [0:n-2] ?>
iter# j [0:n-2-i] ?>
?! arr[j] >> arr[j+1] ?>
tmp <~ arr[j]; arr[j] <~ arr[j+1]; arr[j+1] <~ tmp
!?
!iter
!iter
iter# k [0:n-1] ?>
say arr[k]
!iterקוד 4.2 — AxonLang: שפה חדשה
══ AxonLang — מפרט מקוצר ══
DECL <name> = <val> ; variable
<name> UPDATE <expr> ; assignment
EACH <var> OVER <a>-><b> ; for (EXCLUSIVE upper!)
UNTIL <cond>: ...END ; while
WHEN <cond>: ...END ; if
OTHERWISE: ...END ; else
DISPLAY <expr> ; print
OPERATORS: IS(==) GT(>) LT(<) PLUS MINUS TIMES DIV MOD POWER
// Collatz Sequence — 4 שאלות:
// 1) מה הפלט? 2) ערך n ביציאה? 3) כמה DIV? 4) מה עושה?
DECL n = 360
DECL steps = 0
UNTIL n GT 1:
WHEN n MOD 2 IS 0:
n UPDATE n DIV 2
END
OTHERWISE:
n UPDATE n TIMES 3 PLUS 1
END
steps UPDATE steps PLUS 1
END
DISPLAY n
DISPLAY stepsקוד 4.3 — Zenith: Binary Search Recursive
// arr=[2,5,7,10,13,18,25,40], 1-based
FUNC bsearch(arr, lo, hi, target)
IF lo > hi THEN RETURN -1 END IF
LET mid = (lo + hi) / 2
IF arr[mid] = target THEN RETURN mid END IF
IF arr[mid] < target THEN
RETURN bsearch(arr, mid + 1, hi, target)
END IF
RETURN bsearch(arr, lo, mid - 1, target)
END FUNC
PRINT bsearch(arr, 1, 8, 7) // שאלה: מה הפלט?
PRINT bsearch(arr, 1, 8, 100) // שאלה: מה הפלט?✏תרגול — כנס-סטייל4 שאלות
תרגול 4.1
AxonLang:
DECL a=2; DECL b=3; DECL res=0
EACH i OVER 0->4
WHEN i MOD 2 IS 0:
res UPDATE res PLUS a POWER i
END
OTHERWISE:
res UPDATE res MINUS b
END
END
DISPLAY res — מה הפלט?✓ תשובה: ב) -1 — EACH 0->4 = i=0,1,2,3. i=0: res+=2⁰=1 → res=1. i=1: res-=3 → -2. i=2: res+=2²=4 → 2. i=3: res-=3 → -1.
תרגול 4.2 — מה עושה
קוד:
while a != b: if a>b: a-=b else: b-=a — מה האלגוריתם?✓ תשובה: ד) Euclidean GCD — Pattern מוכר. מחשב GCD(a,b) = המחלק המשותף הגדול ביותר.
תרגול 4.3
מה Big-O: לולאה i=1..n, לכל i — Binary Search על n elements?
✓ תשובה: ג) O(n log n) — n × O(log n) = O(n log n). לולאה חיצונית * Binary Search.
תרגול 4.4 — Timer: 3 דקות!
fn collatz_len[n]
steps <~ 0
>? n ISNT 1 ?>
?! n %% 2 IS 0 ?>
n <~ n DIV 2
!?
?! n %% 2 ISNT 0 ?>
n <~ n TIMES 3 PLUS 1
!?
steps <~ steps PLUS 1
?,
ret steps
endfn
say collatz_len[10]
say collatz_len[1]מה שני הפלטים? ומה יקרה לn=0?✓ תשובה: ד) — collatz_len[10]: 10→5→16→8→4→2→1 = 6 steps. collatz_len[1]: n=1, ISNT 1=FALSE → 0 steps. n=0: 0≠1→נכנס, 0%2=0→n=0 DIV 2=0 → לולאה אינסופית! Bug!
// Pattern Matching + Edge Cases
Pattern Matching ו-Edge Cases
Pattern Matching = לראות קוד ולזהות מה האלגוריתם ללא Dry Run מלא. Edge Cases = מקרים גבוליים שחצי השאלות הקשות בונות עליהם.
טבלת Pattern Matching
| Pattern בקוד | אלגוריתם | מה לצפות |
|---|---|---|
| result=1; result*=i | פקטוריאל | result = n! |
| result=0; result+=i | סכום | 1+2+...+n |
| arr[j]>arr[j+1]: swap | Bubble Sort | מערך ממוין עולה |
| a,b=0,1; a,b=b,a+b | Fibonacci | סדרת פיבונאצ'י |
| n=n//2 (while n>0); count++ | Log₂ counter | מספר סיביות |
| while a!=b: if a>b: a-=b else: b-=a | Euclidean GCD | GCD(a,b) |
| lo,hi,mid: if arr[mid]==t: return mid | Binary Search | אינדקס האיבר |
| if n<=0: return 0; return n+f(n-1) | Sum recursive | n*(n+1)/2 |
5 Edge Cases הנפוצים ביותר
⚠️ Edge Cases שמפילים בכנס
- FOR/LOOP עם start > end → 0 iterations (לא אחת!)
- n=0 ב-recursive → האם Base Case מטפל? אם לא → Stack Overflow
- MOD/% עם 0 → Division by zero!
- מערך ריק → SIZE=0, arr[0] → שגיאה
- WHILE תנאי שקרי מיד → 0 iterations (לא אחת!)
מה עושים כשתקועים
| מצב | מה עושים | מה לא עושים |
|---|---|---|
| לא הבנת Syntax | חזור למפרט → מצא דוגמה | אל תנחש |
| תקוע אחרי 3 דקות | סמן "*" → עבור → חזור בסוף | אל תתעקש |
| הפלט לא הגיוני | בדוק off-by-one → trace מחדש | אל תמחק Symbol Table |
| רקורסיה מסבכת | בנה עץ קריאות → מלא leaves | אל תעקוב "בראש" |
✏תרגול — Pattern + Edge4 שאלות
תרגול 5.1 — Pattern
זהה אלגוריתם:
a<~0;b<~1; iter# i [1:n]: c<~a++b; a<~b; b<~c; say b✓ תשובה: ג) Fibonacci — a,b=b,a+b. Pattern מוכר! n=5 → 5 איטרציות → b=8=fib(6)=fib(n+1).
תרגול 5.2 — Edge Case
Zenith:
FUNC sum(n): IF n<=0 THEN RETURN 0 END IF. RETURN n+sum(n-1). PRINT sum(0)✓ תשובה: ג) 0 — n=0 → n≤0 → RETURN 0. Base Case תפס מיד!
תרגול 5.3
AxonLang:
DECL n=8; UNTIL n LTE 1: n UPDATE n DIV 2 END. DISPLAY n✓ תשובה: ד) 1 — 8→4→2→1. 1 LTE 1 = TRUE → יוצא כשn=1.
תרגול 5.4 — Kova
Kova:
fn sum(n:num)->num{?? n<=0{return 0;} return n+sum(n-1);} sum(-3)?✓ תשובה: ג) 0 — n=-3 ≤ 0 → RETURN 0. Base Case תופס את המספרים השליליים!
// אתגר מעשי
אתגר מעשי — הרצת קוד מומצא: לולאות
שיא השיעור: לבנות ולתקן מערכות אמיתיות — מפרשים, פרוטוקולים, מכונות. פתרו את החובה ואז את האתגר; ההגשה נבדקת אוטומטית מול מקרי-קצה נסתרים.
T2 · בסיסי250 נק'~12 דק'debug
תיקון באג — טווח לולאה (inclusive)
הפונקציה אמורה לסכם את ריבועי המספרים בטווח [a, b] כולל שני הקצוות. אך היא שבורה: הלולאה אינה כוללת את b (range(a, b) עוצר לפני b), ולכן sum_squares(1, 3) מחזיר 5 במקום 14. מצא ותקן. החזר את הגרסה המתוקנת.
// הקוד השבור לתיקון
def sum_squares(a: int, b: int) -> int:
tot = 0
for i in range(a, b): # באג כאן
tot += i * i
return totדוגמאות
sum_squares(1, 3) → 14
sum_squares(2, 2) → 4
הפתרון נשמר מקומית ומשותף עם עמוד „כתיבת קוד”.
T3 · בינוני400 נק'~30 דק'algorithmic
אינטרפרטר לולאות מקוננות
ממש מפרש לשפה זעירה עם לולאות מקוננות. פקודות (שורה לכל אחת): "SET v n" (קבע v=n) · "ADD v n" · "MUL v n" · "OUT v" (הוסף את v לפלט) · "LOOP k" ... "END" (חזור על הבלוק k פעמים; קינון מותר). משתנה שלא אותחל שווה 0. החזר את רשימת ערכי ה-OUT לפי הסדר. שים לב: LOOP 0 מדלג על הבלוק כולו.
דוגמאות
run_loops(['SET r 1','LOOP 3','MUL r 2','END','OUT r']) → [8]
run_loops(['SET s 0','LOOP 2','LOOP 3','ADD s 1','END','END','OUT s']) → [6]
הפתרון נשמר מקומית ומשותף עם עמוד „כתיבת קוד”.
שאלות תרגול ותשובות (10)
שאלה 1 · מה יודפס?
LET x = 1
LET count = 0
WHILE x < 100
SET x TO x * 3
SET count TO count + 1
END WHILE
PRINT x
PRINT count- א. 81 ו-4
- ב. 243 ו-5
- ג. 100 ו-5
- ד. 243 ו-4
תשובה: ב
x: 1→3→9→27→81→243. הלולאה מסתיימת רק אחרי שהתנאי נשבר, ולכן x=243 ו-count=5.
שאלה 2 · כמה פעמים רץ הגוף הפנימי?
SET c TO 0
LOOP i FROM 1 TO 4
LOOP j FROM i TO 4
ADD c BY 1
ENDLOOP
ENDLOOP
OUTPUT c- א. 16
- ב. 10
- ג. 6
- ד. 12
תשובה: ב
4+3+2+1 = 10 — הפנימית מתחילה ב-i, ולכן מתקצרת בכל סיבוב.
שאלה 3 · מה מחזירה f(5)?
FUNC f(n)
IF n <= 1 THEN
RETURN 1
END IF
RETURN n * f(n - 1)
END FUNC- א. 15
- ב. 25
- ג. 120
- ד. 60
תשובה: ג
עצרת: 5*4*3*2*1 = 120. פורסים עד תנאי העצירה ומציבים בחזרה למעלה.
שאלה 4 · מה מחזירה g(6)?
FUNC g(n)
IF n < 2 THEN
RETURN n
END IF
RETURN g(n - 1) + g(n - 2)
END FUNC- א. 8
- ב. 13
- ג. 5
- ד. 21
תשובה: א
פיבונאצ'י: 0,1,1,2,3,5,8 — g(6)=8. קריאה כפולה מחייבת עץ קריאות ולא שרשרת.
שאלה 5 · איזה אלגוריתם מזוהה כאן?
@ i in 0..|a|-2 {
@ j in 0..|a|-2-i {
? a[j] > a[j+1] {
SWAP a[j] a[j+1]
}
}
}- א. Binary Search
- ב. Bubble Sort
- ג. Selection Sort
- ד. Linear Search
תשובה: ב
השוואה והחלפה של שכנים בלולאה מקוננת — חתימה קלאסית של Bubble Sort.
שאלה 6 · כמה איטרציות יבצע החיפוש על מערך ממוין באורך 64 במקרה הגרוע?
lo := 0
hi := |a| - 1
@@ lo <= hi {
mid := (lo + hi) / 2
? a[mid] == t { return mid }
? a[mid] < t { lo := mid + 1 } ~ { hi := mid - 1 }
}- א. 64
- ב. 32
- ג. 7
- ד. 12
תשובה: ג
חיפוש בינארי: log₂(64)=6 חצאים, ועד 7 בדיקות במקרה הגרוע.
שאלה 7 · מה יודפס? (שימו לב לסדר: ההדפסה אחרי הקריאה הרקורסיבית)
FUNC p(n)
IF n = 0 THEN
RETURN
END IF
p(n - 1)
PRINT n
END FUNC
p(3)- א. 3 2 1
- ב. 1 2 3
- ג. 3 2 1 0
- ד. 1 2 3 בלולאה אינסופית
תשובה: ב
הקריאות יורדות עד 0 ורק בדרך חזרה מדפיסות — ולכן הסדר עולה.
שאלה 8 · מה קורה כשמריצים את הקוד על מערך ריק?
lo := 0
hi := |a| - 1
max := a[0]
@ i in 1..hi {
? a[i] > max { max := a[i] }
}- א. מחזיר 0
- ב. מחזיר את המקסימום כרגיל
- ג. נופל כבר בשורה של a[0]
- ד. נכנס ללולאה אינסופית
תשובה: ג
Edge case קלאסי: אתחול המקסימום מהאיבר הראשון קורס כשאין איברים בכלל.
שאלה 9 · מה יודפס?
LET s = 0
FOR i = 1 TO 5
IF i = 3 THEN
SET i TO 5
END IF
SET s TO s + i
END FOR
PRINT s- א. 15
- ב. 13
- ג. 12
- ד. 8
תשובה: ב
1+2, ואז i הופך ל-5 ומתווסף (8), ובסיבוב האחרון i=5... כלומר 1+2+5+5 = 13.
שאלה 10 · מה מחזירה h(4)?
FUNC h(n)
IF n = 0 THEN
RETURN 0
END IF
RETURN h(n - 1) + n * n
END FUNC- א. 16
- ב. 30
- ג. 10
- ד. 20
תשובה: ב
סכום ריבועים: 1+4+9+16 = 30 — פורסים עד 0 ומציבים בחזרה.