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

[שניצל]

הממ אני תוהה, מותר לפונקציה להחזיר זוג ערכים?

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

(יש שפות שבהן מותר להחזיר שני ערכים, באמצעות העברת משתנים by reference)

[Ghosthunter]

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

בפסאודו קוד מותר להחזיר 2 משתנים. בC מותר להחזיר STRUCT.

השאלה היא אם זה מה שביקשו ממנו.

func(t)
1. if(t=nil)
1.1. return (0,0)
2. else
2.1. (a1,a2)<-func(left(t))
2.2. (b1,b2)<-func(right(t))
2.3. c2<-max(a2,b2)+1
3.4. return (a1+b1+c2,c2)

[Da-Funk]

אמממ מותר להשתמש במבנה נתונים נוסף אבל לא היה רשום שמותר להחזיר 2 ערכים..

אגב אלמוג לא למדתי עדיין קורס אלגוריתמים ואין לי מושג מה זה DFS או BFS אבל איך בדיוק זה יכול היה לעזור אני לא מבין ?

[can_not_lose]

http://en.wikipedia.org/wiki/Breadth-first_search

(מקור ויקיפדיה)

סבבה ....תקרא תישאל תבין L:) ....חוק חושב בנושא אלגורימם\מבני נתונים !!! שיעזור לך גם לבחינת כניסה לעבודה ...

זה לשבור את הראש לבד....

תנסה להבין את רעיון שבא מאוחרי זה(BFS)

[Da-Funk]

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

[can_not_lose]

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

כי ה DFS פותר לך את הבעייה ....

לא צריך רקורסיה ....

וכן....כי BFS ו DFS אלה שנושאים היחידים שאתה תלמד !!! אין עוד נושאים !!! הכול זה נגזרות של זה ...

[SerpentMage]

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

ו BFS ו DFS בהחלט פותרים את השאלה בקלות.

אפשר גם ע"י מעבר IN ORDER לעשות את זה - תמצא את העלה הכי שמאלי ואת הגובה שלו ותעבור IN ORDER בכל הצמתים. לכל צומת שתגיע אתה יכול לדעת את הגובה שלו יחסית לצומת אח שלו. אם אין לו אז הגעת אליו מהאב שלו או מהבן ואז אתה יכול לדעת את הגובה יחסית אליהם.

ופשוט תסכם...

בכל מקרה, O(N).

וכן....כי BFS ו DFS אלה שנושאים היחידים שאתה תלמד !!! אין עוד נושאים !!! הכול זה נגזרות של זה ...

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

[Da-Funk]

אני מביא לך דוגמה של עץ שמפילה את הרעיון של In-order . הרי אמרנו שגבהים (לא עומקים! בפעם המאה) נמדדים ע"פ המרחק הכי ארוך מהקודקוד לאחד העלים

O

\ /

O O

\ /

O O

/

O

הגובה של השורש הוא 4 של הבן השמאלי 3 של הנכד השמאלי 1!

כשאתה תגיע לבן השמאלי ביותר גובהו יהיה 1 תמשיך לאחיו ומה אז ? הגובה שלו 2 מה זה עזר לך ?

[can_not_lose]

אני מביא לך דוגמה של עץ שמפילה את הרעיון של In-order . הרי אמרנו שגבהים (לא עומקים! בפעם המאה) נמדדים ע"פ המרחק הכי ארוך מהקודקוד לאחד העלים

O

\ /

O O

\ /

O O

/

O

הגובה של השורש הוא 4 של הבן השמאלי 3 של הנכד השמאלי 1!

כשאתה תגיע לבן השמאלי ביותר גובהו יהיה 1 תמשיך לאחיו ומה אז ? הגובה שלו 2 מה זה עזר לך ?

איזה יופי פרח ...

[SerpentMage]

Da-Funk, אתה צודק, התבלבלתי עם גובה ועומק

הבהרה: אני לא עושה את הטעות הזו בד"כ!!

אוף... פאדיחות בפומבי..