כמה שאלות:

[ronihp]

כמה שאלות:

א) באיזה מבנה נתונים הכי טוב להשתמש על מנת לייצג מפה של רחובות, כאשר ידוע לי שאני רוצה להגיע מרחוב X לרחוב Y, אבל אני רוצה שהמחשב ימצא את כל המסלולים האפשריים. ב) איך ממשים מחסנית עם תורים בלבד? אשמח ליעוץ.

 

[אלוהים1980]

נסיון לענות על ב':

אתה צריך שני תורים: תור א' תור ב' הפעולות הן: הכנסה והוצאה. הכנסה: הוסף את האיבר לתור א'. הוצאה: קרא את כל האיברים מתור א' והעבר אותם לתור ב', מלבד האחרון, שאותו תוציא לפלט. החלף תפקידים כעת בין תור א' ותור ב'.

 

[vinney]

א - ייצוג גרפים

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

 

[IsraeliSecretToilets]

אתה לא זוכר נכון ../images/Emo13.gif

בשביל למצוא מסלולים צריך אלגוריתם BFS או Dijkstra (תלוי אם זה ממושקל או לא). הם עובדים גם על ייצוג מטריציוני וגם על ייצוג עם רשימה.

 

[IsraeliSecretToilets]

אהה.. אופס ../images/Emo13.gif

לא Dijkstra. אבל BFS (עם מודיפיקציה קטנה) יכול למצוא את כל המסלולים. והוא עובד על שני הסוגים.

 

[vinney]

המעבר בינהם זה O של N

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

 

[IsraeliSecretToilets]

קרוב ../images/Emo13.gif

דייקסטרא זה שיפוץ של BFS. מה שטוב ל-BFS טוב גם לדייקסטרא. ולהיפך.

 

[ronihp]

לא הבנתי כלום

כנראה שעוד לא למדנו את זה. רק התחיל הקורס. נתון לי מפה של רחובות ורוצים שארשום את כל המסלולים האפשריים מ-A ל-B במפה הספציפית שנתונה. לפי המפה, יש לי 3 דרכים: AB ADB ACB בסך הכל שלושה מסלולים. נתתי פתרון עם רשימה מקושרת פשוטה שמתחילה מ-A וכל רחוב שמחובר עם A יהיה פוינטר אליו ככה שלבסוף יבנה (דמיונית) מעין עץ.

 

[ronihp]

שאלה לגבי מיון של רשימה מקושרת

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

 

[IsraeliSecretToilets]

לצורך העניין..

הכי טוב לא להחזיר רשימה מקושרת למטרה זו

 

[ronihp]

הנה השאלה במלואה:

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

 

[vinney]

מערך או מחסנית

עם 3 משתני עזר.

 

[ronihp]

בטוח?

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

 

[vinney]

שים לב, אתה לא אמור לחפש

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

 

[ronihp]

פספסתי משהו

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

 

[vinney]

היי, פה זה הטריק ../images/Emo13.gif

אני לא אפתור לך את השאלה פה, תחשוב קצת

איך עושים את זה בלי לחשב כל פעם מחדש? נתתי לך רמז - 3 משתני עזר.

 

[ronihp]

שוב

אני מניח שאתה אומר לשמור מראש את ה-2 משתנים הקטנים ביותר לפני הכנסתם לאוסף. רק שהאוסף כבר נתון.

 

[vinney]

האוסף נתון?

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

 

[ronihp]

קורס במבני נתונים

נוסח השאלה שוב: "נתון אוסף של מספרים ממשיים השונים זה מזה. הצע מבנה נתונים....."

 

[vinney]

אז התשובה שלי נכונה, המבנה שהצעתי

מטפל באוסף כזה הכוונה לא שנתון לך אוסף מסוים, אלא נתון לך אוסף בו אתה צריך להשתמש במבנה שלך.