בעיה שכזו:

[joeher]

בעיה שכזו:

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

 

[vinney]

תתרגם לאיטרטיבי

כל אלגוריתם רקורסיבי ניתן לתרגם לאיטרטיבי באותה יעילות זמן ריצה

 

[DadleFish]

.... או יעיל יותר.

 

[joeher]

נכון אבל יכול להיות שלמישהו יהיה

רעיון הרבה יותר טוב.. וגם ברקורסיה זה ממש טריואלי, באיטרציות זה לא לגמרי ברור שאפשר לבצע עם פחות זכרון, נראה לי שאני מחליף את זכרון ה STACK של הרקורסיה בזכרון DATA למשתנים.

 

[vinney]

למה הצביעה רקורסיבית מלכתחילה?

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

 

[joeher]

ודאי - אבל צריך להמשיך לצבוע את

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

 

[DadleFish]

אני מניח...

שאין שום הנחות לגבי השטחים הלבנים? למשל, אם הם CONVEX אז אפשר להשתמש באלגוריתם פשוט הרבה יותר.

 

[joeher]

לצערי הרב - יכול להיות אפילו שיש

בהם חורים.

 

[selalerer]

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

שכל פעם משתמשת בערכים האחרונים שדחפת למחסנית, רקורסיה במימוש עצמי, מה עוד יש לעשות?

 

[joeher]

תראו חבר'ה - אני מחפש רעיון אחר

לא שיפור של מה שאני כבר יודע. למשל משהו שנראה לא רע זה: נגדיר קבוצה של צבעים ונתחיל לסרוק. פגשנו לבן נצבע אותו בצבע A וכך את שאר השורה עד לשחור פגשנו עוד לבן נקח צבע חדש ונמשיך. אם פגשנו לבו שיש לו שכן צבוע נצבע באותו הצבע (ואם לא נקח צבע חדש). אם הסתיימה שורה ולא השתמשנו בצבע "משומש" נספור אחד ונחזיר את הצבע לשימוש חוזר. יש כאן בעיה עם צורת קעורות (למשל X) שנתחיל עם 2 צבעים והם יפגשו אבל זה סיבוך קל שניתן לפתרון. אני לא אוהב את הסיבוך הקל הזה...