עבודה 5 - IsElementAtSpecialPlace

מנהל: TA_Isana

שלח תגובה
sheknabs
הודעות: 31
הצטרף: 17:03 12/11/2009

עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי sheknabs » 20:02 16/05/2010

האם יתכן שיש טעות בזמן הריצה של הפונקציה הנ"ל כיוון שיש צורך לבדוק האם קיים a כך שהאיבר נמצא במקום המיוחד תלוי a זה?
ולכן בחיפוש עקר עלינו לעבור על כל a בין 1 לk וזה גם במקרה הממוצע לא יכול ליהיות O(1).

תודה.

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

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי TA_Ariel » 20:58 16/05/2010

לא אין טעות.
תחשוב על מבנה נתונים שמסוגל לעשות את זה בO(1) בממוצע.
כלומר מבנה נתונים שמחזיק k מפתחות ומסוגל בO(1) בממוצע, לענות האם קיים מפתח מסויים במבנה. בשביל לעשות זאת בk מספיקה רשימה פשוטה.

sheknabs
הודעות: 31
הצטרף: 17:03 12/11/2009

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי sheknabs » 21:26 16/05/2010

יש לי עוד 2 שאלות:
1. האם מותר להשתמש בorderStatistics שלמדנו לפני הרצאה אחת?
2. O(nlogk+klogn)=O(nlogk) ?? כמובן בתנאי העבודה n>=k.

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

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי TA_Ariel » 23:22 16/05/2010

1. כן, אתה יכול להשתמש בכל שיטה, כל עוד היא עומדת בזמני הריצה. בתור התחלה זה רעיון טוב, אבל אתה צריך למצוא דרך לשמור את הנתונים במבנה שיחסוך לך את החיפוש לאחר ההכנסות.
2. נכון.

GalRoot
הודעות: 3
הצטרף: 10:19 23/10/2009

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי GalRoot » 19:39 17/05/2010

TA_Ariel כתב:לא אין טעות.
תחשוב על מבנה נתונים שמסוגל לעשות את זה בO(1) בממוצע.
כלומר מבנה נתונים שמחזיק k מפתחות ומסוגל בO(1) בממוצע, לענות האם קיים מפתח מסויים במבנה. בשביל לעשות זאת בk מספיקה רשימה פשוטה.

אפשר את האות הראשונה?..

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

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי TA_Ariel » 21:20 17/05/2010

כן, אפילו את שתי הראשונות, הם משותפות לתחילת שמו של שיר שמתחיל ככה :
Now I've heard there was a secret chord
That David played, and it pleased the Lord

hades200621
הודעות: 35
הצטרף: 01:00 24/10/2009

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי hades200621 » 21:52 17/05/2010

האם האות השלישית היא האות הראשונה של שם השיר שכמעט מתחיל ככה:
And you want to travel with her
And you want to travel blind
??? תודה מראש!

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי בר כהן » 22:34 17/05/2010

יש פרסים למנחשים נכונה?? :o

hades200621
הודעות: 35
הצטרף: 01:00 24/10/2009

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי hades200621 » 23:00 17/05/2010

אין תקציב לפרסים...

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

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי TA_Ariel » 23:21 17/05/2010

:),
עכשיו נשאר לחשוב מה הגודל.

hades200621
הודעות: 35
הצטרף: 01:00 24/10/2009

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי hades200621 » 23:33 17/05/2010

הבהרה כללית לגבי הקלט פלט...

לפני שאני נכנס עמוק מדיי רציתי לוודא שהכיוון אכן נכון.

הקובץ הראשי Heaps.java ישמש כרצף ענק של מחרוזת כאשר כל שורה בעצם זה מספר אותו אנחנו צריכים להרכיב בעזרת הפונקציות הנתונות.
את המספרים המתקבלים יש לשמור בקובץ code.txt. הקובץ הנ"ל ישמש אותנו כאוסף מספרים בעזרת אנו נדרשים לבנות את מבנה הנתונים התומך בפעולות בזמן ריצה מבוקש (האם אפשר להניח שאלו מספרים שלמים בין 0 ל-84)
להריץ את הפעולה שתחזיר את הגדלים [i*n/k] כאשר i אינדקס רץ על המספרים השלמים מ-1 ועד k ואת התוצאה יש לשמור על הקובץ Halt.txt.

נ.ב לא הבנתי מה ההבדל בין הקובץ code.txt שלנו לקבוץ האופציונאלי?

תודה מראש!

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

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי TA_Ariel » 23:56 17/05/2010

Heaps.java - כל מילה תהפוך למספר, לא כל שורה. הקובץ הזה יקרא code.txt.
תוצאת ריצת התוכנית שלכם על code.txt כקובץ קלט תהיה Halt.txt.
כל מה שכתבתי למעלה שייך רק להגשה. במקרה הזה המספרים אכן בין 0 ל84 לפי ההגדרה.

התוכנית שלכם צריכה לדעת במקרה הכללי (בניגוד למקרה הפרטי שצויין למעלה) לקבל [b]שני[/b] קבצים,
הראשון הוא קובץ מספרים שאותו תכניסו למבנה הנתונים שלכם(פעולת הinit),
השני שהוא אופציונלי, כלומר לא בהכרח ינתן לכם בכל ריצה, מכיל מספרים נוספים אותם עליכם להוסיף למבנה (ע"י פעולת Insert),

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

code.txt - הוא רק דוגמת קלט אחת של התוכנית, הוא לא צריך להיות קלט קבוע.

אני מקווה שיותר ברור עכשיו ההבדל בין התוכנית לבין דרישות ההגשה.

נ.ב יתכן כי כדאי לדחות את הטיפול בחלק של ההגשה ולהתמקד במבנה נתונים, בינתיים.

hades200621
הודעות: 35
הצטרף: 01:00 24/10/2009

Re: עבודה 5 - IsElementAtSpecialPlace

שליחה על ידי hades200621 » 00:20 18/05/2010

תודה רבה.

שלח תגובה

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