איך לתרגל שאלות נוסחת נסיגה במבני נתונים?

באתר prepd תמצאו שאלות נוסחת נסיגה במבני נתונים ממבחנים אמיתיים של אוניברסיטת בר-אילן. השאלות ממוינות לפי רמת קושי.

כמה שאלות נוסחת נסיגה יש במבני נתונים?

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

מה חשוב לדעת על נוסחת נסיגה לקראת מבחן במבני נתונים?

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

מבני נתונים - נוסחת נסיגה

מבני נתונים, אלגוריתמים וסיבוכיות

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

תתי-נושאים של רקורסיה

רמת קושי:

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

G_{0}, G_{1}, G_{2}, \dots

(ראו תרשים):

תרשים לשאלה

סעיף א' (10 נקודות)
הוכיחו באינדוקציה על המבנה כי גובה העץ

G_{i}

הוא

2 i

.

סעיף ב' (15 נקודות)
הוכיחו כי משפחת העצים הרקורסיביים מסדר שני היא משפחה מאוזנת.

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

O (lo g n)

, כאשר

n

הוא מספר הצמתים בעץ.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהנוסחת נסיגההוכחת נכונותסימון אסימפטוטיBig-Oעצים בינאריים

שאלה 1:
ברצוננו לערוך מסע לאורך של מסלול ישר מנקודת-התחלה

s = 0

לנקודת-סיום

f > 0

.

נתון מערך

p

של מיקומי-מלונות

0 < p_{1} < \dots < p_{n} = f

, כך שמלון

i

ממוקם בדיוק

p_{i}

קילומטרים מנקודת תחילת המסלול.

להלן סרטוט המסלול עבור

n = 6

:
[איור הושמט]

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

t

ימים (נתון

t < n

).
המאמץ שנדרש ביום-הליכה הינה

d^{2}

, כאשר

d

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

הערה: הבעיה ניתנת לפתרון בעזרת תכנות דינמי.

סעיף א' (10 נקודות)
בהינתן נקודת-התחלה

s = 0

ונקודת-סיום

f > 0

ומערך

p

של מיקומי-מלונות וכן

t

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

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

t

וביחס ל-

n

.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

תכנות דינמינוסחת נסיגהסיבוכיות זמןסיבוכיות מקוםמעקב אחר אלגוריתם

שאלה 3:
נתון מערך בגודל

n

.
רוצים למצוא את האיבר שהוא ה-

k

-י הקטן ביותר כאשר

k < \frac{n}{2}

.

מותר להשתמש ב SELECT רק על תתי מערכים בגודל לכל היותר \frac{n}{2}.

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

O (n)

לפתרון הבעיה המוצגת. נמקו תשובתכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיותסיבוכיות זמןרקורסיהנוסחת נסיגההוכחת נכונותחיפוש

נתון מערך

A

באורך

N

(אין חשיבות לתוכן

A

). נאמר כי

P = {[1, i_{1}], [i_{1} + 1, i_{2}], \dots, [i_{k - 1} + 1, N]}

היא חלוקה

k

-רציפה של מיקומי המערך

A

, כלומר היא מחלקת את המערך ל-

k

תתי מערכים (רציפים).

דוגמה: עבור מערך

A

באורך

14

ו-

k = 4

, חלוקה 4-רציפה אפשרית של המערך

A

היא:

P = {[1, 3], [4, 8], [9, 10], [11, 14]}

נניח כי לכל זוג

1 \leq i \leq j \leq n

נתונה פונקציית עלות כללית

C (i, j)

המחזירה את העלות של תת המערך מהאינדקס

i

עד האינדקס

j

(כולל), קרי

[i, j]

.

נגדיר את מחיר החלוקה

P

cost (P) = C (1, i_{1}) + C (i_{k - 1}, N) + ℓ = 1 \sum k - 1 C (i_{ℓ} + 1, i_{ℓ + 1})

כלומר, מחיר החלוקה הוא סכום העלויות של חלקי החלוקה ה-

k

רציפה.

להלן הגדרת בעיית החלוקה ה-

k

-רציפה מינימלית:
קלט: מערך

A

באורך

N

, מספר טבעי

k

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

C (i, j)

, המחזירה את עלות החלק

[i, j]

.
פלט: חלוקה

k

-רציפה

P = {[1, i_{1}], [i_{1} + 1, i_{2}], \dots, [i_{k - 1} + 1, N]}

של המערך

A

(ל-

k

תת מערכים רציפים), שעבורה מחיר החלוקה

cost (P)

הוא מינימלי מבין כל החלוקות ה-

k

-רציפות האפשריות.

הערה: הבעיה ניתנת לפתרון בעזרת תכנות דינמי.

סעיף א' (10 נקודות)
בהינתן מערך

A

בגודל

N

, מספר טבעי

k

ופונקציית עלות כללית

C (i, j)

,
כתבו נוסחה רקורסיבית לחישוב העלות של מחיר החלוקה

k

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

סעיף ב' (10 נקודות)
הראו אלגוריתם תכנות דינמי לפתירת בעיית החלוקה

k

-רציפה מינימלית.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

תכנות דינמינוסחת נסיגהסיבוכיות זמןסיבוכיות מקוםמעקב אחר אלגוריתם

יהי

A [1, \dots, n]

מערך של מספרים שלמים. לכל תת מערך

A [i, \dots, j]

עבור

1 \leq i \leq j \leq n

נגדיר את סכום תת המערך כ-

S_{i, j} = \sum_{ℓ = i}^{j} A [ℓ]

. שימו לב שתת המערך הוא תמיד רציף. להלן הגדרת בעיית מקסימום סכום תת מערך

A

קלט: מערך $A [1, \dots, n]$ מערך של מספרים שלמים.
פלט: סכום תת המערך המקסימלי של המערך $A$ . כלומר, $max_{i, j \in [n], i \leq j} S_{i, j}$ .

למשל, עבור הקלט

A = [2, - 4, 1, 9, - 6, 7, - 3]

סכום תת המערך המקסימלי של

A

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

O (n^{3})

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

O (n lo g n)

.
3. (10 נקודות) הוכיחו שזמן הריצה של האלגוריתם שמצאתם הוא

O (n lo g n)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2024 · סמסטר ב

★★★★★

סיבוכיות זמןBig-Oרקורסיהנוסחת נסיגההפרד ומשול

[1] ראינו כיצד להכפיל שני מספרים

X, Y

, כל אחד בעל

n

סיביות בשיטת הפרד ומשול בזמן

O (n^{2})

, כאשר כל מספר חולק לשני חלקים באורך

n /2

סיביות כל אחד. כאשר צמצמנו את מספר הקריאות הרקורסיביות מ 4 ל 3, הסיבוכיות ירדה ל

O (n^{1.58})

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

סעיף 5 נקודות.

א) הגדירו את

X

Y

כל אחד כפונקציה של שלושת חלקיהם

X_{1}, X_{2}, X_{3}

Y_{1}, Y_{2}, Y_{3}

ב) הראו איך ניתן לחשב את

X * Y

ע"י 9 קריאות רקורסיביות (הפרד) ועוד עבודת איסוף התוצאות שעלותה לינארית ב

n

(ומשול)
ג) מה הסיבוכיות של שיטה זו?
ד) בדומה למה שראינו במקרה של חלוקה ל2 חלקים, הראו איך, ע"י חישוב שלושת הערכים הבאים:

G = (X_{1} + X_{3}) (Y_{1} + Y_{3})

F = (X_{2} + X_{3}) (Y_{2} + Y_{3})

E = (X_{1} + X_{2}) (Y_{1} + Y_{2})

ניתן להוריד את מספר הקריאות הרקורסיביות מ9 ל 6.
ה) מה הנוסחה המתקבלת עבור הסיבוכיות?

(3 נקודות) בונוס: האם כדאי לחלק ל3?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2023 · סמסטר ב

★★★★★

סיבוכיותסיבוכיות זמןרקורסיהנוסחת נסיגהסימון אסימפטוטי

(3) שאלת בונוס: מהו

\frac{1}{2}!

(חצי עצרת)?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2022 · סמסטר ב

★★★★★

נוסחת נסיגהפונקציית גמא

נתונה קבוצה של

n

ערים

a_{1}, \dots, a_{n}

ומטריצה

C [i, j]

עבור

n \geq i, j \geq 1

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

a_{i}

a_{j}

(בלי תחנות ביניים). אם אין אפשרות לנסיעה ישירה מ

a_{i}

a_{j}

, אז

C [i, j] = \infty

. נרצה לבנות מטריצה

D [i, j]

שנותנת את עלות הנסיעה הזולה ביותר מ

a_{i}

a_{j}

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

רמז: תכנות דינמי.

א. (13) הגדירו נוסחה רקורסיבית

E (i, j, k)

עבור

n \geq k \geq 0

n \geq i, j \geq 1

, שתחזיר את עלות הנסיעה הזולה ביותר מ

a_{i}

a_{j}

, כאשר מותר להשתמש בתחנות ביניים רק מתוך הקבוצה

{1, 2, \dots, k}

; יש לכלול את תנאי העצירה בנוסחה.

ב. (6) הגדירו את המטריצה

D

שברצוננו לבנות במונחים של הנוסחה הרקורסיבית

E (i, j, k)

.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד א · 2022 · סמסטר ב

★★★★★

תכנות דינמיגרפיםמסלולים קצריםנוסחת נסיגה

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

מותר להפחית את N ב-1 להיות N-1
אם קיימים $a \leq b$ כך ש- $N = a \cdot b$ , אז ניתן להפחית את N להיות b

לדוגמא:

N = 100

, ניתן להגיע ל-1 ב-5 צעדים:

100 \to 10 \to 5 \to 4 \to 2 \to 1

הבעיה ניתנת לפתרון בתכנות דינמי.

א) תארו נוסחה רקורסיבית לפתרון הבעיה.

ב) תארו את מבנה הנתונים התומך בפתרון בתכנות דינמי. יש לתאר את סיבוכיות הזמן והמקום כפונקציה של N.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בר-אילןמועד ב · 2022 · סמסטר ב

★★★★★

תכנות דינמינוסחת נסיגהסיבוכיות זמןסיבוכיות מקום

יהי

A

מערך עם

n

איברים שונים. נאמר כי

A

מערך ממוין באופן מעגלי אם קיים

k

כך שאחרי הזזת האיברים

k

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

לדוגמא: המערך

A

הבא הוא מערך ממוין מעגלי כאשר

k = 2

.

א. כתוב/י אלגוריתם המקבל מערך

A

עם

n

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

i \in {1, \dots, n}

ומחזיר 0 אם האיבר הגדול ביותר במערך נמצא משמאל לאינדקס

i

(כולל, ז"א ב-

A [1 \dots i]

) אחרת, יחזיר 1. זמן הריצה

O (1)

.
ב. כתוב/י אלגוריתם המקבל מערך

A

עם

n

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

O (lo g n)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

חיפוש בינאריסיבוכיות זמןרקורסיהנוסחת נסיגההוכחת נכונות

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

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