שתי פעולות עצמאיות על תור מספרים שלמים: putInPlace ממקמת מספר נתון כך שכל הקטנים ממנו לפניו וכל השווים/גדולים ממנו אחריו; moveToFront מעבירה את k האיברים האחרונים בתור אל ראשו. בשני הסעיפים פותרים אך ורק עם פעולות התור (insert/remove/head/isEmpty), בעזרת תורי עזר.
שתי פעולות עצמאיות על תור מספרים שלמים: putInPlace ממקמת מספר נתון כך שכל הקטנים ממנו לפניו וכל השווים/גדולים ממנו אחריו; moveToFront מעבירה את k האיברים האחרונים בתור אל ראשו. בשני הסעיפים פותרים אך ורק עם פעולות התור (insert/remove/head/isEmpty), בעזרת תורי עזר.
putInPlace: עבור q=[2,10,12,3,7,4,1] (ראש→סוף) ו-num=9, תוצאה אפשרית: [2,3,7,4,1,9,10,12], והפעולה מחזירה 6 (המיקום הסידורי של 9, החל מ-1).
q (ראש→סוף): 2,10,12,3,7,4,1 num=9
תוצאה אפשרית (ראש→סוף): 2,3,7,4,1,9,10,12 (הפעולה מחזירה 6)
moveToFront: עבור q=[7,2,5,4,6,8,10,12] (ראש→סוף) ו-k=5, מעבירים את 5 האיברים האחרונים (4,6,8,10,12) אל ראש התור: תוצאה [4,6,8,10,12,7,2,5].
q (ראש→סוף): 7,2,5,4,6,8,10,12 k=5
תוצאה (ראש→סוף): 4,6,8,10,12,7,2,5
כתבו פעולה בשם putInPlace המקבלת תור q ומספר num, וממקמת את המספר num במיקומו, כך שכל האיברים הקטנים ממנו נמצאים לפניו וכל האיברים השווים לו או הגדולים ממנו נמצאים אחריו (אין משמעות לסדר של האיברים הקטנים או הגדולים ממנו). הפעולה תחזיר את מיקומו הסידורי של num בתוך התור אחרי הכנסתו.
public static int putInPlace(Queue<Integer> q, int num)
כתבו פעולה חיצונית המקבלת תור q של מספרים שלמים ומספר שלם וחיובי k, ומעבירה את k האיברים האחרונים בתור אל ראש התור. אפשר להניח ש-k קטן מאורך התור.
public static void moveToFront(Queue<Integer> q, int k)
מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.