שאלה אלגוריתמית

[mosh2308]

שאלה אלגוריתמית

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

תודה מראש

 

[HackPoint]

זו שאלה על גראפים עם עצים

http://en.wikipedia.org/wiki/Graph_traversal
&nbsp
אתה צריך פסאודוקוד או מימוש? אם כן אז באיזה שפה?

 

[mosh2308]

תודה. צריך מימוש ב- .net למשל vb.net

 

[Royi Namir]

לא ברור

אתה מכניס ילד ואתה רוצה לראות אם יש לו סבא או אבא או יותר?
או שאתה מכניס ילד ואתה רוצה לבדוק אם יש לו ילדים וכו ?
מה הקלט שלך תן דוגמא

 

[mosh2308]

דוגמא

על קלט של 2 מספרים לבדוק האם הראשון הוא בן או נכד או נין וכו' של השני

 

[טרול המתכנן]

יש לתת *האם* יש קשר משפחתי, או *את הקשר המשפחתי* ??

 

[mosh2308]

האם יש קשר משפחתי

 

[mosh2308]

המשך הסבר

על קלט של 2 מספרים לבדוק האם הראשון הוא בן או נכד או נין וכו' של השני

 

[marvin2]

ומה הדרישות ?

O של 1 ? מה מבחינת זיכרון ?
&nbsp

 

[marvin2]

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

פשוט מחזיקים ב SET כלשהו שתומך בהוצאה של O1 זוג מספרים - את הבן ואת הרפרנס לאבא. או שאני מפספס משהו בשאלה ?
&nbsp

 

[Royi Namir]

Try this

http://i.imgur.com/Y2O8Ws0.png

שימוש ברקורסיה
שים לב שהוא בודק קשר של אב לבן ולא בן של אב

כלומר אם תתן לו אריה הוא ידע להגיע לחתול בית
אבל אם תתן לו חתול בית - הוא לא ידע להגיע לאריה ( למרות ששינוי קטן בקוד יטפל גם בזה)

הקוד הנל בא להמחיש פיתרון וכמובן שאפשר לשפר הקוד

קוד:
http://jsbin.com/mosiyo/1/edit

 

[HackPoint]

אתה מתכוון לכתוב קוד

שאנשים ידעו לקרוא. אני הייתי ממליץ לכתוב את הקוד בצורה שהיא יותר implicit,
לצערי אין לי זמן עכשיו אבל אני אכתוב דוגמא כשאגיע הבייתה.
&nbsp
הlinq נראה לא קריא במיוחד.

 

[Royi Namir]

הכל בסדר זו רק דוגמא להמחשה כפי שרשמתי

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