איך לתרגל שאלות memoization במבוא למדעי המחשב?

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

כמה שאלות memoization יש במבוא למדעי המחשב?

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

מה חשוב לדעת על memoization לקראת מבחן במבוא למדעי המחשב?

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

מבוא למדעי המחשב - memoization

תכנות, רקורסיה, מערכים, מחרוזות, עצים בינאריים ורשימות מקושרות

סטטיסטיקות מבחנים

רמת קושי:

בהינתן מחרוזת

s t = s_{0} s_{1} \dots s_{n - 1}

בעלת

n

תווים, תת מחרוזת של

s t

מוגדרת להיות מילה

w = s_{i_{1}} s_{i_{2}} \dots s_{i_{k}}

כך ש-

0 \leq i_{1} < i_{2} < \dots < i_{k} \leq n - 1

.

לדוגמה, קבוצת תתי המחרוזות של המחרוזת

ab c

היא:

{ϵ, a, b, c, ab, a c, b c, ab c}

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

aa

היא

{ϵ, a, aa}

, כאשר הסימון

ϵ

מייצג את המחרוזת הריקה, שהיא תת מחרוזת חוקית של כל מחרוזת (המחרוזת הריקה היא תת מחרוזת חוקית גם של המחרוזת הריקה).

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

s t = ab c d

המילה

a c

היא תת מחרוזת של

s t

, אבל

c a

היא לא תת מחרוזת של

s t

.

בשאלה זו נפתור את בעיית תת המחרוזת המשותפת הארוכה ביותר (Longest Common Subsequence, LCS). בבעיה זו נתונות שתי מחרוזות

s t_{1}, s t_{2}

ועלינו למצוא את האורך המקסימלי של מילה

w

אשר מהווה תת מחרוזת גם של

s t_{1}

וגם של

s t_{2}

.

דוגמאות:

$L C S (b x c g, ab c d e f g) = 3$ (כאן המחרוזת המשותפת הארוכה ביותר היא $b c g$ ואורכה 3).
$L C S (aaa, aba) = 2$ (כאן המחרוזת המשותפת הארוכה ביותר היא $aa$ ואורכה 2).
$L C S (a x, x a) = 1$ (כאן מחרוזת משותפת ארוכה ביותר היא למשל $a$ ואורכה 1).
$L C S (bina r y, co m p u t er) = 1$ (כאן המחרוזת המשותפת הארוכה ביותר היא $r$ ואורכה 1).
$L C S (aaaa, x y z) = 0$ (כאן המחרוזת המשותפת הארוכה ביותר היא המחרוזת הריקה ואורכה 0).

לאורך השאלה ניתן להניח כי שני הקלטים

s t_{1}, s t_{2}

לפונקציה הם משתנים חוקיים מטיפוס str (ייתכן כי מדובר במחרוזת ריקה).

א. (10 נק') נתון פתרון רקורסיבי לבעיית LCS. השלימו את הקוד המטפל במקרי הקצה ובמקרה הכללי בשורות החסרות.
הנחיה: אסור להשתמש ב-slicing.

ב. (10 נק') נסמן

m = l e n (s t_{1})

n = l e n (s t_{2})

ונניח לצורך פשטות כי

m = n

. נסמן ב-

S (n)

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

l cs_r ec

.

(i) הקיפו בעיגול את התשובה המתארת את גודל עץ הרקורסיה במקרה הטוב ביותר עבור האלגוריתם שהוצג בסעיף א' כתלות ב-

n

.

האפשרויות:

S (n) = O (1)

S (n) = Θ (lo g n)

S (n) = Θ (n)

S (n) = Θ (n lo g n)

S (n) = Θ (n^{2})

S (n) = Θ (n^{c})

עבור קבוע

c \geq 3

כלשהו,

c_{1} \cdot 2^{n} \leq S (n) \leq c_{2} \cdot 4^{n}

עבור קבועים

c_{1}, c_{2}

חיוביים כלשהם,

S (n) = Θ (n!)

.

(ii) הקיפו בעיגול את התשובה המתארת את גודל עץ הרקורסיה במקרה הגרוע ביותר עבור האלגוריתם שהוצג בסעיף א' כתלות ב-

n

.

ג. (5 נק') בסעיף זה נוסיף ממואיזציה למימוש הרקורסיבי משעיף א'. השלימו את הקוד של הפונקציה

l cs_m e m

למטה. הפונקציה מקבלת מחרוזת

s t

המורכבת מאותיות קטנות באנגלית.
הנחיות: (1) אסור להשתמש ב-slicing. (2) והפתרון צריך לרוץ בסיבוכיות זמן פולינומית בממוצע.

ד. (5 נק') נאמר שמחרוזת

s t

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

a ez

היא מונוטונית עולה, גם

aabb c

היא מונוטונית עולה, אבל

a d x c

היא לא מונוטונית עולה (מכיוון ש-

c

קטן למשל מ-

d

אבל מופיע אחריו).

השלימו את הקוד של הפונקציה longest_monotone למטה. הפונקציה מקבלת מחרוזת

s t

המורכבת מאותיות קטנות באנגלית ('a','b','c',...,'z'), ומחזירה את האורך המקסימלי של תת מחרוזת מונוטונית עולה של

s t

. דוגמאות:

$l o n g es t_m o n o t o n e (a x b y cz d) = 4$ (המחרוזת המונוטונית עולה הארוכה ביותר היא $ab c d$ ).
$l o n g es t_m o n o t o n e (aabaa) = 4$ (המחרוזת המונוטונית עולה הארוכה ביותר היא $aaaa$ ).
$l o n g es t_m o n o t o n e (x a) = 1$ (מחרוזת מונוטונית עולה ארוכה ביותר היא למשל $a$ ).

הנחיות: (1) על הפונקציה להשתמש בפונקציה

l cs_m e m

מהסעיף הקודם (גם אם לא מימשתם אותה). (2) על הפתרון שלכם להיות בעל סיבוכיות זמן ריצה פולינומית (אבל לא משנה מה דרגת הפולינום).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2026 · סמסטר א

★★★★★

רקורסיהמחרוזותתת-סדרהסיבוכיות זמןmemoization

הקלט הוא עץ חיפוש בינארי

t r ee

שבו

n

צמתים (מתקיים

n \geq 1

) בו המפתחות הם מספרים שלמים חיוביים יחודיים, ומספר שלם חיובי

k

.

נאמר שעץ חיפוש בינארי הוא

k

-מאוזן-מפתחות אם מתקיים לכל

i, j

אי-שליליים שונים שקטנים מ-

k

(

i \neq = j

0 \leq i, j < k

), ההפרש בין מספר המפתחות בעץ ששארית החלוקה שלהם ב-

k

היא

i

למספר המפתחות בעץ ששארית החלוקה שלהם ב-

k

היא

j

הוא

1, 0

או

- 1

.

באופן שקול, בכתיב מתמטי, עץ כזה מקיים לכל

0 \leq i, j < k

את הפסוק הבא:

{k ey \in t r ee ∣ k ey mod k = i} - {k ey \in t r ee ∣ k ey mod k = j} \in {- 1, 0, 1}

הערה: בכל סעיפי השאלה הניחו כי פעולות אריתמטיות הן מסיבוכיות זמן

O (1)

.

תזכורת: מחלקות

B ina r y_se a r c h_t r ee

ו-

T r ee_n o d e

מהכיתה.

סעיף א (7 נק'). השלימו את הפונקציה

i s_k ey_ba l an ce d 1 (t r ee, k)

. הפונקציה מקבלת מטיפוס

B ina r y_se a r c h_t r ee

ומספר שלם אי שלילי

k

, ומחזירה

T r u e

אם

t r ee

הוא

k

-מאוזן-מפתחות, אחרת מחזירה

F a l se

. הניחו כי נתונה לכם הפונקציה

co u n t_m o d k_e q_c (t r ee, k, c)

שבהינתן עץ

t r ee

מחזירה את מספר המפתחות בעץ ששארית החלוקה שלהם ב-

k

היא

c

, וכי סיבוכיות הזמן של פונקציה זו היא

O (f (n))

וכי אינה מקצה זיכרון עזר נוסף. על הפונקציה להיות מסיבוכיות זמן

O (f (n) \cdot k)

במקרה הגרוע, ולא להקצות זיכרון עזר נוסף.

סעיף ב (10 נק'). השלימו את הפונקציה

i s_k ey_ba l an ce d 2 (t r ee, k)

שמחזירה

T r u e

אם

t r ee

הוא

k

-מאוזן-מפתחות, אחרת מחזירה

F a l se

. יש להשתמש ברקורסיה ולהשלים גם את הפונקציה הרקורסיבית

r ec

. כמו כן על הפונקציה להיות מסיבוכיות זמן

O (n + k)

במקרה הגרוע. מותר לפונקציה

i s_k ey_ba l an ce d 2

להקצות זיכרון עזר (נוסף על הקלט) מסיבוכיות

O (k)

. הסבירו מדוע היא עומדת בדרישת הסיבוכיות הנ"ל.

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

n \leq k

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

O

), אחרת הותירו את התא ריק.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

עצים בינארייםעץ חיפוש בינארירקורסיהסיבוכיות זמןmemoization

בקורס מבוא למדעי המחשב, ישנן

k

קבוצות תרגול ו-

n

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

h e i g h t s

של

n

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

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

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

דוגמה: עבור

h e i g h t s = [1, 2, 3, 10, 20, 30, 100, 200, 250, 322]

k = 3

, התשובה היא

149

— מתקבלת מהחלוקה

[[1, 2, 3, 10, 20, 30, 100], [200, 250], [322]]

(הקבוצה הראשונה בהפרש

99

, השנייה

50

, השלישית

0

, סכום

149

).

סעיף א (12 נק'). השלימו את הקוד הרקורסיבי הבא לבעיה ונתחו את עץ הרקורסיה במקרה הגרוע, כתלות ב-

n

. אסור להשתמש ב-slicing.

ניתוח עץ הרקורסיה: נניח כי

k = lo g (n)

. ציינו את עומק עץ הרקורסיה המתקבל מהמימוש בסעיף א, במקרה הגרוע, כתלות ב-

n

.

סעיף ב (5 נק'). האם תוספת ממואיזציה למימוש הנ"ל תשפר (=תקטין) את סיבוכיות זמן הריצה במקרה הגרוע? הקיפו את תשובתכם, ובנוסף, אם היא תשפר תארו בקצרה את זיכרון העזר (ציינו במפורש את מפתחות המילון) ותנו חסם עליון הדוק על סיבוכיות זמן הריצה (במקרה הגרוע) שתתקבל לאחר השיפור (במונחי

O

, כתלות ב-

k, n

). אחרת נמקו בקצרה מדוע.

סעיף ג (8 נק'). בסעיף זה ננסה לשפר את סיבוכיות זמן הריצה של הבעיה באמצעות פתרון איטרטיבי. בהינתן

h e i g h t s

נגדיר את רשימת הפרשי הגבהים העוקבים,

d i f f

, באופן הבא:

i \in {0, \dots, n - 2} : d i f f [i] = h e i g h t s [i + 1] - h e i g h t s [i]

.

השלימו את מימוש

min_s u m_h e i g h t s_d i f f

שמקבלת קלט זהה לבעיה המתוארת, מבצע פתרון איטרטיבי, תוך שימוש ברשימה

d i f f

הנ"ל. הפתרון חייב להיות

O (n lo g n)

, ויש להשלים את מימוש

d i f f

עם list comprehension.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

רקורסיהmemoizationסיבוכיות זמןמערכים

בהינתן מחרוזת

s t = s_{0} s_{1} \dots s_{n - 1}

בעלת

n

תווים, תת מחרוזת של

s t

מוגדרת להיות מילה

w = s_{i_{1}} s_{i_{2}} \dots s_{i_{k}}

כך ש-

0 \leq i_{1} < i_{2} < \dots < i_{k} \leq n - 1

. לדוגמה,

a c

היא תת מחרוזת של

ab c d

, אך

c a

אינה.

בשאלה זו נפתור את בעיית תת המחרוזת המשותפת הארוכה ביותר (Longest Common Subsequence, LCS): בהינתן שתי מחרוזות

s t_{1}, s t_{2}

, למצוא את האורך המקסימלי של מילה

w

אשר מהווה תת מחרוזת גם של

s t_{1}

וגם של

s t_{2}

.

א. (10 נק') השלימו את הקוד הרקורסיבי הבא לבעיית LCS (אסור להשתמש ב-slicing):

ב. (10 נק') נסמן

m = l e n (s t_{1})

n = l e n (s t_{2})

, ונניח לצורך פשטות

m = n

. נסמן ב-

S (n)

את גודל עץ הרקורסיה (מספר הצמתים).

(i) מהו

S (n)

במקרה הטוב ביותר (כתלות ב-

n

)?

(ii) מהו

S (n)

במקרה הגרוע ביותר (כתלות ב-

n

)?

האפשרויות:

Θ (1)

Θ (lo g n)

Θ (n)

Θ (n lo g n)

Θ (n^{2})

Θ (n^{c})

עבור קבוע

c \geq 3

c_{1} \cdot 2^{n} \leq S (n) \leq c_{2} \cdot 4^{n}

Θ (n!)

.

ג. (5 נק') הוסיפו ממואיזציה למימוש הרקורסיבי, וקראו לפונקציה החדשה lcs_mem. אסור להשתמש ב-slicing, והפתרון צריך לרוץ בסיבוכיות זמן פולינומית בממוצע.

ד. (5 נק') נאמר שמחרוזת

s t

היא מונוטונית עולה אם תוויה מסודרים בסדר לקסיקוגרפי מהקטן לגדול. למשל

a ez

מונוטונית עולה,

aabb c

מונוטונית עולה, אך

a d x c

אינה (כי

c < d

אבל מופיע אחריו).

השלימו את הפונקציה longest_monotone(st) שמקבלת מחרוזת

s t

המורכבת מאותיות קטנות באנגלית, ומחזירה את האורך המקסימלי של תת מחרוזת מונוטונית עולה של

s t

. מותר (אך לא חובה) להשתמש בפונקציה lcs_mem. הפתרון צריך לרוץ בסיבוכיות זמן פולינומית בממוצע.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר א

★★★★★

רקורסיהמחרוזותתת-מחרוזתסיבוכיות זמןmemoization

במסלול של רכבת יש

n

תחנות.
מחירי הכרטיסים של הנסיעות מתחנה

i

לתחנה

j

(כאשר

j

גדול ממש מ-

i

) נתונים במערך דו-ממדי.

לדוגמא, מערך המחירים של הכרטיסים הוא זה:
שימו לב שהערכים בתאים בהם

i

גדול מ-

j

הם

- 1

כי מותר לנסוע רק בכיוון אחד (רק מ-

i

ל-

j

שמקיימים

j < i

, וכאשר הם שווים, המחיר הוא

0

, כמובן (נשארים בתחנה...))

00123 10 - 1 - 1 - 1 2150 - 1 - 1 380400 - 1 9050700

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

0

לאחרונה

n - 1

.

הנחות חשובות:
המערך תקין, ואכן כל התאים באלכסון הראשי הם 0 ומתחת לאלכסון הראשי הם

- 1

.
כל הנסיעות מתחנה

i

לתחנה

j

אפשריות. אין תאים ריקים.
אין צורך לבדוק את תקינות המערך.

בדוגמא לעיל, המחיר המינימלי הוא

65

, אפשר להגיע אליו אם נוסעים מתחנה 0 לתחנה 1 ומתחנה 1 לתחנה 3.

חתימת השיטה היא:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 85 · 2021 · סמסטר א

★★★★★

רקורסיהmemoizationמערך דו-ממדישיטות סטטיות

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

(k ey, v a l u e)

כאשר מפתחות מסודרים על פי ערכי ה-

k ey

של הצמתים. ניתן להניח כי לכל הצמתים בעץ מתקיים שהערך בצומת (

v a l u e

) הוא מספר שלם חיובי.

בהינתן עץ חיפוש בינארי נגדיר רמות בעץ באופן הבא:

l e v e l (r) = 1

אם

r

הוא שורש.

l e v e l (u) = l e v e l (v) + 1

אם

u

הוא בן של

v

. כלומר: השורש הוא ברמה 1, הבנים של השורש הם ברמה 2, הנכדים ברמה 3 וכן הלאה.

בהינתן צומת

u = (k ey, v a l u e)

בעץ בינארי נגדיר את המשקל (ונסמן:

w t

) של

u

להיות:

w t (u) = v a l u e \cdot l e v e l (u)

.

בהינתן עץ

T

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

בהינתן רשימה

w e i g h t s

של שלמים חיוביים נחשוב על הרשימה כמייצגת אוסף צמתים כאשר

w e i g h t s [i]

מייצג את הצומת

(i, w e i g h t s [i])

. לדוגמה, הרשימה

w e i g h t s = [10, 9, 9]

מייצגת את הצמתים

(0, 10), (1, 9), (2, 9)

.

בהינתן רשימת שלמים חיוביים נרצה למצוא את המשקל המינימלי של עץ חיפוש בינארי המכיל את הצמתים שב-

w e i g h t s

.

סעיף א. ממשו את הפונקציה

min_r ec

שנקראת מתוך פונקציית המעטפת

min_t r ee

, המקבלת כקלט רשימה

w e i g h t s

של שלמים חיוביים ומחזירה את המשקל המינימלי של עץ חיפוש בינארי המכיל את הצמתים שב-

w e i g h t s

על פי ההגדרה הנ"ל. על הפתרון להיות רקורסיבי. ניתן להניח כי

w e i g h t s

מכילה מספרים שלמים חיוביים בלבד.

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

n

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

1. זמן הריצה של הפונקציה הוא פולינומיאלי, כלומר קיימים קבועים

c \geq 1, n_{0}

כך שלכל

n \geq n_{0}

זמן הריצה במקרה הגרוע ביותר הוא לכל היותר

n^{c}

.

2. זמן הריצה של הפונקציה הוא אקספוננציאלי, כלומר קיימים קבועים

c > 1, n_{0}

כך שלכל

n \geq n_{0}

זמן הריצה במקרה הגרוע ביותר הוא לפחות

c^{n}

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2021 · סמסטר א

★★★★★

עצים בינארייםעץ חיפוש בינארירקורסיהסיבוכיות זמןmemoization

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

d = {’a’: 1, ’b’: 2}

מייצג את אחד של

a

ושני תווים של

b

.

נתונה הפונקציה הרקורסיבית הבאה אשר בהינתן מילון כנ"ל שמתואר מעלה, מחזירה את מספר המחרוזות אשר ניתן להרכיב מהתווים במילון (לא בהכרח כולם):

לדוגמה: עבור

d = {’a’: 1, ’b’: 1}

הפונקציה תחזיר

5

, כי יש

5

מחרוזות אפשריות:

ϵ

(ריקה),

a

b

ab

ba

.

א. ציירו את עץ הרקורסיה עבור הקלט

d = {’a’: 1, ’b’: 2}

. בכל צומת רשמו מה הקלט לקריאה שמיוצגת ע"י הצומת.

ב. נרצה לשמות את הפונקציה

n u m_s t r

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

ג. נרצה לשמות את הפונקציה

n u m_s t r

כך שתחסוך קריאות רקורסיביות ע"י שימוש במילון

m e m_d i c t

לממואיזציה. השלימו את הקוד.

ד. נרצה לשמות את הפונקציה

n u m_s t r

מתחילת השאלה כך שתקבל קלט נוסף

k

שהוא מספר סעיף טבעי. הפונקציה תספור רק את המחרוזות שאורכן בדיוק

k

ותחזיר את מספרן. תארו בסבלה הבאה את השינויים הנדרשים.

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

" r a d a r "

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

n u m_s t r

הנתונה בתחילת השאלה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2020 · סמסטר ב

★★★★★

רקורסיהמחרוזותmemoizationפלינדרום

בהמשך לפונקציית edit_distance:

ג. האם ממואיזציה תעזור לשיפור סיבוכיות הקוד?

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

נמקו והסבירו, אך אין צורך לכתוב את הקוד עצמו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2020 · סמסטר א

★★★★★

רקורסיהmemoizationסיבוכיות זמןמחרוזות

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

+

ואת העלים בסימן

∙

הטבלה הבאה מפרטת את כל העצים הבינארים המלאים בעלי

n

קודקודים פנימיים כאשר

0 \leq n \leq 3

.

כמפורט בטבלה, כאשר

n = 0

וגם כאשר

n = 1

יש בדיוק עץ בינארי מלא אחד. כאשר

n > 1

, פרט לשורש העץ, שהוא חייב להיות קודקוד פנימי, יש עוד

n - 1

קודקודים פנימיים. חלקם משמאל לשורש, והשאר מימין.

סעיף א' (15 נקודות):

השלימו בדף התשובות את הגדרת הפונקציה הרקורסיבית

int h(int n)

המקבלת מספר

0 \leq n

ומחזירה את מספר העצים הבינארים המלאים שיש בהם

n

קודקודים פנימיים.

יש להניח שהמספר

n

בקלט הוא מספר אי־שלילי. בסעיף זה אין לקרוא לפונקציות עזר נוספות. קטע הקוד הבא מדפיס את השורה: 42 14 5 2 1 1.

סעיף ב' (10 נקודות):

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

h (n)

שחושבו בשלבים קודמים של מהלך החישוב. השלימו את הגדרת הפונקציה

h

שמקבלת מספר

0 \leq n

ומחזירה את מספר העצים הבינארים המלאים שיש בהם

n

קודקודים פנימיים.

יש להניח שהמספר

n

בקלט הוא מספר אי־שלילי.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בן גוריוןמועד א · 2020 · סמסטר א

★★★★★

רקורסיהmemoizationיעילותסיבוכיות זמןסיבוכיות מקוםעצים בינאריים

במשחק "נים" משתתפים שני שחקנים: שחקן א' ושחקן ב'. בתחילת המשחק, ניצבות לפניהם

n

ערימות נפרדות של גפרורים, כאשר בכל ערימה מספר נתון של גפרורים. הערימות ממוספרות מ-0 עד

n - 1

. מספר הגפרורים בערימה

i

בתור

a_{i}

.

כל שחקן בתורו (שחקן א' מתחיל את המשחק) בוחר ערימה לא ריקה של גפרורים מבין

n

הערימות, ומוריד ממנה גפרור אחד. הערימות ממוספרות מ-0. מספר מוגבל של גפרורים לבחירה: לפחות גפרור אחד, אך לא יותר ממספר הגפרורים שבערימה.

המשחק נגמר כאשר לא נותרו יותר גפרורים (כלומר

a_{i} = 0

לכל

i

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

דוגמה: עבור ערימות בערימות הוא

n = 3

, מספר הגפרורים בערימות הוא

a_{0} = 1, a_{1} = 1, a_{2} = 3

1. שחקן א' פותח את המשחק, ומוריד מערימה 2 את כל שלושת הגפרורים. כעת

a_{0} = 1, a_{1} = 1, a_{2} = 0

.
2. שחקן ב' מוריד מערימה 1 גפרור אחד. כעת

a_{0} = 1, a_{1} = 0, a_{2} = 0

.
3. שחקן א' מוריד מערימה 0 גפרור אחד. כעת לא נותרו גפרורים, ולכן שחקן א' ניצח.

נגדיר את מצב הערימות

a

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

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

א. ציירו את עץ הרקורסיה עבור

n = 2

a_{0} = 2

a_{1} = 1

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

ב. השלימו את הפונקציה can_win_nim אשר מקבלת רשימה

l s t

בגודל חיובי

n

(גם מספר הגפרורים ב-

n

הערימות), ומחזירה True אם מצב הערימות

l s t

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

דוגמת הרצה:

החזירה למצב קודם צריכה להיות לפני ה-return הסופי.

ג. כעת נרצה לשפר את הפונקציה מסעיף ב' ע"י שימוש ב-memoization, לצורך שיפור זמן הריצה.

i. השלימו את החימוש של הפונקציה המעטפת, שקוראת לפונקציה הרקורסיבית:

ii. ציינו עד 5 שינויים/תוספות לקוד הרקורסיבי בסעיף ב', כך שיעבוד עם memoization. לכל שינוי, רשמו את מספר השורה ואת התוספת:

1. שינוי מספר שורה: 4 / תוספת אחרי מספר שורה:
if tuple(lst) in d: return d[tuple(lst)]

2. שינוי מספר שורה: 1 / תוספת אחרי מספר שורה:
def can_win_nim(lst, d)

3. שינוי מספר שורה: 8 / תוספת אחרי מספר שורה:
if not can_win_nim(lst, d):

4. שינוי מספר שורה: כמה / תוספת אחרי מספר שורה:
lst[i] += 1; d[tuple(lst)] = True

5. שינוי מספר שורה: 12 / תוספת אחרי מספר שורה:
d[tuple(lst)] = False

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2019 · סמסטר ב

★★★★★

רקורסיהרקורסיה עם מעקבmemoizationמעקב אחר קוד

שאלות memoization במבוא למדעי המחשב עם פתרונות

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