דף 1 מתוך 1

שאלה לגבי 1ב במבחן (למתרגלים)

נשלח: 21:13 05/08/2009
על ידי JonathanS
היי,
קיבלתי היום את הסריקה של מחברת הבחינה וראיתי שהתשובה שלי זהה מבחינת הלוגיקה שלה לתשובה שפירסמתם, אולם בסריקת המחברת נכתב שהמסלול שמצאתי הוא לא בהכרח המסלול הקצר ביותר. אני אודה להסבר מדוע האלגוריתם שהצעתי הוא אכן לא נכון, מכיוון שלא מצאתי בו כל פגם והוא למעשה זהה לוגית למה שפירסמתם.

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

תודה רבה,
יהונתן