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

שני מספרים שלמים וחיוביים num1 ו-num2 נקראים "זרים זה לזה" אם אין להם אף מחלק משותף פרט ל-1. סעיף א' בודק זרות בין שני מספרים; סעיף ב' משתמש בכך כדי לסדר תור לפי זרות למספר נתון.

תור q לדוגמה עבור סעיף ב', לפני הפעולה change (ראש התור בצד ימין של הציור, סוף התור בצד שמאל — שני החצים בציור מצביעים שמאלה, מציינים את כיוון הזרימה מסוף התור לראשו).

ראש (head)→ 2 | 10 | 12 | 3 | 7 | 4 | 1 ←סוף (tail, num=9 נבדק כאן)

דוגמה לתור אפשרי אחרי change(q, 9) — כל הזרים ל-9 (2,10,7,4,1) לפני כל הלא-זרים ל-9 (3,12); הסדר הפנימי בכל קבוצה אינו מחייב (הניסוח 'יכול להיות' בשאלון).

ראש→ 2 | 10 | 7 | 4 | 1 | 3 | 12 ←סוף

סעיף א

שני מספרים שלמים וחיוביים num1 ו-num2 נקראים "זרים זה לזה" אם אין להם אף מחלק משותף פרט ל-1. כתבו פעולה המקבלת שני מספרים שלמים חיוביים. הפעולה תבדוק אם הם "זרים". אם כן, הפעולה תחזיר ערך true, ולא — הפעולה תחזיר ערך false. כותרת הפעולה: public static boolean strangers(int num1, int num2)

סעיף ב

כתבו פעולה change המקבלת תור q ומספר num. הפעולה משנה את סדר האיברים בתור כך שכל המספרים ה"זרים" ל-num יהיו בתחילת התור וכל האיברים אשר "לא זרים" ל-num, יהיו אחריהם. לדוגמה: עבור התור q הבא (ראה איור) והמספר num=9, התור שיתקבל יכול להיות (ראה איור). כותרת הפעולה: public static void change(Queue<Integer> q, int num)

סעיף ג

מהי הסיבוכיות של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.

שאלות ותגובות על השאלה

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה לתכנות עונה כאן — תקבלו מענה מקצועי

לתרגל עוד שאלות — חינם ←