האלגוריתם שלי לשאלה 4

צפה בנושא הקודם צפה בנושא הבא Go down

האלגוריתם שלי לשאלה 4

הודעה  Admin on Sun May 10, 2009 4:47 am

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

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

הרעיון הרקורסיבי:
הפונקציה צריכה לקבל מצביע לצומת כלומר TreeNode* ומצביע למשתנה שלם int* שזהו בעצם המשתנה שהגדרנו במעטפת בצירוף &.

שני תנאי עצירה - אם אני NULL אז אחזיר ערך 0. אם אני עלה אז אחזיר ערך 1.

המקרה הכללי - אם אני לא NULL ולא עלה,

*ראשית עליי לברר האם אני החולייה המקשרת של המסלול הכי ארוך בעץ (שנכון לעכשיו הוא 0 כפי שהגדרנו בתוך המשתנה). כלומר, לשלוח את הפונקציה הרקורסיבית גם על הבן הימני שלי וגם על הבן השמאלי שלי, ואשמור את התוצאות של שתי הריצות הללו בשני משתנים. המשתנים האלה הם בעצם הגבהים של הבנים שלי. עכשיו נחבר את שני הגבהים של הבנים ונשווה סכום זה לערך שנמצא במשתנה המתעדכן שלנו. אם הסכום הזה גדול יותר, משמע "אני החולייה שמקשרת את הקוטר הארוך ביותר נכון לעכשיו" ולכן נעדכן את המשתנה הזה להכיל את הסכום המדובר.
*שנית עליי להחזיר למי שקרא לי (לאבא שלי) את הגובה שלי, וזאת אעשה ע"י השוואת הגבהים של הבנים שלי (ששמורים לי כבר בתוך המשתנים ממקודם) ואחזיר את גובהו של הבן הגבוה יותר + 1 (לספור גם את הקשת שמחברת ביני לבין אבי).

זהו

זה עובד, וזה הכי יעיל שיכול להיות. בהצלחה.
cheers
avatar
Admin
Admin

מספר הודעות : 62
Join date : 08.04.09
Age : 32

צפה בפרופיל המשתמש http://csmta.forumhebrew.com

חזרה למעלה Go down

אלגוריתם מעולה :)

הודעה  talmidonet on Sun May 10, 2009 5:22 am


מר מנהל,

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

sunny ניתן לבצע אבחנה בין תאור של אלגוריתם לבין תאור של קוד. מה שתיארת מכיל מרכיבים של תאור קוד (שימוש בתחביר ספציפי של קוד, כגון TreeNode*), בעוד שתאור של אלגוריתם הוא א-שפתי, כלומר לא מניח שפה מסויימת אלא כללי לכל השפות.

תלמידונת

avatar
talmidonet
by ref
by ref

מספר הודעות : 12
Join date : 10.05.09
Age : 31
מיקום : תל אביב

צפה בפרופיל המשתמש http://talmido.net/

חזרה למעלה Go down

Re: האלגוריתם שלי לשאלה 4

הודעה  Admin on Tue May 12, 2009 6:37 am

קודם כל תודות על המחמאות, תלמידונת
אני מניח שקראתי לזה תיאור של אלגוריתם, ובאמת הכלתי שם מושגים שמקושרים לקוד של c, אבל כל עוד אנשים יבינו איך לפתור את הבעיה - אני מבסוט! Smile
הצדעה
avatar
Admin
Admin

מספר הודעות : 62
Join date : 08.04.09
Age : 32

צפה בפרופיל המשתמש http://csmta.forumhebrew.com

חזרה למעלה Go down

צפה בנושא הקודם צפה בנושא הבא חזרה למעלה


 
Permissions in this forum:
אתה לא יכול להגיב לנושאים בפורום זה