הערה כללית לשאלה: אין להשתמש במבני נתונים נוספים פרט למחסנית או מחסניות אחרות, ויש לשמור את המחסנית במצב מקורי בסיום הפעולה. שלושה סעיפי קוד עצמאיים על אותו רעיון בסיס (ריקון-לעזר-וספירה) ורביעי — ניתוח סיבוכיות.
הערה כללית לשאלה: אין להשתמש במבני נתונים נוספים פרט למחסנית או מחסניות אחרות, ויש לשמור את המחסנית במצב מקורי בסיום הפעולה. שלושה סעיפי קוד עצמאיים על אותו רעיון בסיס (ריקון-לעזר-וספירה) ורביעי — ניתוח סיבוכיות.
מחסנית stk לדוגמה עבור סעיפים א'/ב' (הראש בצד שמאל של הציור — שני החצים מצביעים שמאלה מציינים push/pop באותו הקצה).
top→ 18 | 3 | 15 | 13 | 3 | 12 | 21 | 12 | 10 | 3 | 7 ←bottom (num=3: firstPlace=2, lastPlace=10)
מחסנית לדוגמה עבור סעיף ג' — כל מספר מופיע פעמיים בדיוק; המרחק הקטן ביותר בין שני מופעים זהים הוא 1 (בין שני ה-11).
top→ 4 | 8 | -2 | 11 | 4 | 11 | 1 | -2 | 8 | 1 ←bottom (minDistance=1)
כתבו פעולה המקבלת מחסנית של מספרים שלמים stk ומספר שלם num. הפעולה תחזיר מיקומו הראשון של num בתוך המחסנית. אם num לא מופיע במחסנית, הפעולה תחזיר ערך 1-. לדוגמה: עבור המחסנית stk הבאה והמספר num=3, הפעולה תחזיר 2. כותרת הפעולה: public static int firstPlace(Stack<Integer>stk, int num)
public static int firstPlace(Stack<Integer> stk, int num)
כתבו פעולה המקבלת מחסנית של מספרים שלמים stk ומספר שלם num. הפעולה תחזיר את מיקומו האחרון של num בתוך המחסנית. אם num לא מופיע במחסנית, הפעולה תחזיר ערך 1-. לדוגמה: עבור המחסנית stk הבאה והמספר num=3, הפעולה תחזיר 10. כותרת הפעולה: public static int lastPlace(Stack<Integer>stk, int num)
public static int lastPlace(Stack<Integer> stk, int num)
כתבו פעולה המקבלת מחסנית של מספרים שלמים stk, כל מספר במחסנית מופיע פעמיים בדיוק. הפעולה תבדוק מהו המרחק במחסנית עבור כל שני מספרים זהים ותחזיר את המרחק הקטן ביותר בין שני מספרים זהים. המרחק בין שני מספרים זהים מוגדר כמות המספרים הנמצאים ביניהם. לדוגמה: עבור המחסנית הבאה הפעולה תחזיר 1 (כי מרחק הקטן ביותר בין שני מספרים זהים (11 ו-11) הוא 1).
public static int minDistance(Stack<Integer> stk)
מהי סיבוכיות של הפעולות שכתבתם בסעיפים א'-ג'? הסבירו את תשובתכם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.