עבודה 6 שאלה 1 סעיף א'

מנהל: TA_Isana

שלח תגובה
KooKeR
הודעות: 9
הצטרף: 13:54 13/11/2009

עבודה 6 שאלה 1 סעיף א'

שליחה על ידי KooKeR » 21:30 14/06/2010

שלום,
כתוב ברמז לפיתרון של שאלה 1 סעיף א' שעלינו להגדיר קבוצה בתור אוסף של ערימות חוקיות כאשר נרשה ערימה אחת מכל גובה (מלבד הקטנה ביותר).
כמה שורות מתחת כתוב בפעולות על קבוצה שנראה כיצד למזג שתי ערימת חוקיות מאותו גובה ואיבר נוסף לערימה חוקית חדשה.
לא היה כתוב לנו הרגע שאסור שיהיו שתי ערימות באותו הגובה או שפספסתי פה משהו?
בכלל, אני לא מבין איך בצורה הזאת אני יכול לייצג קבוצה בגודל 6.
הרי ערימה חוקית בגובה 3 תכיל 7 איברים ולכן אני לא יכול להשתמש בה.
ושתי ערימות בגובה 1 ועוד ערימה בגובה 2 יכילו סה"כ 5 איברים, אז איך בדיוק זה אפשרי?

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

Re: עבודה 6 שאלה 1 סעיף א'

שליחה על ידי hades200621 » 21:55 14/06/2010

אני חושב שהכוונה הייתה שאת/ה יכול להרשות שני ערימות חוקיות בעלות אותו גובה כאשר מדובר בערימה הכי קטנה שקיימת ומייצגת את הקבוצה ולא ערימה בגודל איבר 1 בלבד.

כלומר ל-6 איברים יהיו ברשותך שני ערימות בגודל 3 כל אחד וזה עדיין יעמוד בדרישות...מכיון שהערימה הקטנה היותר היינה הערימה בעלת 3 איברים.

לייצוג 24 איברים לדוגמא יהיו לך הערימות הבאות
ערימה 1 של 15
ערימה 1 של 7
שני ערימות של 1 הערימה בגודל 1 היינה הקטנה ביותר מהערימות שלך, ולכן חוקי להחזיק שני ערימות בגובה/גודל 1

ronenhe
הודעות: 182
הצטרף: 10:27 28/10/2009

Re: עבודה 6 שאלה 1 סעיף א'

שליחה על ידי ronenhe » 01:49 15/06/2010

נראה לי כדאי להוסיף ולהדגיש משהו..
בעיקרון ניתן לבטא כל מספר בעזרת הסכומים המדוברים ואני אפרט:
כדאי לשים לב שההבדל בין ערמה אחת לאחרת היא בעצם שהערמה ה"כבדה" יותר היא 2 ערימות קלות יותר כאלו שבאות לפניה בגודל +1
לדוגמא:

קוד: בחירת הכל

2*1+1=3,    2*3+1=7,   2*7+1=15.......
אלו למעשה הערמות איתם נעבוד..
נגיד שיש לנו איבר אחד. כלומר ערמה בגודל 1
נוסיף עוד ערמה יהיה לנו 2 ערמות בגודל 1
אחרי שנוסיף עוד איבר כבר יש 3 מאותו סוג וזה איתות לכך שאנחנו מתחילים לדבר שטויות אז..
נעבור לערימה חדשה בגודל 3
ואז נמשיך נוסיף עוד איבר ויהיה לנו ערמה בגודל 3 וערמה בגודל 1
נוסיף עוד איבר ויהיה לנו ערימה בגודל 3 ועוד 2 ערימות בגודל 1
נוסיף עוד איבר ואז יהיה לנו ערימה בגודל 3 ועוד 3 ערימות בגודל 1
ושוב אנחנו מדברים שטויות אז נעבור ל 2 ערימות בגודל 3
נוסיף עוד איבר ויש לנו 2 ערימות בגודל 3 ועדו ערימה בגודל 1
אבל זה די טיפשי להשאר ככה אז נעבור לערימה אחת גדולה בגודל 7..
ככה נמשיך לשחק ונשים לב שאם נשחק באותם חוקים אין סיבה למעשה שיהיה לנו יותר משני איברים מינימלים זהים
אם היה יותר משני מינימלים זהים זה אומר שיכלנו לאחד את שני המינימלים ולקבל משהו גדול יותר
אם נגיד היו לנו שני זהים שהם לא מינימלים יכולנו "להלוות" מהמינימלי איזה אחד ואז יכלנו גם להפוך ליותר גדול..
מקווה שזה הסבר ברור מעבר לזה אני אאלץ להתחיל לדבר על פיות ודרדסים ואני לא חושב שזה רלוונטי לשאלה..
בהצלחה!

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

Re: עבודה 6 שאלה 1 סעיף א'

שליחה על ידי TA_Yakim » 08:56 15/06/2010

ענו לך יפה. אוסיף רק:

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

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

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

KooKeR
הודעות: 9
הצטרף: 13:54 13/11/2009

Re: עבודה 6 שאלה 1 סעיף א'

שליחה על ידי KooKeR » 16:37 15/06/2010

הטעות שלי היתה שהבנתי שניתן להשתמש בערימה באותו הגובה רק אם היא בגובה 1, אז עכשיו הכל מסתדר לי
תודה לכולם

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

Re: עבודה 6 שאלה 1 סעיף א'

שליחה על ידי hades200621 » 21:20 15/06/2010

אתה לא היחיד :)

שלח תגובה

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