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

מנהל: TA_Isana

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

הודעהעל ידי gata » 21:28 25/07/2009

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

למישהו יש הסבר למה זה לא יעבוד?
(או כמו שאנחנו אוהבים - דוגמה נגדית :))
gata
 
הודעות: 88
הצטרף: 17:25 10/11/2007

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

הודעהעל ידי TA_Ariel » 23:48 25/07/2009

האתחול הוא לא (o(n אלא (o(nlogn
נערך לאחרונה על ידי TA_Ariel בתאריך 00:16 26/07/2009, נערך פעם אחת בסך הכל.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

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

הודעהעל ידי gata » 00:15 26/07/2009

אאאה.... damn...
good point.
נערך לאחרונה על ידי gata בתאריך 18:19 14/08/2009, נערך פעם אחת בסך הכל.
gata
 
הודעות: 88
הצטרף: 17:25 10/11/2007

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

הודעהעל ידי roie » 07:59 26/07/2009

אפשר למיין את המשכורות באחד מהמיונים הלינארים ( radixSort ) ואז להכניס לעץ avl ע"פ רמות וככה המיון וההכנסה יקחו o(n) ?
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008

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

הודעהעל ידי gata » 10:11 26/07/2009

לא כי מיון מסוג זה (לא השוואה) מסתמך על כך שהמספרים שאתה ממיין מתפלגים בצורה אחידה
וזה לא המיקרה
gata
 
הודעות: 88
הצטרף: 17:25 10/11/2007

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

הודעהעל ידי roie » 10:59 26/07/2009

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

במיון radixsort ממיינים משכורות וניתן להניח שמהשכורת המקסימלית חסומה ע"י מספר ספרות כלשהו ( לדוגמה 7 ספרות )
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008

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

הודעהעל ידי roie » 11:05 26/07/2009

ועוד משהו קטן : הכוונה הייתה לבנות עץ ריק ועץ להכניס את האיברים ע"פ inorder
ולא כמו שכתבתי להכניס ע"פ רמות...
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008

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

הודעהעל ידי gata » 16:15 26/07/2009

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

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

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

הודעהעל ידי roie » 17:24 26/07/2009

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

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

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

בהצלחה מחר!
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008

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

הודעהעל ידי gata » 19:36 26/07/2009

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

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

הודעהעל ידי TA_Ariel » 00:40 27/07/2009

מה שנכתב לגבי המיון לא נכון לחלוטין. המשכורות לא חסומות.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

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

הודעהעל ידי roie » 15:17 27/07/2009

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

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

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

בבקשה תקן אותי אם אני טועה,אחרי הכל יש מועד ב' ללמוד אליו...
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד

cron