דף 1 מתוך 1

2008 מועד א - שאלה אחרונה

נשלח: 22:28 25/07/2009
על ידי gata
ברור לי הרעיון עם ה4 ערימות
אבל אני תוהה למה לא לעשות את זה עם עץ AVL כל הפעולות לוקחות O(logN) - ואיתחול O(n)
עוד משתנה שמכיל את סכום המשכורות ואת מספר העובדים
ופוינטר לשלישון (שחושב\נתון בהתחלה)
וכל פעם שמכניסים איבר (או מוציאים איבר) מזיזים את המצביע או להבא או לקודם (או בכלל לא) שזה מספר קבוע של פעולות.
ככה אנחנו שומרים את המצביע במקום ה n\3 ערך עליון
(יש קצת פינות שעוד צריך לפתור כמו אם מוצאים לי את השלישון וכאלה אבל זה פתיר)

למישהו יש הסבר למה זה לא יעבוד?
(או כמו שאנחנו אוהבים - דוגמה נגדית :))

Re: 2008 מועד א - שאלה אחרונה

נשלח: 00:48 26/07/2009
על ידי TA_Ariel
האתחול הוא לא (o(n אלא (o(nlogn

Re: 2008 מועד א - שאלה אחרונה

נשלח: 01:15 26/07/2009
על ידי gata
אאאה.... damn...
good point.

Re: 2008 מועד א - שאלה אחרונה

נשלח: 08:59 26/07/2009
על ידי roie
אפשר למיין את המשכורות באחד מהמיונים הלינארים ( radixSort ) ואז להכניס לעץ avl ע"פ רמות וככה המיון וההכנסה יקחו o(n) ?

Re: 2008 מועד א - שאלה אחרונה

נשלח: 11:11 26/07/2009
על ידי gata
לא כי מיון מסוג זה (לא השוואה) מסתמך על כך שהמספרים שאתה ממיין מתפלגים בצורה אחידה
וזה לא המיקרה

Re: 2008 מועד א - שאלה אחרונה

נשלח: 11:59 26/07/2009
על ידי roie
מיון דליים מסתמך על כך שיש התפלגות שווה

במיון radixsort ממיינים משכורות וניתן להניח שמהשכורת המקסימלית חסומה ע"י מספר ספרות כלשהו ( לדוגמה 7 ספרות )

Re: 2008 מועד א - שאלה אחרונה

נשלח: 12:05 26/07/2009
על ידי roie
ועוד משהו קטן : הכוונה הייתה לבנות עץ ריק ועץ להכניס את האיברים ע"פ inorder
ולא כמו שכתבתי להכניס ע"פ רמות...

Re: 2008 מועד א - שאלה אחרונה

נשלח: 17:15 26/07/2009
על ידי gata
שכנעת אותי לגבי המיון
הבעיה שאתה עדיין מכניס N איברים לעץ וזה לוקח nlog(n)
log(1)+log(2)+....+log(n) = nLog(n)

.
.
.

Re: 2008 מועד א - שאלה אחרונה

נשלח: 18:24 26/07/2009
על ידי roie
ניתן להכניס מערך ממוין בגודל n לעץ avl בגודל n
ניתן לבנות עץ ריק ללא מפתחות בצורה רקורסיבית(מבלי לעשות n פעמים insert ) ולאחר מכן לעבור על העץ הריק inorder ולהכניס את איברי המערך הממוין

אם יש לך ספקות כנס ל http://www.dsdb.co.nr/
תכנס לקובץ pdf שקוראים לו עצי avl - טכניון ותסתכל על השקופית האחרונה

שים לב שזהו עוד פתרון לשאלה 2 ג' בעבודה 4 שלנו

בהצלחה מחר!

Re: 2008 מועד א - שאלה אחרונה

נשלח: 20:36 26/07/2009
על ידי gata
תודה ובהצלחה

Re: 2008 מועד א - שאלה אחרונה

נשלח: 01:40 27/07/2009
על ידי TA_Ariel
מה שנכתב לגבי המיון לא נכון לחלוטין. המשכורות לא חסומות.

Re: 2008 מועד א - שאלה אחרונה

נשלח: 16:17 27/07/2009
על ידי roie
המשכורות לא חסומות ?

בתרגול של המיונים שאלה 4 ,נדרשנו למיין מילים באנגלית.
הנחנו ש m היא אורך המילה המקסימלית בקלט - m = קבוע
וביצענו radixsort

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

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