חידה

[M486]

חידה

שלום לכולם

אני בודק לראשונה את כוחכם בנסיון למצוא אלגוריתם לא פשוט, שאני יודע שאפשר למצוא אותו בודאות: נתון מערך מספרים דו-מימדי ריבועי (מטריצה nxn). במערך אפשריים הערכים 0 או 1 בלבד. נתון כי ערך איברי האלכסון הראשי הוא 0 (כלומר M(1,1)=0, M(2,2)=0 וכו'). השאר לא ידועים. דרוש אלגוריתם בסיבוכיות חיפוש (O(n אשר מוצא שורה שבה יש רק אפסים שמצטלבת עם עמודה שיש בה רק 1-ים, מלבד נקודת ההצטלבות, בה יש 0. לדוגמא: 1 1 00000 1 1 אם קיים כזה דבר - תוחזר מס' העמודה (בדוגמה תוחזר מס' העמודה-4), אחרת יוחזר NULL. n להזכירכם- מס' העמודות/שורות של המטריצה. מאותגרים, קדימה

 

[DadleFish]

מה מסובך בזה?

 

[M486]

אם זה לא מסובך, תפתור ../images/Emo13.gif

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

 

[MegaMango]

אני חושב שאני נכנע ._.

זה נראה בלתי אפשרי! מצד שני, יש את אלגוריתם select שלמדתי באלגו' 1 ועד היום אני לא מבין איך הוא פועל (גם על מטריצה ובסיבוכיות n) -warning: frustration ahead- אם הייתי יכול להתייחס לשורה במערך כאל מספר!!..! כל מה שאני יודע הוא שאם מצאתי עמודת אחדים מסויימת אז המקום שבו היא קטועה חייב להיות רק באלכסון של האפסים ובעצם לפי אינדקס עמודת האחדים יש לי גם את אינדקס שורת האפסים. אבל אפילו אם מצאתי עמודת אחדים אני צריך לעבור על השורת אפסים כדי לבדוק שהיא באמת מלאה רק באפסים וזה לוקח n פעולות. אם זה לא עבד, אני צריך להמשיך הלאה בסריקה (שכנראה תהיה תלויה בn) ואז עברתי את הסיבוכיות הרצויה.. אז אולי עם התקדמות במקום אחד אנייכול להסיק על מקומות אחרים..אבל לא! אין שום קשר בין התאים במטריצה! סתם ערימת ביטים טמאה!

 

[MegaMango]

רגעעע

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

 

[MegaMango]

יאי ^____^

אני חושב שיש לי משהו D: -אגוז! הרעיון הוא לפסול שורות. נתחיל מ 1,1במטריצה (נגיד שאין אפסים באינדקסים) ונתקדם על האלכסון הראשי. בכל פעם שאנחנו רואים שמלמטה ומלמעה לתא שבו אנחנו נמצאים יש יש אחד ומימין ושמאל יש 0, אנחנו אומרים שיש צ'אנס שזה התא של ההצטלבות. עכשיו, נתחיל לעבור על שורת האפסים. אם הגענו לאפס, אז אנחנו יודעים שבעמודה שבה אנחנו נמצאים כבר אין עמודת אחד-ים, אז פוסלים אותה. ממשיכים עם זה עד שמגיעים לסוף המערך ומגלים שורת אפסים של ממש או עד שמגיעים לאחד ויודעים לפסול גם את התא שחשבו שיכול להיות ההצטלבות. אם לא נחזור על שורות שפסלנו אז נסיים את כל העסק הזה בO של n (כי ככל שסריקה יוצאת ארוכה יותר, אנחנו פוסלים יותר שורות. סכום הפסילות וסכום הבדיקות ביחד בכל הפעמים הוא מקסימום n)

 

[MegaMango]

יש גם את העניין של לבדוק את האחדים

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

 

[MegaMango]

אוף אני כזה טיפש זאת שאלה קלה ><

ברגע שמתחילים לעבור עם האצבע על הדוגמא זה מיידי. שאלה.. כשאעבוד בחברת מחשבים נורמלית (למרות שאין לי מושג מה אני אמור לעשות שם) אם אני לא אצליח לפתור משהו ברמה הזאת יעיפו אותי לאלף עשרים וארבע עזאזל, נכון? הי! חמישה הודעות שלי ברצף! לא מעיפים אנשים מהפורום על דברים כאלה? אני צריך להתאקלם P: פעם ראשונה שאני ממש מגיב בפורום ולא רק קורא...

 

[MegaMango]

חמש* וכן, אני לא ישן בלילה. בדיוק

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

 

[vinney]

לי יש תירוץ יותר טוב

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

 

[vinney]

תגיד, יש לך נדודי שינה? ../images/Emo13.gif

 

[M486]

הפתרון שלך לא ברור לי

קודם כל, כל הכבוד על המאמץ הראוי!!! אני לא מבין מה כוונתך מהשלב שרשמת "נתחיל לעבור על שורת האפסים". מהשלב הזה, די ברור ששאר מה שרשמת עוד יותר לא ברור לי, לצערי. אם כוונתך לרוץ שורה שורה, אתה יכול לעבור שורות שלמות, שרק בסוף שלהן תגלה שהן מקלקלות, ואז זה On^2. שים לב שאם תרוץ על שורות כל פעם עד איבר האלכסון אז תרוץ 3+2+1+...+n שזה בטור חשבוני (2^O(n סתם הערה כדרך אגב: הבעייה היא הפשטה בעצם של בעיה בתורת הגרפים, מציאת קודקוד שדרגת הכניסה שלו 1-

ודרגת היציאה היא 0.

 

[M486]

איפה שרשום

הכוונה כמובן ל- | V | - שזה מס' הקשתות/צלעות בגרף. ותודה לתפוז.

 

[MegaMango]

רשמתי את זה בזריזות מתוך

התקף רגשות נחיתות P: הרעיון הוא לולאה אחת שרצה על האלכסון(על האלכסון עצמו, כלומר (1,1) (2,2) , (3,3) עד (n,n) . בכל פעם שאנחנו מתקדמים בלולאה(ובפעם הראשונה) נבדוק האם התא מימין הוא אפס.אם לא, אז אנחנו יודעים שהשורה שלנו ובעצם גם העמודה(כי השורה והעמודה חייבים להיות בעליו אותו אינדקס) פסולים ונמשיך הלאה. אם הוא כן אפס, אז השורה שלנו חשודה כשורת אפסים. נתחיל לרוץ עליה לכיוון ימין ונבדוק כמה אפסים יש(אנחנו לא מתחילים לרוץ על כל השורה, רק על החלק שבין האלכסון לקצה הימני של המטריצה באותה שורה שבה היינו). על כל אפס שמצאנו אנחנו יודעים שהעמודה שבה אנחנו נמצאים כבר לא עמודת אחדים ולכן אפשר לפסול גם אותה וכך גם אם פתאום נמצא אחד ונחליט שגם השורה שלנו עכשיו לא טובה, נדע שלא צריך להמשיך לסרוק את כל השורות מהמקום שבו היינו אלא רק השורה שנמצאת בגובה העמודה שהגענו אליו. מספר הקידומים של הלולאות שבודקות אפסים בכל הפעמים ביחד שווה למס' הפעמים שפוסלים שורות ובגלל שיש רק n שורות לפסול, זה לא עובר את o(n(. בנוסף, אחרי שמצאנו שורת אפסים מצד ימין לנקודה, נבדוק האם מצד שמאל שורת האפסים ממשיכה(אם הגענו למצב שבו אנחנו בודקים את הצד השני , אז כבר פסלנו את כל השורות והעמודות האחרות ולכן זה דבר שיקרה רק פעם אחת ולא מפריע לסיבוכיות) ואם מצאנו שזו שורת אפסים מלאה , נבדוק אם יש גם עמודת אחדים מתאימה. אם מצאנו שהכל מתקיים, אז התא שבדקנו בהתחלה ונראה חשוד הוא התא הנכון. אם לא, ממשיכים לשורה הבאה שעדיין לא פסלנו. אני מקווה שזה יותר ברור >.> אני ממש לא חשבתי על להפוך את זה לבעיית גרפים..אבל זה גם נכון.

 

[DadleFish]

לא טוב,

כי אם בכל השורות מתקיים למשל שהאלכסון הוא 0 וכל התאים שמימין לאלכסון הם 0, אז אתה תרוץ על כל השורות, ואז זה (O(N^2 (למרות שאתה רץ "רק" על כל המשולש העליון למעשה).

 

[MegaMango]

אני רק רץ עד שאני מוצא אחד, לא על

כל השורה

 

[DadleFish]

אבל במקרה הגרוע תרוץ על כל השורה

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

 

[MegaMango]

אם רצתי על כל השורה אז פסלתי את כל

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

 

[DadleFish]

אההה ../images/Emo45.gif

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

 

[M486]

הפתרון שלך דומה מאוד

לפתרון, הוא מעט שונה מזה שהתכוונתי אליו. הפתרון הוא להשוות כל פעם אינדקס של שורה מסויימת ועמודה מסויימת (אך שמס' העמודה שונה ממס' השורה), להשוות, ובהכרח לפסול אחת מהשניים. בדרך זו שבה פוסלים כל פעם N/2 איברים, נעשה סה"כ N-1 פעמים השוואות, ולבסוף עבור העמודה הנותרת נרוץ עוד N פעמים כדי לדעת אם יש להחזיר אותה. בכל מקרה כל הכבוד!

ואחלה פורום