חידת אלגוריתם

[טלמון סילבר]

בנוגע לאותו אלגוריתם,

אפשר להיפתר לגמרי מבעיית הזיכרון בדרך הפשוטה הבאה: לרוץ כל פעם על שתי שורות שכנות, ותוך כדי הריצה עליהן לחשב את ה-m-ים. טוב, אולי יֵצֵא לי לחשוב על אלגוריתם אחר.

 

[טלמון סילבר]

../images/Emo62.gif אנסה לפשט אותו אלגוריתם.

1. מאפסים את מונה הגושים. 2. רצים שורה-שורה. 3. מחפשים פיקסל שחור. 4. אם מצאנו פיקסל שחור, מוסיפים 1 למונה הגושים. 5. רצים על כל הפיקסלים השחורים החל מזה שמצאנו, עד שנגיע לפיקסל לבן. 6. עבור כל פיקסל (מהקטע השחור שמצאנו) בודקים את הפיקסל שמעליו. כל פעם שהופיע לראשונה פיקסל שחור מעל הפיקסל שלנו, מורידים 1 ממונה הגושים. כלומר, בפעם הראשונה שמצאנו (אם מצאנו) פיקסל שחור מעל הפיקסל שלנו, מורידים 1 ממונה הגושים, ואם בשורה שמעלינו ממשיכים להיות פיקסלים שחורים, אז לא עושים שום דבר, אבל אם הופיע מעלינו פיקסל לבן, אז כשיופיע (אם יופיע) מעלינו שוב פיקסל שחור, אז שוב נוריד 1 ממונה הגושים, ומרצף פיקסלים שחורים שיהיו מעלינו בהמשך, שוב נתעלם, עד שנגיע לפיקסל לבן מעלינו, וכו'. 7. כשנסיים את הקטע השחור, נמשיך הלאה באותה השורה אל סעיף 3. אם אינני טועה, זה בעצם אותו אלגוריתם שהצעתי קודם, אבל נראה יותר פשוט.

 

[עריסטו]

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

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

)

 

[טלמון סילבר]

מה פתאום! ../images/Emo62.gif

אפשר למשל ככה: 1. מאפסים את מונה הגושים. 2. רצים על כל הפיקסלים. 3. אם הפיקסל לבן, מתעלמים ממנו. 4. אם הפיקסל שחור, מבצעים את הפעולות הבאות: 4.1. אם משמאלו ומעליו יש פיקסלים לבנים, מוסיפים 1 למונה הגושים. 4.2. אם משמאלו ומעליו יש פיקסלים שחורים, ובאלכסון שמאלה-למעלה יש פיקסל לבן, מחסירים 1 ממונה הגושים. 4.3. בשאר המקרים לא עושים שום דבר. סוף. השאלה היא, אם זה באמת יותר מהיר מהאלגוריתם הראשון שהצעתי. דבר ראשון, תלוי איך מוצגים הנתונים. אם מדובר בפיקסלים פיזייםפ בצג, שבאמת צריך לקרוא אותם אחד-לאחד, או שאפשר לדבר על משתנים רגילים, שגם יש לנו אפשרות לבחור את המבנה שלהם, כמו שהצגתי ב-MUMPS (ואפשר להציגם גם אחרת). דבר שני, תלוי מהו האופי הרווח של הגושים. ברור, שבמקרה של לוח שחמט האלגוריתם האחרון, הפשוט יותר, גם יהיה מהיר יותר. לעומת זאת, בדוגמה של הציור שהצגת, חוששני שהאלגוריתם הראשון שהצעתי יהיה מהיר יותר, וגם די פשוט לכתיבה, לפחות ב-MUMPS. אם לא אתעצל, אריץ תכנית שתשווה את זמני הביצוע של שני האלגוריתמים.

 

[טלמון סילבר]

בדקתי ../images/Emo26.gif

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

 

[עריסטו]

../images/Emo127.gif../images/Emo127.gif../images/Emo127.gif../images/Emo127.gif../images/Emo127.gif../images/Emo127.gif

 

[עריסטו]

פסאודו-קוד למי שלא הבין

את האלגוריתם של טלמון: יש במערך m שורות הממוספרות 1 עד m, ו - n עמודות הממוספרות 1 עד n.

s=0; FOR i=2 TO m-1 FOR j=2 TO n-1 IF pixel(i,j)=black AND pixel(i+1,j)=white AND pixel(i,j+1)=white THEN s=s+1; IF pixel(i,j)=black AND pixel(i+1,j)=black AND pixel(i,j+1)=black AND pixel(i+1,j+1)=white THEN s=s-1; NEXT j NEXT i RETURN s;​

 

[סאביבית]

ומה לגבי מי שלא הבין למה זה נכון?

 

[טלמון סילבר]

האם מובן האלגוריתם הראשון שהצעתי?

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

 

[Alkhimey]

נסיון

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