טוען...
טוען...
שים לב
בכל שאלה שנדרש בה מימוש אתה יכול להשתמש בפעולות של המחלקות תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם אתה משתמש בפעולות נוספות, עליך לממש אותן.
לפניך הגדרה של חמש פעולות הפועלות על מבנה נתונים כלשהו.
שים לב
שמות הפעולות שלפניך אינם כתובים ב-Java או ב-C#.
insert(x): פעולה המכניסה למבנה איבר שערכו x מטיפוס שלם.showMin(): פעולה המחזירה את הערך הנמוך ביותר במבנה, בלי לשנות את המבנה.getMax(): פעולה המחזירה את האיבר שערכו הוא הגדול ביותר במבנה, ומוציאה אותו מן המבנה. אם יש יותר מאיבר אחד כזה, הפעולה תחזיר ותוציא את זה שמופיע ראשון.exists(x): פעולה בוליאנית המחזירה true אם האיבר שערכו x קיים במבנה. אחרת הפעולה מחזירה false.div7(): פעולה בוליאנית המחזירה true אם קיים במבנה איבר שערכו מתחלק ב-7 בלי שארית. אחרת הפעולה מחזירה false.נרצה להציע מבני נתונים העומדים בדרישות סיבוכיות שונות למימוש פעולות מתוך חמש הפעולות שהוגדרו.
✎ דוגמה
רוצים להציע מבנה נתונים שאפשר לבצע עליו את הפעולות
insert,showMinבסיבוכיות O(1), ואת הפעולותgetMax,existsבסיבוכיות O(n). לשם כך נגדיר את מבנה הנתונים ונסביר כיצד ימומשו הפעולות. שים לב: במבנה זה אין צורך להתייחס לפעולהdiv7.
מבנה נתונים מתאים מורכב מ-:
lst מטיפוס שלם.min.הפעולות יבוצעו כך:
| הפעולה | הסבר כיצד תמומש | נימוק מדוע המימוש עומד בדרישות הסיבוכיות |
|---|---|---|
insert(x) | הכנסת האיבר x לראש הרשימה. אם האיבר קטן מן המינימום עד כה, עדכון המצביע min כך שיצביע על האיבר החדש. | הכנסת איבר לראש הרשימה - O(1). אם הוכנס איבר שקטן מן המינימום: עדכון המצביע לאיבר המינימלי - O(1). אם הוכנס איבר ראשון - הכנסה לראש הרשימה ב-O(1) ועדכון המצביע לאיבר הראשון שהוא גם המינימלי. סך הכול - O(1). |
showMin() | החזרת הערך של האיבר שעליו מצביע min. | החזרת הערך - O(1). |
exists(x) | מעבר על הרשימה lst וחיפוש האיבר שערכו x. | במקרה הגרוע - מעבר על כל הרשימה - O(n). |
getMax() | מעבר על הרשימה lst, חיפוש האיבר שערכו מקסימלי והוצאתו מן הרשימה. | חיפוש האיבר שערכו מקסימלי O(n). הוצאתו מן הרשימה O(1). |
לפניך שני סעיפים א-ב.
עליך להציע מבנה נתונים מתאים העומד בדרישות: ביצוע הפעולות insert, exists בסיבוכיות O(n), וביצוע הפעולות showMin, getMax בסיבוכיות O(1). המבנה יכול להיות מורכב משילוב של כמה מבנים וטיפוסים שלמדת. לכל אחת מן הפעולות הסבר כיצד תממש אותה, ונמק מדוע המימוש עומד בדרישות (כפי שהוצג בטבלה שבדוגמה). אין צורך לממש את הפעולות.
עליך להציע מבנה נתונים מתאים העומד בדרישות: ביצוע הפעולות insert, getMax בסיבוכיות O(n), וביצוע הפעולה div7 בסיבוכיות O(1). המבנה יכול להיות מורכב משילוב של כמה מבנים וטיפוסים שלמדת. לכל אחת מן הפעולות הסבר כיצד תממש אותה, ונמק מדוע המימוש עומד בדרישות (כפי שהוצג בטבלה שבדוגמה). אין צורך לממש את הפעולות.
שים לב
בכל שאלה שנדרש בה מימוש אתה יכול להשתמש בפעולות של המחלקות תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם אתה משתמש בפעולות נוספות, עליך לממש אותן.
לפניך הגדרה של חמש פעולות הפועלות על מבנה נתונים כלשהו.
שים לב
שמות הפעולות שלפניך אינם כתובים ב-Java או ב-C#.
insert(x): פעולה המכניסה למבנה איבר שערכו x מטיפוס שלם.showMin(): פעולה המחזירה את הערך הנמוך ביותר במבנה, בלי לשנות את המבנה.getMax(): פעולה המחזירה את האיבר שערכו הוא הגדול ביותר במבנה, ומוציאה אותו מן המבנה. אם יש יותר מאיבר אחד כזה, הפעולה תחזיר ותוציא את זה שמופיע ראשון.exists(x): פעולה בוליאנית המחזירה true אם האיבר שערכו x קיים במבנה. אחרת הפעולה מחזירה false.div7(): פעולה בוליאנית המחזירה true אם קיים במבנה איבר שערכו מתחלק ב-7 בלי שארית. אחרת הפעולה מחזירה false.נרצה להציע מבני נתונים העומדים בדרישות סיבוכיות שונות למימוש פעולות מתוך חמש הפעולות שהוגדרו.
✎ דוגמה
רוצים להציע מבנה נתונים שאפשר לבצע עליו את הפעולות
insert,showMinבסיבוכיות O(1), ואת הפעולותgetMax,existsבסיבוכיות O(n). לשם כך נגדיר את מבנה הנתונים ונסביר כיצד ימומשו הפעולות. שים לב: במבנה זה אין צורך להתייחס לפעולהdiv7.
מבנה נתונים מתאים מורכב מ-:
lst מטיפוס שלם.min.הפעולות יבוצעו כך:
| הפעולה | הסבר כיצד תמומש | נימוק מדוע המימוש עומד בדרישות הסיבוכיות |
|---|---|---|
insert(x) | הכנסת האיבר x לראש הרשימה. אם האיבר קטן מן המינימום עד כה, עדכון המצביע min כך שיצביע על האיבר החדש. | הכנסת איבר לראש הרשימה - O(1). אם הוכנס איבר שקטן מן המינימום: עדכון המצביע לאיבר המינימלי - O(1). אם הוכנס איבר ראשון - הכנסה לראש הרשימה ב-O(1) ועדכון המצביע לאיבר הראשון שהוא גם המינימלי. סך הכול - O(1). |
showMin() | החזרת הערך של האיבר שעליו מצביע min. | החזרת הערך - O(1). |
exists(x) | מעבר על הרשימה lst וחיפוש האיבר שערכו x. | במקרה הגרוע - מעבר על כל הרשימה - O(n). |
getMax() | מעבר על הרשימה lst, חיפוש האיבר שערכו מקסימלי והוצאתו מן הרשימה. | חיפוש האיבר שערכו מקסימלי O(n). הוצאתו מן הרשימה O(1). |
לפניך שני סעיפים א-ב.
עליך להציע מבנה נתונים מתאים העומד בדרישות: ביצוע הפעולות insert, exists בסיבוכיות O(n), וביצוע הפעולות showMin, getMax בסיבוכיות O(1). המבנה יכול להיות מורכב משילוב של כמה מבנים וטיפוסים שלמדת. לכל אחת מן הפעולות הסבר כיצד תממש אותה, ונמק מדוע המימוש עומד בדרישות (כפי שהוצג בטבלה שבדוגמה). אין צורך לממש את הפעולות.
עליך להציע מבנה נתונים מתאים העומד בדרישות: ביצוע הפעולות insert, getMax בסיבוכיות O(n), וביצוע הפעולה div7 בסיבוכיות O(1). המבנה יכול להיות מורכב משילוב של כמה מבנים וטיפוסים שלמדת. לכל אחת מן הפעולות הסבר כיצד תממש אותה, ונמק מדוע המימוש עומד בדרישות (כפי שהוצג בטבלה שבדוגמה). אין צורך לממש את הפעולות.