שאלה במבני נתונים

[gil levi]

שאלה במבני נתונים

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

 

[yuvalmadar]

רמז

תשתמש בשתי ערימות, אבל תחלק את האיברים ביניהן.

 

[gil levi]

תודה על הרמז.

 

[gil levi]

שתי שאלות נוספות

השאלות בתמונה. בשאלה 3 הגודל של הערימה לא נתון. בשאלה הזו היו לי כמה כיוונים. למשל- למדוד את הגובה של הערימה על ידי פנייה שמאלה בכל צומת וברגע שיש לנו את הגובה של הערימה צריך לטייל על הערימה בסדר מסלולים מסוים ובכל פעם שנגיע לעלה נבדוק האם אורך המסלול הנוכחי שווה לגובה הערימה. סדר המסלולים צריך להיות כזה שנגיע לאיבר הימני ביותר בשכבה התחתונה ראשון מכל העלים בשכבה התחתונה. הבעיה היא שלא הצלחתי למצוא מהו סדר המסלולים הנכון כך שמספר המסלולים במקרה הגרוע ביותר יהיה O(logn) zzz. רעיון אחר היה להשתמש בתנאי העצירה שאם לצומת יש רק בן יחיד אז לעצור, אבל גם במקרה הזה לא הצלחתי להגיע לסדר המסלולים הנכון, מה עוד שלא תמיד נעצור לפי התנאי הזה (אם השכבה התחתונה מלאה). בשאלה 4 א'- אני יודע שזה לא נכון אבל אני לא מצליח למצוא דוגמא נגדית. ברור לי שצריך למצוא קשר בין X וY (המפתחות שמוחקים) אבל לא הצלחתי להגיע לפתרון. ניסיתי כמה דוגמאות שבהן אחרי מחליפים את X בY ואז מוחקים את X (אם X נמחק ראשון) ואז מוחקים את Y (וכעת הוא במקום שבו היה X) אבל בכל המקרים האלו המחיקה הייתה קומוטטיבית. אפשר רמז/הדרכה/כיוון לשאלות? תודה מראש.

 

[gil levi]

השאלות כבר לא רלוונטיות.

 

[דודהלי]

החתימה שלך א-ד-י-ר-ה../images/Emo6.gif