מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 4/שאלות

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי


שימו לב:

*נא להגיש רק את שאלות 1-5.
  • שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

1[עריכה]

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

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

א'[עריכה]

שימוש ברשימה מקושרת:

1	l = Make-List()
	
2	do
3		c = Read()
4		if c != 'q'
5			Insert-Back(l, c)
6	while c != 'q'

הקוד פשוט למדי. 1 מייצרת רשימה מקושרת. הלולאה 2-6 קוראת תווים כל עוד לא נלחץ 'q', ומכניסה תווים (למעט 'q') לסוף הרשימה.


ב'[עריכה]

שימוש במערך גדל ב1:

1	A = Make-Array(1)
2	used = 0
	
3	do
4		c = Read()
5		if c != 'q'
6			A[++used] = c
			
7			if used == Length(A)
8				Tmp = Make-Array(used + 1)
				
9				for j in [1, ..., used]
10					Tmp[j] = A[j]
	
11				A = Tmp
12	while c != 'q'

1 מייצרת מערך בגודל 1.‏ 2 מאתחלת משתנה used, המתאר כמה איברים בשימוש בְמערך A,‏ ל1.‏ 3-12 קוראת תווים כל עוד לא נלחץ 'q', ומכניסה תווים (למעט 'q') לסוף המערך. 7-11 מטפלות במקרה בו נגמר המקום במערך A.‏ 8 מייצרת מערך חדש Tmp, שארכו גדול ב1 מזה של A.‏ 9-10 מעתיקות את האיברים למערך החדש. 11 משימה את המערך החדש לA במקום הקודם. ביציאה מהלולאה, A[1, ..., used] יחזיק את האיברים שנקלטו.

ג'[עריכה]

שימוש במערך גדל פי 2:

1	A = Make-Array(1)
2	used = 0
	
3	do
4		c = Read()
5		if c != 'q'
6			A[++used] = c
			
7			if used == Length(A)
8				Tmp = Make-Array(used * 2)
				
9				for j in [1, ..., used]
10					Tmp[j] = A[j]
	
11				A = Tmp
12	while c != 'q'

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

2[עריכה]

א'[עריכה]

אנא כתוב מימוש יעיל לפונקציה List-Set-All(l, v) המקבלת (מצביע ל)רשימה מקושרת l, ערך v, וקובעת את הערכים בכל חוליות הרשימה לv.

ב'[עריכה]

אנא כתוב מימוש יעיל לפונקציה List-Union(l1, l2) המקבלת (מצביעים ל)רשימות מקושרות 1l וl2. לאחר הקריאה לפונקציה, על 1l להכיל את איחוד האיברים שהיו בשתי הרשימות לפני הקריאה, ועל l2 להיות ריקה.

3[עריכה]

להלן מבנה אפשרי לרשימה מקושרת חד-כוונית.

הרשימה מורכבת מחוליות. כל חוליה נראית כך:

# A data structure that describes a link which has a value, and can
#	be connected to a following and previous link.
Link
	# The next Link.
1	next
	# The value at this link.
2	value

להלן הפסוודו-קוד לרשימה עצמה:

# A data structure that describes a (doubly-linked) list of values.
List
        # The leftmost link.
1      front
        # The size (number of links).
2      size

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

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

4[עריכה]

הגדרה:

מחרוזת היא רצף של תווים. אם ,‏ ,‏ ו הן שלוש מחרוזות, אז:

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




דוגמה:

ו הן מחרוזות.

אם ו, אז:

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



הגדרה:

אם ו הן מחרוזות, אז היא הLCS (או longest common subsequence), אם היא הארוכה ביותר מבין תתי-המחרוזות המשותפות ל ול.

בשאלה זו עליך למצוא אלגוריתם יעיל למציאת הLCS לכל שתי מחרוזות ו:

  1. אנא תאר אלגוריתם יעיל המוצא את אורך הLCS.
  2. אנא תאר אלגוריתם יעיל המדפיס את הLCS עצמו.


שימו לב:

בכל אחד משני הסעיפים:
  1. הנח שX וY הם שני מערכים גלובליים המתארים את המחרוזות ו, בעלות האורכים ו בהתאמה.
  2. אנא הוכח נכונות תשובתך, ונתח את סיבוכיותה במונחי ו.

5[עריכה]

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

נתונות מידות, , שלהן מותאמים מחירים . כלומר:

  1. חתיכת בד במידה שווה שקלים.
  2. חתיכת בד במידה שווה שקלים.
  3. ...
  4. חתיכת בד במידה שווה שקלים.חוץ מ מידות אלה, כל המידות האחרות חסרות ביקוש, ולכן כל חתיכת בד במידה שונה

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




דוגמה:

בתרשים הבא, A מראה פיסת בד במידות , וB מראה שתי מידות בעלת ערך: העליונה בעלת המידות , והתחתונה בעלת המידות . נניח שהמידה העליונה שווה 35 שקל, והתחתונה שווה 2 שקלים.


.
.


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




דוגמה:

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

בתרשים הבא:

  1. A מראה את החתך הראשון: נחתוך את הצורה אנכית בשורה 1, ונקבל את שתי הצורות בB.
  2. את הצורה העליונה בB נחתוך אנכית בטור הראשון, ונקבל את שלוש הצורות בC.
  3. את הצורה התחתונה בC נחתוך אנכית בטור 2, ונקבל את ארבע הצורות בD.
  4. כל אחת מהשורות בD מכילה כעת צורה אחת ששווייה 2 שקלים, ועוד צורה חסרת ערך.
.
.


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


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

הנח שקיימת פונקציה Value(i, j) המחזירה בזמן :

  1. 0 אם אינה אחת מ המידות בעלות התועלת.
  2. אם .


כדאי לדעת:

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

6[עריכה]

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

7[עריכה]

אנא כתוב מימוש יעיל לפונקציה Find-Num-In-Range(A, a, b), המקבלת:

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

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

הנח שברשותך פונקציה Dist(x) המקבלת מספר מרוכב ומחזירה את מרחקו מראשית הצירים.