מנסה למצוא אלוגריתם יעיל מ-n² לבעיה מסוימת

[gshhary]

"להציץ באלכסון" נראה לי יהיה טוב

[שניצל]

אוקי, ואז מה?

תן לי אלגוריתם שלם, לא בחלקים, לא "אהה נראה לי שאני אעשה ככה".

[gshhary]

אוקי מתחיל מהתחלה ז"א =0 ו-k=0.

אם אני מוצא 0 אני בודק שמימין ומשמאל יש אפסים: אם אין - ממשיך באלכסון,אם יש - בודק את השאר, אם יש בודק שמלמעלה ומלמטה יש מספרי אחד, אם יש ממשך לבדוק אם אין ממשיך באלכסון

[שניצל]

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

[gshhary]

זה כ"כ מבלבל אותי...

אני מקווה שאני בכיוון: אם אני מוצא 0 אני בודק את כל השורה

זה מה שיש לי כרגע

[שניצל]

אין יותר מדי אופציות. יש בסך הכל שני בורות אפשריים - או ש-0 הוא בור, או ש-1 הוא בור.

איך תוכל בצורה הכי מהירה לפסול אחד מהם?

[Second Edition]

^כשאתה מתעלם מהאיברים שמתחת לאלכסון הראשי .

[gshhary]

מה ז"א

או ש-0 הוא בור, או ש-1 הוא בור ? איך 1 יכול להיות בור ?

[Second Edition]

הוא לא .

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

אין יותר מדי אופציות. יש בסך הכל שני בורות אפשריים - או ש-0 הוא בור, או ש-1 הוא בור.

איך תוכל בצורה הכי מהירה לפסול אחד מהם?

^כשאתה מתעלם מהאיברים שמתחת לאלכסון הראשי .

- - - תגובה אוחדה: - - -

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

[gshhary]

רגע, מה בדיוק בכוונה לאלכסון הראשי ? זה המתחיל ב-0 0 ?

[Second Edition]

נניח שחיפשת לבד בגוגל :

http://he.wikipedia.org/wiki/אלכסון_ראשי

- - - תגובה אוחדה: - - -

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

מה אני יכול לקצר ?

אין לך באמת בעיה : אתה יודע איך לפתור את הבעיה . אתה רק מתקשה לעמוד ביעילות . תתנתק ותחשוב על כיוון חשיבה שונה .

[gshhary]

אין אין אני פשוט דפוק בזה.

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

[שניצל]

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

אז אם אתה חושד לדוגמה ש-4 או 5 הם בור, אתה יכול בבדיקה אחת פשוטה, בוודאות לפסול אחד מהם.

[Gil28]

נראה לי הוא עדיין לא הבין את השאלה או מיהו בור.

בור אינו תא מסויים, בוא הוא אינדקס בודד(!) המציין שורה שלמה ועמודה שלמה.

[gshhary]

באמת נראה לי שלא הבנתי.

מה ז"א אינדקס בודד ?

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