מבני נתונים (שאלה יבשה ממת"ם)

[602]

http://i.imgur.com/IVoldI1.png?2

האפש' הן רשימה/קבוצה/מחסנית/גרף/מערך.

אם הבנתי נכון את הניסוח שלהם, המבנה אמור להחזיר שילושים כאלה, כלומר זוגות של קבוצות.

יש למישהו רעיון?

 

תודה מראש =]

[samael]

זה בדיוק גרף

[602]

למה גרף?

(אנחנו מדברים על לשמור שילושים? כלומר לא מבנה נתונים שישמור הרבה משולשים, אלא מבנה נתונים שישמור הרבה אוספים-של-משולשים.)

[samael]

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

נערך בתאריך מאי 17, 2013 - על-ידי samael

[602]

התכוונתי שרשום שאנחנו רוצים לשמור מודלים, כלומר אוספים של "אוספים של משולשים", ולא לשמור אוספים של משולשים.

[samael]

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

[602]

קודם כל תודה רבה.

 

לגבי זה: "אתה יכול בצורה מאוד אינטואיטיבית לשלוף את כל השכנים של נקודה מסויימת (שזה בעצם כל המשולשים שהיא קודקוד שלהם)".

הקשתות של הגרף יהיו הצלעות של המשולשים? אם כן אז שליפת כל השכנים לא תיתן בדיוק את כל המשולשים שהיא קדקוד שלהם.

 

אם לא, אז מה כבר קשתות הגרף יכולות להיות?

[samael]

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

[602]

אוקיי, תודה רבה!