דף 1 מתוך 1

שאלה 4 קבוצה U נתונה ?

נשלח: 13:29 07/04/2010
על ידי caridin
שלום
בשאלה רשום
U={1,2,..,n} מקבוצה נתונה של קבוצות זרות של איברי

האם ניתן להניח ש U נתונה ומאותחלת לפי מבנה הנתונים שהצעתי ?
כלומר אם בחרתי במערך דו מימדי , האם ניתן להניח שU נתונה כמערך בהתאם למבנה הנתונים שבחרתי או שצריך לאתחל את המערך קרי , את U ?

תודה,

Re: שאלה 4 קבוצה U נתונה ?

נשלח: 14:21 07/04/2010
על ידי ronenhe
לפי מה שאני מבין אתה צודק ואתה מקבל כבר את מה שאתה עובד איתו אבל משהו לא מסתדר..
אם נגיד אתה מממש במערך דו מיימדי
איך אתה משנה את הגודל שלו?
כלומר נגיד יש לך מערך "ראשי" בגודל N ואתה רוצה לשים N+1 קבוצות זרות מה אתה עושה?
בונה מערך חדש?
נראה לי זה קצת בזבוז או שלא הבנתי?

Re: שאלה 4 קבוצה U נתונה ?

נשלח: 14:23 07/04/2010
על ידי caridin
ממש לא
לא יכולות להיות לך N+1 קבוצות זרות יש סהכ N איברים .
כל איחוד יתן לך קבוצה חדשה וימחוק את השניות .

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

זו סתם רעיון ..

Re: שאלה 4 קבוצה U נתונה ?

נשלח: 14:36 07/04/2010
על ידי caridin
אבל שוב , אני לא בטוח לגבי הכוונה , אז אני מעדיף שמתרגל יענה לגבי U, איך הוא מתקבל
והאם ניתן להניח איך מקבלים אותו .
ז"א האם U מערך חד מימדי שצריך לעבוד איתו
או שאפשר להניח שהוא מגיע כמבנה נתונים כראות עיניי ..?

Re: שאלה 4 קבוצה U נתונה ?

נשלח: 18:08 07/04/2010
על ידי Fogpiskalo
או..קי...

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

Re: שאלה 4 קבוצה U נתונה ?

נשלח: 20:38 07/04/2010
על ידי TA_Lena
אכן U נועדה להגדיר איזה נתונים המבנה נתונים יקבל.