פורסם 2005 במאי 220 שנים "כתוב אלגוריתם המקבל עץ בינרי T ומדפיס עבור כל רמה את מספרה ואת סכומה."האם יש דרך להפריד כל רמה, זאת אומרת מתי מתחילה רמה חדשה?איך פותרים את התרגיל הזה?תודה.
פורסם 2005 במאי 220 שנים אני גם לא הכי בטוח בשאלה הזאת.. המורה שלנו אמר לנו פשוט לברוח מהשאלה אם אנחנו רואים אותה בבגרות.הכוונה כל רמה זה כאילו "דור".. השורש של העץ הוא רמה 1 (או רמה 0, לא זוכר בדיוק) הבנים שלו זו רמה 2 (או 1 בהתאמה). הבנים של הבנים אלה רמה 3 (או 2 בהתאמה).. וכמה זה ממשיך.. איך לפתור מזה אין לי מושג
פורסם 2005 במאי 220 שנים בשביל לדעת מה מספר האיברים בכל רמה ואת הסכום שלהם (בהנחה שמאוכסן בהם מספר) לא צריך BFS ולא צריך מחסניתמבחינת זיכרון והזמן הכי מהר יהיה לעשות את זה ע"י סריקת back tracking כשאתה שומר בצד 2 מערכים בגודל של עומק העץ ובאחד אתה שומר את מספר האיברים באותה הרמה ובשני את הסכום
פורסם 2005 במאי 220 שנים זה לא כזה מסובך... סכום בערכים ברמה מסויימת הוא סכום ערכיהם של הבנים... משהו כמוif (tree has sons) then sum(tree)= sum(left(tree))+sum(right(tree))else sum(tree) = value(tree) BFS באמת יפתור את עניין הדרגות בצירה היעילה ביותר (באורדר של מספר הקדקדים בעץ = מעבר יחיד) פשוט חפש BFS או breath first searchמטי.
פורסם 2005 במאי 220 שנים מחבר טוב ככה, ממה שהבנתי BFS זה "סריקה לפי רמות", שמכניסים את כל העץ/הצמתים לתור משמאל לימין או להפך. זה נכון? עדיין איך זה עוזר לי איך אני יודע שמתחילה רמה חדשה הרי בתור קיימים כל הצמתים בלי סדר מסויים. יש לי דרך עם משתנה נוסף ורשומה אבל זה לא יעיל. מישהו יכול להסביר לי יותר מפורט? תודה רבה, זה חשוב לי מאוד.
פורסם 2005 במאי 220 שנים BFS עובד על תור(לעומת DFS - מחסנית DEEP). אם רשמתי מקודם ההפך - טעיתי.תחשוב שכשאתה מכניס לתור אז אתה מכניס את האיברים לפי הסדר שנתקלת בהם, וכך אתה גם מוציא, כלומר, הרמות יהיו מסודרות לך בקבוצות(רמה 0 - השורש - לבד, רמה 1 - הבנים של השורש - ביחד, רמה 2 - הנכדים של השורש - ביחד וכו).
פורסם 2005 במאי 220 שנים אתה רוצה לחסוף בזכרון של מחסנית של BFS (למה מחסנית ?) ע"י הוספת מחסנית של רקורסיה (back tracking) ?... כן, זה יעיל.מטי.
פורסם 2005 במאי 220 שנים האלגוריתם אפשרי רק ע"י סריקה לפי רמות, וזה בעצם אלגוריתם דיי פשוט.אם יש לך את האלגוריתם לש הסריקה לפי רמות, אז פשוט צריך לערוך בו שינויים קטנים כדי שהוא ידפיס את הערכים שאתה צריך.אגב, אין שום סיבה לברוח משאלות על עצים בינאריים, כי לרוב זה מעקב רקורסיבי (יכול להיות גם לא רקורסיבי) על עץ בינאי, ואז זו שאלה מאוד פשוטה.ובכלל, זה לא טוב לבוא לבגרות כשאתה בא מראש עם מנטליות של "אני לא מתכוון לענות על השאלות מהנושא הזה, אז אני בכלל לא אתכונן עליהן", כי יכול להיות שדווקא השאלה של העצים תיהיה מאוד פשוטה (במקרה של מעקב), או שטיפה יותר מסובכת (בניית תת-תוכנית), אבל התוכניות לא מסתבכות יותר מידי, ואם יש לך לידך כמה תוכניות של עצים בינאריים, אז זה נפתר בקלות.כי סה"כ, זו בגרות פשוטה, מי שכתב את השאלות לא יכול להמציא דברים מיוחדים, הוא משתמש בדברים ידועים מראש.
פורסם 2005 במאי 220 שנים איזה מחנסית backtracking בדיוק?איפה צריך מחסנית בדיוק?הסיבוכיות זיכרון שאתה משיג עם חיפוש רקורסיבי פשוט (backtracking) הוא עומק העץ ולא מספר הצמתים בעץ במקרה הגרוע ב-BFS.
פורסם 2005 במאי 220 שנים אם אתה מתכוון לזה: http://www.faust.fr.bw.schule.de/mhb/backtrack/btrnscen.htm.זה נראה לי כמו O(n!) לעומת BFS שזה O(n) כאשר n זה מספר הקודקודים.אבל אני לא בטוח שהתכוונת לזה.ד.א אני ראשון http://en.wikipedia.org/wiki/Backtracking.
פורסם 2005 במאי 320 שנים מחבר BFS עובד על תור(לעומת DFS - מחסנית DEEP). אם רשמתי מקודם ההפך - טעיתי. תחשוב שכשאתה מכניס לתור אז אתה מכניס את האיברים לפי הסדר שנתקלת בהם, וכך אתה גם מוציא, כלומר, הרמות יהיו מסודרות לך בקבוצות(רמה 0 - השורש - לבד, רמה 1 - הבנים של השורש - ביחד, רמה 2 - הנכדים של השורש - ביחד וכו). עדיין, אם העץ לא שלם איך אתה יודע לאיזה רמה שייך כל צומת? למשל עץ עם בן יחיד ועוד בן יחיד. אם עץ היה שלם [כל רמותיו מלאות], אז הצומת השלישית שהיית מוציא מהתור הייתה שייכת לרמה הראשונה, אבל זה לא המצב. יכול להיות שאני מפספס פה משהו. ויש שם לBack Tracking בעברית? האם זה סריקה בסדר סופי/תחילי/תוכי? אתם מדברים במושגים שאני לא ממש יודע, תודה שוב
פורסם 2005 במאי 320 שנים כל פעם כשאתה מכניס מישהו לתוך התור, אז המרחק ממנו לשורש זה המרחק מאבא שלו לשורש + 1. אתה מתחיל מהשורש(0), עובר לבים שלו(0+1) עובר לנכדים שלו(1+1) וכו'.ד.א. ה- BFS עובד לכל גרף שהו(לא חייב להיות עץ).
פורסם 2005 במאי 320 שנים למה אתם מסתבכים?! למה?!פשוט עושים סריקה רקורסיבית רגילה על העץ בלי שום מחסנית
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.