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

מנהל: TA_Isana

שלח תגובה
gata
הודעות: 88
הצטרף: 17:25 10/11/2007

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

שליחה על ידי gata » 22:28 25/07/2009

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

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

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

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

שליחה על ידי TA_Ariel » 00:48 26/07/2009

האתחול הוא לא (o(n אלא (o(nlogn
נערך לאחרונה על ידי TA_Ariel ב 01:16 26/07/2009, נערך פעם 1 בסך הכל.

gata
הודעות: 88
הצטרף: 17:25 10/11/2007

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

שליחה על ידי gata » 01:15 26/07/2009

אאאה.... damn...
good point.
נערך לאחרונה על ידי gata ב 19:19 14/08/2009, נערך פעם 1 בסך הכל.

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

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

שליחה על ידי roie » 08:59 26/07/2009

אפשר למיין את המשכורות באחד מהמיונים הלינארים ( radixSort ) ואז להכניס לעץ avl ע"פ רמות וככה המיון וההכנסה יקחו o(n) ?

gata
הודעות: 88
הצטרף: 17:25 10/11/2007

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

שליחה על ידי gata » 11:11 26/07/2009

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

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

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

שליחה על ידי roie » 11:59 26/07/2009

מיון דליים מסתמך על כך שיש התפלגות שווה

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

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

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

שליחה על ידי roie » 12:05 26/07/2009

ועוד משהו קטן : הכוונה הייתה לבנות עץ ריק ועץ להכניס את האיברים ע"פ inorder
ולא כמו שכתבתי להכניס ע"פ רמות...

gata
הודעות: 88
הצטרף: 17:25 10/11/2007

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

שליחה על ידי gata » 17:15 26/07/2009

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

.
.
.

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

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

שליחה על ידי roie » 18:24 26/07/2009

ניתן להכניס מערך ממוין בגודל n לעץ avl בגודל n
ניתן לבנות עץ ריק ללא מפתחות בצורה רקורסיבית(מבלי לעשות n פעמים insert ) ולאחר מכן לעבור על העץ הריק inorder ולהכניס את איברי המערך הממוין

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

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

בהצלחה מחר!

gata
הודעות: 88
הצטרף: 17:25 10/11/2007

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

שליחה על ידי gata » 20:36 26/07/2009

תודה ובהצלחה

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

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

שליחה על ידי TA_Ariel » 01:40 27/07/2009

מה שנכתב לגבי המיון לא נכון לחלוטין. המשכורות לא חסומות.

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

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

שליחה על ידי roie » 16:17 27/07/2009

המשכורות לא חסומות ?

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

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

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

שלח תגובה

חזור אל “- מבני נתונים”