שאלה על עצים בינארים מדעי המחשב ב'

[Idan-h]

"כתוב אלגוריתם המקבל עץ בינרי T ומדפיס עבור כל רמה את מספרה ואת סכומה."

האם יש דרך להפריד כל רמה, זאת אומרת מתי מתחילה רמה חדשה?

איך פותרים את התרגיל הזה?

תודה.

[MandariNa]

אני גם לא הכי בטוח בשאלה הזאת.. המורה שלנו אמר לנו פשוט לברוח מהשאלה אם אנחנו רואים אותה בבגרות.

הכוונה כל רמה זה כאילו "דור".. השורש של העץ הוא רמה 1 (או רמה 0, לא זוכר בדיוק) הבנים שלו זו רמה 2 (או 1 בהתאמה). הבנים של הבנים אלה רמה 3 (או 2 בהתאמה).. וכמה זה ממשיך.. איך לפתור מזה אין לי מושג

[Ghosthunter]

ע"י מחסנית.

עריכה: תחפש BFS זה אלגוריתם דיי מוכר לכך.

[Holy]

בשביל לדעת מה מספר האיברים בכל רמה ואת הסכום שלהם (בהנחה שמאוכסן בהם מספר) לא צריך BFS ולא צריך מחסנית

מבחינת זיכרון והזמן הכי מהר יהיה לעשות את זה ע"י סריקת back tracking כשאתה שומר בצד 2 מערכים בגודל של עומק העץ ובאחד אתה שומר את מספר האיברים באותה הרמה ובשני את הסכום

[iceman90]

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

if (tree has sons) then sum(tree)= sum(left(tree))+sum(right(tree))

else sum(tree) = value(tree)

BFS באמת יפתור את עניין הדרגות בצירה היעילה ביותר (באורדר של מספר הקדקדים בעץ = מעבר יחיד) פשוט חפש BFS או breath first search

מטי.

[Holy]

BFS אוכל זיכרון

אפשר להשיג אותה תוצאה בלי לבזבז את הזיכרון על המחסנית של BFS

[Idan-h]

טוב ככה,

ממה שהבנתי BFS זה "סריקה לפי רמות", שמכניסים את כל העץ/הצמתים לתור משמאל לימין או להפך. זה נכון?

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

יש לי דרך עם משתנה נוסף ורשומה אבל זה לא יעיל.

מישהו יכול להסביר לי יותר מפורט? תודה רבה, זה חשוב לי מאוד.

[Ghosthunter]

BFS עובד על תור(לעומת DFS - מחסנית DEEP). אם רשמתי מקודם ההפך - טעיתי.

תחשוב שכשאתה מכניס לתור אז אתה מכניס את האיברים לפי הסדר שנתקלת בהם, וכך אתה גם מוציא, כלומר, הרמות יהיו מסודרות לך בקבוצות(רמה 0 - השורש - לבד, רמה 1 - הבנים של השורש - ביחד, רמה 2 - הנכדים של השורש - ביחד וכו).

[iceman90]

אתה רוצה לחסוף בזכרון של מחסנית של BFS (למה מחסנית ?) ע"י הוספת מחסנית של רקורסיה (back tracking) ?... כן, זה יעיל.

מטי.

[Aurora Borealis]

האלגוריתם אפשרי רק ע"י סריקה לפי רמות, וזה בעצם אלגוריתם דיי פשוט.

אם יש לך את האלגוריתם לש הסריקה לפי רמות, אז פשוט צריך לערוך בו שינויים קטנים כדי שהוא ידפיס את הערכים שאתה צריך.

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

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

כי סה"כ, זו בגרות פשוטה, מי שכתב את השאלות לא יכול להמציא דברים מיוחדים, הוא משתמש בדברים ידועים מראש.

[Holy]

איזה מחנסית backtracking בדיוק?

איפה צריך מחסנית בדיוק?

הסיבוכיות זיכרון שאתה משיג עם חיפוש רקורסיבי פשוט (backtracking) הוא עומק העץ ולא מספר הצמתים בעץ במקרה הגרוע ב-BFS.

[Ghosthunter]

אם אתה מתכוון לזה: http://www.faust.fr.bw.schule.de/mhb/backtrack/btrnscen.htm.

זה נראה לי כמו O(n!) לעומת BFS שזה O(n) כאשר n זה מספר הקודקודים.

אבל אני לא בטוח שהתכוונת לזה.

ד.א אני ראשון http://en.wikipedia.org/wiki/Backtracking.

[Idan-h]

BFS עובד על תור(לעומת DFS - מחסנית DEEP). אם רשמתי מקודם ההפך - טעיתי.

תחשוב שכשאתה מכניס לתור אז אתה מכניס את האיברים לפי הסדר שנתקלת בהם, וכך אתה גם מוציא, כלומר, הרמות יהיו מסודרות לך בקבוצות(רמה 0 - השורש - לבד, רמה 1 - הבנים של השורש - ביחד, רמה 2 - הנכדים של השורש - ביחד וכו).

עדיין, אם העץ לא שלם איך אתה יודע לאיזה רמה שייך כל צומת?

למשל עץ עם בן יחיד ועוד בן יחיד. אם עץ היה שלם [כל רמותיו מלאות], אז הצומת השלישית שהיית מוציא מהתור הייתה שייכת לרמה הראשונה, אבל זה לא המצב. יכול להיות שאני מפספס פה משהו.

ויש שם לBack Tracking בעברית? האם זה סריקה בסדר סופי/תחילי/תוכי?

אתם מדברים במושגים שאני לא ממש יודע, תודה שוב

[Ghosthunter]

כל פעם כשאתה מכניס מישהו לתוך התור, אז המרחק ממנו לשורש זה המרחק מאבא שלו לשורש + 1. אתה מתחיל מהשורש(0), עובר לבים שלו(0+1) עובר לנכדים שלו(1+1) וכו'.

ד.א. ה- BFS עובד לכל גרף שהו(לא חייב להיות עץ).

[Holy]

למה אתם מסתבכים?! למה?!

פשוט עושים סריקה רקורסיבית רגילה על העץ בלי שום מחסנית