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

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

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

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

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

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

מבוא למדעי המחשב - רקורסיה עם מעקב

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

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

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

רמת קושי:

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

N

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

5 N

השפית הידועה מדאם כרובית אחראית על ארוחת הערב החגיגית ועליה לתכנן מראש אילו מנות להגיש לכל אחד מ-

N

השולחנות. לשם כך יש להתחשב באילוצים הבאים:

כל סועד סימן מראש שלוש מנות מתוך תפריט של $K$ מנות, כאשר לכל מנה יש מספר שונה החל מ-0 ועד $K - 1$ . יש להכין לו בדיוק מנה אחת מתוך השלוש שסימן.
משיקולים קולינריים, ישנן מנות שלא יכולות להיות יחד באותו שולחן. אילוצים אלו מתוארים במטריצת אילוצים בגודל $K \times K$ , בה האיבר במקום $[i] [j]$ הוא 0 אם מנה $i$ לא יכולה להיות עם מנה $j$ באותו שולחן, ו-1 אם הן יכולות להיות יחד.

עליכם לממש את הפונקציה הבאה:

int e x am_q 4 (int ma t 1 [] [3], int ma t 2 [K] [K]);

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

ma t 1

(שורות 0 עד 4 הסועדים בשולחן הראשון, שורות 5 עד 9 הסועדים בשולחן השני, וכך הלאה), ואת מטריצת האילוצים

ma t 2

.

על הפונקציה להחזיר את מספר המנות השונות המינימלי שיכול לקיים את כל האילוצים. אם לא קיימת אפשרות העונה על כל האילוצים יש להחזיר -1.

למשל, עבור 2 שולחנות ו-6 מנות, אם בחירת הסועדים היא:

ומטריצת האילוצים היא:

כלומר כל המנות יכולות להיות על אותו שולחן, מלבד מנות 0 ו-5 שלא יכולות להיות על אותו שולחן.

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

הטכניוןמועד א · 2025 · סמסטר קיץ

★★★★★

רקורסיהרקורסיה עם מעקבמערכיםמערך דו-ממדימעקב אחר קוד

שאלה :4 ] 25 נקודות [

יוסי מנסה לתכנן טיול מסביב לעולם דרך מדינות שנמספרות

0, 1, 2, 3, \dots, N - 1

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

N \times N

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

i

למדינה

j

אזי routes[i][j] יהיה מחיר המעבר. אם לא קיים מעבר, routes[i][j] יהיה

0

.

שימו לב שהמטריצה לא חייבת להיות סימטרית, כלומר ייתכן שקיים מעבר מ

i

j

אך לא קיים מעבר מ

j

i

, או שהמחיר שונה.

עליכם לממש את הפונקציה הבאה:

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

0

אם לא קיים מסלול כזה.

למשל, עבור

N = 3

(3 מדינות) ומטריצת המעברים הבאה:

	$j = 0$	$j = 1$	$j = 2$
$i = 0$	0	200	300
$i = 1$	50	0	25
$i = 2$	150	0	0

יוסי יכול לטייל במסלול הבא: לצאת ממדינה 1 למדינה 2 (עולה 25) ואז ממדינה 2 למדינה 0 (עולה 150). סה"כ יוסי ישלם 175.

מסלול אחר יכול להיות ממדינה 0 למדינה 1 (עולה 200) וממדינה 1 למדינה 2 (עולה 25). סה"כ המחיר 250, יקר יותר מהאפשרות הראשונה.

קיימים עוד מסלולים, כולם יקרים יותר.

עבור 3 מדינות ומטריצת המעברים הבאה:

	$j = 0$	$j = 1$	$j = 2$
$i = 0$	0	200	0
$i = 1$	0	0	0
$i = 2$	0	100	0

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

הטכניוןמועד ב · 2025 · סמסטר קיץ

★★★★★

רקורסיהרקורסיה עם מעקבמערך דו-ממדיגרפיםמעקב אחר קוד

נניח שהמחלקה node שלהלן מממשת צומת בעץ בינרי.

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

0

.

בין השיטות נתונות השיטות what הבאות:

נתון העץ הבינרי הבא, ששורשו הוא root:

         3
       /   \
      2     7
     / \     \
    9   8     5
   /   / \
  6   1   4
       \
       10

.

סעיף א (4 נקודות):
איזה ערך תחזיר השיטה what אם נקרא לה עם הפרמטרים הבאים: השורש root לעיל והערך

c = 1

?

סעיף ב (6 נקודות):
מה מבצעת השיטה what באופן כללי כשהיא מקבלת כפרמטר שורש של עץ בינרי root ובהינתן לה מספר שלם

c

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

סעיף ג (6 נקודות):
נשנה עתה את השורה החמישית מהסוף בשיטה השנייה, השורה שמסומנת בסופה בכוכביות.
במקום שהשורה תהיה:
if (ans == 0 && root.getRightSon() != null)
נשנה אותה לשורה:
if (root.getRightSon() != null)
כלומר נמחק את החלק הראשון של התנאי ונותיר רק את השני.
עליכם לצייר עץ בעל מספר צמתים מינימלי, וכתבו ערך עבור הפרמטר

c

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהעצים בינארייםמעקב אחר קודרקורסיה עם מעקבשיטות סטטיותOverloading

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

n

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

(0, 0)

ועד לתא האחרון שהוא התא

(ma t . l e n g t h - 1, ma t . l e n g t h - 1)

, כאשר אפשר לעבור מתא

(i, j)

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

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

דוגמאות:

נתונים המערכים הבאים:

בכל אחד מהמערכים

A

ו-

B

יש שני מסלולים מהתא הראשון לאחרון:

המסלול הראשון עובר בתאים [0][0] -> [0][1] -> [1][1]
המסלול השני עובר בתאים [0][0] -> [1][0] -> [1][1]

במערך

A

המספר המקסימלי במסלול הראשון הוא

4

, והמספר המקסימלי במסלול השני הוא

4

. לכן יוחזר

4

.
במערך

B

המספר המקסימלי במסלול הראשון הוא

3

, והמספר המקסימלי במסלול השני הוא

4

. לכן יוחזר

3

אם המערכים הם:

D =
4   5   8   2
3  12  16   7
13  1  10  14
15 11   9   6

C =
4   5   8   2
3  12   7  16
13  1  10  14
15 11   9   6

אז במערך

C

המספר שיוחזר יהיה

10

, שהוא המקסימום במסלול המסומן, והוא המינימלי מבין כל ערכי המקסימום של כל המסלולים האחרים.
אבל אם נחליף את התאים [1][3] שבו יש

16

ואת [1][2] שבו יש

7

(זה המערך

D

), המספר שיוחזר יהיה

12

, שהוא המקסימום במסלול המסומן. שימו לב ש-

12

הוא המקסימום גם במסלול הזה: [0][0] -> [0][1] -> [1][1] -> [1][2] -> [2][2] -> [2][3] -> [3][3]

אם המערכים הם:

D =
4   1   9   3  25
24 23   2  21   5
13 12  15  16  22
17 11  18  19  20
10 14   8   7   6

C =
4   1   9   3  25
24 23  22  21   5
13 12  15  16  14
17 11  18  19  20
10  2   8   7   6

אז במערך

C

המספר שיוחזר יהיה

21

, שהוא המקסימום במסלול המסומן, והוא המינימלי מבין כל ערכי המקסימום של כל המסלולים האחרים. שימו לב ש-

21

הוא המקסימום בעוד כמה מסלולים. לדוגמא:
1. [0][0] -> [0][1] -> [0][2] -> [0][3] -> [1][3] -> [3][2] -> [3][3] -> [3][4] -> [4][4]
2. [0][0] -> [0][1] -> [0][2] -> [0][3] -> [1][3] -> [3][2] -> [2][2] -> [2][3] -> [2][4] -> [3][4] -> [4][4]
אבל אם נחליף את התאים

14, 22, 2

במערך (זה המערך

D

), המספר שיוחזר יהיה

15

, שהוא המקסימום במסלול המסומן.

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

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

מותר לשנות את המטריצה במהלך השיטה, אבל המטריצה צריכה לחזור לקדמותה לאחר ביצוע השיטה.
המטריצה בהכרח ריבועית. כלומר, מספר השורות שווה למספר העמודות.
מותר להשתמש בשיטות Math.max ו- Math.min מהמחלקה Math וכן בקבועים Integer.MAX_VALUE, Integer.MIn_VALUE מהמחלקה Integer.
מותר להשתמש בהעמסת-יתר (Overloading).
אין צורך לדאוג ליעילות השיטה! אבל כמובן שצריך לשים לב לא לעשות קריאות רקורסיביות מיותרות!
אל תשכחו לתעד את מה שכתבתם!

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרקורסיה עם מעקבמערך דו-ממדיחיפוש בינאריגרפים

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

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

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

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

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

021122334154617381

אז המסלול היחיד האפשרי הוא:

מתחילים בתא 0. לוקחים את המטיל שמשקלו 2. בצעד הראשון אפשר ללכת רק ימינה, והקפיצה היא בגודל 3 = הסכום של מספר הצעד (1) + הערך בתא (2). קופצים לתא 3. בתא 3 לוקחים את המטיל שמשקלו 3. הקפיצה הבאה האפשרית היא בגודל 5 = הסכום של מספר הצעד (2) + הערך בתא (3). לכן אי אפשר לקפוץ שמאלה, אלא רק ימינה ומגיעים מתא 3 לתא 8 שהוא התא האחרון במערך. לוקחים את המטיל האחרון שמשקלו 1.

סה"כ המשקל של מטילי הזהב שנלקחו הוא 6 (2 בתא 0, 3 בתא 3, 1 בתא 8,

2 + 3 + 1 = 6

).

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

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

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

דוגמא נוספת:

arr = 09142737445461738192101113122131149152

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

1. 0 -- 10 -- 13 -- 9 -- 15 sum = 15
2. 0 -- 10 -- 13 -- 9 -- 3 -- 15 sum = 22
3. 0 -- 10 -- 7 -- 13 -- 8 -- 2 -- 15 sum = 24
4. 0 -- 10 -- 7 -- 1 -- 9 -- 2 -- 15 sum = 28

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

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

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

שימו לב:

אם השיטה שתכתבו רק תחזיר את המשקל המקסימלי, אבל לא תדפיס את המסלולים, התשובה תקבל לכל היותר 17 נקודות.
מותר לשנות את המערך במהלך השיטה, אבל המערך צריך לחזור לקדמותו לאחר ביצוע השיטה.
מותר להשתמש בשיטות Math.max ו- Math.min מהמחלקה Math וכן בקבועים Integer.MAX_VALUE, Integer.MIN_VALUE מהמחלקה Integer.
מותר להשתמש בהעמסת-יתר (Overloading).
אין צורך לדאוג ליעילות השיטה! אבל כמובן שצריך לשים לב לא לעשות קריאות רקורסיביות מיותרות!
אל תשכחו לתעד את מה שכתבתם!

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרקורסיה עם מעקבמערכיםשיטות סטטיותOverloadingמעקב אחר קוד

תזכורת מתמטית:
א. גודל (size) של קבוצה (set) הוא מספר האיברים שיש בה.
למשל, בקבוצה

{- 5, 2, 3, 6}

יש ארבעה איברים, ולכן גודלה הוא 4.
ב. קבוצות זרות ומשלימות (disjoint and complementary sets) של המערך הן קבוצות שאין להן איבר משותף, והאיחוד שלהן הוא כל איברי המערך. במילים אחרות, כל איבר במערך נמצא בדיוק באחת משתי הקבוצות.
לדוגמא: אם המערך a הוא:

  0   1   2   3   4
  1   2   0   3  -1

אז יש הרבה קבוצות זרות ומשלימות במערך זה. הנה כמה מהן:
1.

{1, 2, 0, 3}

{- 1}

{1, 2, - 1}

{0, 3}

{0, 3}

{1, 2, - 1}

{1, 2, 0, 3, - 1}

\emptyset

{1, 3}

{2, 0, - 1}

{2, 0, - 1}

{1, 3}

{1}

{2, 0, 3, - 1}

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

לדוגמא:
במערך a, החלוקות 2, 3, 4, 7 שציינו לעיל מקיימות את התנאי שההפרש בין הסכומים של שתי הקבוצות הוא בדיוק ההפרש בין הגדלים שלהן.
בחלוקה 2 לעיל:

A = {1, 2, - 1}

B = {0, 3}

בקבוצה A גודל הקבוצה הוא 3 סכום האיברים 2
בקבוצה B גודל הקבוצה הוא 2 סכום האיברים הוא 3
ואכן ההפרש בין הסכומים של שתי הקבוצות הוא 1 (

∣3 - 2∣ = 1

), וגם ההפרש בין מספר האיברים של שתי הקבוצות הוא 1 (

∣2 - 3∣ = 1

בערך מוחלט זה 1).

בחלוקה 3 לעיל:

A = {0, 3}

B = {1, 2, - 1}

בקבוצה A גודל הקבוצה הוא 2 סכום האיברים 3
בקבוצה B גודל הקבוצה הוא 3 סכום האיברים הוא 2
ההפרש בין הסכומים הוא 1 וההפרש בין הגדלים הוא 1.

בחלוקה 4 לעיל:

A = {1, 2, 3, 0, - 1}

B = \emptyset

בקבוצה A גודל הקבוצה הוא 5 סכום האיברים 5
בקבוצה B גודל הקבוצה הוא 0 סכום האיברים הוא 0
ההפרש בין הסכומים הוא 5 וההפרש בין הגדלים הוא 5.

בחלוקה 7 לעיל:

A = {1}

B = {2, 0, 3, - 1}

בקבוצה A גודל הקבוצה הוא 1 סכום האיברים 1
בקבוצה B גודל הקבוצה הוא 4 סכום האיברים הוא 4
ההפרש בין הסכומים הוא 3 וההפרש בין הגדלים הוא 3.

אפשר לראות כי בחלוקה 1 לעיל:

A = {1, 2, 0, 3}

B = {- 1}

בקבוצה A גודל הקבוצה הוא 4 סכום האיברים 6
בקבוצה B גודל הקבוצה הוא 1 סכום האיברים הוא -1
ההפרש בין הסכומים הוא 7 וההפרש בין הגדלים הוא 3.
לכן החלוקה הזו לא מקיימת את התנאי, ולכן היא לא תודפס ולא תיספר.

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

1 2 0         sum = 3 count = 3
3 -1          sum = 2 count = 2

2 0 3 -1      sum = 4 count = 4
1             sum = 1 count = 1

וכן הלאה הדפסה של שאר החלוקות... הסדר לא משנה!

אם המערך b הוא:

  0   1   2   3   4
  1   2   0   4  -1

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

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

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

שימו לב,

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרקורסיה עם מעקבמערכיםשיטות סטטיותOverloading

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

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

לדוגמא, עבור 7 = sum השיטה count תחזיר את הערך 5, שכן יש בדיוק 5 סדרות עולות ממש שסכום האיברים שלהן שווה ל-7. להלן הסדרות:
1. (1, 2, 4)
2. (1, 6)
3. (2, 5)
4. (3, 4)
5. (7)

שימו לב: הסדרה הריקה גם היא סדרה עולה ממש וסכום האיברים שלה שווה לאפס.

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

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרקורסיה עם מעקבOverloadingשיטות סטטיות

תזכורת מתמטית:
א. גודל (size) של קבוצה (set) הוא מספר האיברים שיש בה.
למשל, בקבוצה

{- 5, 3, 2, 6}

, יש ארבעה איברים, ולכן גודלה הוא 4.

ב. קבוצות זרות ומשלימות (disjoint and complementary sets) של המערך הן קבוצות שאין להן איבר משותף, והאיחוד שלהן הוא כל איברי המערך. במילים אחרות, כל איבר במערך נמצא בדיוק באחת משתי הקבוצות.
לדוגמא: אם המערך a הוא:

a = 01122033 4 - 1

אז יש הרבה קבוצות זרות ומשלימות במערך זה. הנה כמה מהן:
1.

{1, 2, 0, 3}

{- 1}

{1, 2, - 1}

{0, 3}

{0, 3}

{1, 2, - 1}

{1, 2, 0, 3, - 1}

{}

{1, 3}

{2, 0, - 1}

{2, 0, - 1}

{1, 3}

{1}

{2, 0, 3, - 1}

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

0

.

לדוגמא:
במערך a, החלוקות

2, 3, 4, 7

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

בחלוקה 2 לעיל:

A = {1, 2, - 1}

B = {0, 3}

בקבוצה

A

גודל הקבוצה הוא

3

סכום האיברים

2

בקבוצה

B

גודל הקבוצה הוא

2

סכום האיברים הוא

3

ואכן ההפרש בין הסכומים של שתי הקבוצות הוא

1

(

3 - 2 = 1

), וגם ההפרש בין מספר האיברים של שתי הקבוצות הוא

1

(

2 - 3 = - 1

בערך מוחלט זה

1

).

בחלוקה 3 לעיל:

A = {0, 3}

B = {1, 2, - 1}

בקבוצה

A

גודל הקבוצה הוא

2

סכום האיברים

3

בקבוצה

B

גודל הקבוצה הוא

3

סכום האיברים הוא

2

ההפרש בין הסכומים הוא

1

וההפרש בין הגדלים הוא

1

.

בחלוקה 4 לעיל:

A = {1, 2, 3, 0, - 1}

B = {}

בקבוצה

A

גודל הקבוצה הוא

5

סכום האיברים

5

בקבוצה

B

גודל הקבוצה הוא

0

סכום האיברים הוא

0

ההפרש בין הסכומים הוא

5

וההפרש בין הגדלים הוא

5

.

בחלוקה 7 לעיל:

A = {1}

B = {2, 0, 3, - 1}

בקבוצה

A

גודל הקבוצה הוא

1

סכום האיברים

1

בקבוצה

B

גודל הקבוצה הוא

4

סכום האיברים הוא

4

ההפרש בין הסכומים הוא

3

וההפרש בין הגדלים הוא

3

.

אפשר לראות כי בחלוקה 1 לעיל:

A = {1, 2, 0, 3}

B = {- 1}

בקבוצה

A

גודל הקבוצה הוא

4

סכום האיברים

6

בקבוצה

B

גודל הקבוצה הוא

1

סכום האיברים הוא

- 1

ההפרש בין הסכומים הוא

7

וההפרש בין הגדלים הוא

3

.
לכן החלוקה הזו לא מקיימת את התנאי, ולכן היא לא תודפס ולא תיספר.

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

12

חלוקות כאלו, לכן השיטה תחזיר

12

.

ההדפסה צריכה להיראות כך:

וכן הלאה הדפסה של שאר החלוקות... הסדר לא משנה!

אם המערך b הוא:

b = 01122034 4 - 1

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

0

ולא תדפיס כלום.

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

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

שימו לב,

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרקורסיה עם מעקבמערכיםשיטות סטטיותOverloading

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

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

המשחק נמשך עד שנותר משתתף יחיד, והוא המנצח!

לדוגמא, עבור משחק בו יש שלושה משתתפים: רועי, שקד ויואב (לפי הסדר הזה) והשיר שמתנגן הוא "Elik Belik Bili Bili Boom!" כך ייראה רצף האירועים:

רועי יקבל את המילה "Elik"
שקד תקבל את המילה "Belik"
יואב יקבל את המילה "Bili"
רועי יקבל את המילה "Bili"
שקד תקבל את המילה "Boom!" ותצא מהמשחק. כעת נשארו רק רועי ויואב.
יואב יקבל את המילה "Elik"
רועי יקבל את המילה "Belik"
יואב יקבל את המילה "Bili"
רועי יקבל את המילה "Bili"
יואב יקבל את המילה "Boom!" ויצא מהמשחק.
רועי האחרון שנשאר ולכן הוא המנצח!

עליכם לממש את הפונקציה:

int exam_B_q4(char *players[ ], char *words[ ], int n, int k);

המקבלת:

• את שמות השחקנים לפי הסדר שלהם במערך players
• את מילות השיר לפי הסדר במערך words
• את מספר השחקנים

n

• את מספר המילים בשיר

k

ומחזירה את האינדקס של השחקן שניצח.

למשל בדוגמא לעיל ועבור הקריאה הבאה לפונקציה:

יוחזר הערך 0 שהוא האינדקס של "roey" המנצח של המשחק.

הערות:

• ניתן להניח את תקינות הפרמטרים – המערך players תקין ומכיל לפחות שחקן אחד, ואכן אורכו

n

. המערך words תקין, מכיל את המילה "Boom!" לפחות פעם אחת, וארכו

k

.
• נתונה לכם תוכנית אשר קולטת מהמשתמש את אורך המערך

n

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

k

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

דרישות:

• אסור להשתמש בלולאות מכל סוג, מלבד לצורך אתחול מערך העזר.
• מותר להגדיר פונקציות עזר וכן פונקציות מעטפת. בתנאי שהן מקיימות את התנאי הקודם.
• אסור להשתמש בפונקציות ספרייה (למעט malloc ו-free).
• אסור לשנות את תוכן המערכים words ו-players.
• המילה "Boom!" יכולה להופיע יותר מפעם אחת במהלך השיר.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

הטכניוןמועד ב · 2024 · סמסטר א

★★★★★

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

סעיף ב (15 נקודות)

הגדרות:

• מסלול של מספרים במטריצה דו מימדית בגודל

m \times n

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

[0, 0]

במטריצה ומסתיימת בתא הפינתי הנגדי

[m - 1, n - 1]

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

• מסלול מונוטוני ממש הוא מסלול של מספרים בו כל מספר גדול ממש מקודמו.

דוגמאות:

במטריצה המספרית הבאה, אשר גודלה

4 \times 6

, מסומנים באפור שני מסלולים מונוטוניים ממש:

הראשון: 2-4-5-7-8-11-12-14-15

	0	1	2	3	4	5
0	2	4	1	4	6	0
1	5	5	7	6	8	3
2	4	8	8	10	11	13
3	2	9	11	12	14	15

השני: 2-4-5-8-9-11-12-14-15

	0	1	2	3	4	5
0	2	4	1	4	6	0
1	5	5	7	6	8	3
2	4	8	8	10	11	13
3	2	9	11	12	14	15

לעומת זאת, המסלול 2-4-1-7-6-10-11-13-15 אינו מסלול מונוטוני ממש.

	0	1	2	3	4	5
0	2	4	1	4	6	0
1	5	5	7	6	8	3
2	4	8	8	10	11	13
3	2	9	11	12	14	15

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

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

ניתן להניח כי המטריצה מכילה לפחות מספר אחד.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רקורסיהרקורסיה עם מעקבמערך דו-ממדימחרוזות

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

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