שאלות לגבי מבחן 2010

מנהל: TA_Isana

שאלות לגבי מבחן 2010

הודעהעל ידי Brk » 12:05 09/07/2010

יש לי מספר שאלות לגבי התשובות שבפירסמתם למבחן 2010.
בכול אופן לגבי שאלה 2 סעיף ג,אני מצטט " נתון גרף קשיר ולא מכוון ידוע שמשקל של הקשתות שונים זה מזה ורק לשתי קשתות יש אותו משקל"
הפיתרון שלי לבעיה(לא מה שרשמתי במבחן): נשתמש באלגוריתם של קרוסקל רק שנשנה אותו טיפה נעזר בשני משתני עזר: prev_w,curr_w.
ומשתנה flag=true ,שמייצג האם קיים יחיד(true) אחרת false. נאתחל את curr_w=prev_w=0
נוסיף שינוי ללולאה באלגוריתם של קרוסקל,נשמור כול צלע שאנו מבקרים בה בcurr_w
ונשאל האם הצלע הנוכחית שווה לצלע הקודמת בסדר המיון (if(curr_w=prev_w אם כן נשאל האם זה סוגר מעגל ? אם כן משמע יש אפשרות לשני עצים פורשים שונים ונשנה את flag
לfalse .
לפני המעבר לצלע הבאה: נבצע prev_w=curr_w כך שתמיד נשמור את הצלע שקדמה לנו.

האם זה עונה על השאלה?

בנוסף יש לכם טעות דפוס בפתרונות של שאלה 3 עם המטריצה:
כאשר אתם סוכמים את השורות אתם מכניסים את זה למיקום הi,i במקום הi,j.
נערך לאחרונה על ידי Brk בתאריך 10:35 10/07/2010, נערך פעם אחת בסך הכל.
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלות לגבי מבחן 2010

הודעהעל ידי TA_Yoni » 10:23 10/07/2010

יהיו שני MST שונים לגרף אם נוכל להחליף בין הצלעות ומשקל הגרף יהיה זהה. זה נכון מכיוון שלגרף עם צלעות בעלות משקל שונה קיים MST יחיד. לכן אם קיימות שתי צלעות בעלות משקל זהה ושאר הצלעות בעלות משקל שונה, אם קיימים שני MST הם יהיו שונים זה מזה רק בצלעות אלו.
אם הבנתי נכון את הפתרון שלך אז זה בדיוק מה שהוא בודק.
נערך לאחרונה על ידי TA_Yoni בתאריך 15:07 10/07/2010, נערך פעם אחת בסך הכל.
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: שאלות לגבי מבחן 2010

הודעהעל ידי Brk » 10:35 10/07/2010

תודה יוני על התשובה המהירה! :D
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלות לגבי מבחן 2010

הודעהעל ידי TA_Yoni » 15:04 10/07/2010

הבהרה:
הכוונה שלי הייתה שאם נוסיף את הצלע שאינה ב MST ל MST והיא תסגור מעגל בMST שהצלע האחרת חלק ממעגל זה אז קיימים שני עצים.
("הצלע" ו"הצלע האחרת" בעלות אותו משקל)
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: שאלות לגבי מבחן 2010

הודעהעל ידי Brk » 15:28 10/07/2010

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

כן לזה התכוונתי
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלות לגבי מבחן 2010

הודעהעל ידי TA_Yoni » 15:32 10/07/2010

חשוב לציין:
במקרה ונסגר מעגל צריך לבדוק שהצלע הקודמת אכן חלק מאותו מעגל
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד

cron