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

ה-k בדוגמה הוא 3 (הספירה מתחילה מימין, לא משמאל... זה כנראה מה שבלבל אותך).

אלכסון מוכלל זה אוסף התאים [mat[k][(k+c)%n כאשר c הוא קבוע כלשהו.

נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0,

ובעמודה ה- k -ית כל הערכים הם 1

הרי על פי ההגדרה שנתת בגוף השאלה לבור, השורה ה-k היא 0 והעמודה ה-k היא 1, (מלבד k,k) ובמטריצה A הבור הוא ב-k=3. והצומת בין השורה לעמודת הבור (מה שכינית בתור בור) באינדקס 3,3.

ועוד משהו של לא הבנתי איך אני אשמור את כל [k][k]

איפה ראית שאתה צריך לשמור אותם?

גם באלגוריתם שאני הצעתי וגם בזה של שניצל, צריך לשמור מערך חד ממדי באורך k, כדי לשמור חשודים בתור בור, ולצמצם את רשימת החשודים לחשוד יחיד (צמצום החשודים היא הנקודה בה שני האלגוריתמים נבדלים).

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

udii, ע"פ הניסוח של השאלה שלך הבורות יכולים ליהיות רק על האלכסון הראשי ("נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0, ובעמודה ה- k -ית כל הערכים הם 1 (חוץ מהאיבר [k][k] עצמו שהוא 0).")

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

[עריכה]

טעות שלי, תשכחו ממה שאמרתי.

קראת את הת'רד לפני שהגבת?

הפתרון שנתת הוא הפתרון הפשוט ולא יעיל. אנחנו דיברנו על פתרון יעיל ב-(O(n.

אני לא מבין את השאלה (חשד לחוסר דיוק בניסוח השאלה )

נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0,

ובעמודה ה- k -ית כל הערכים הם 1 (חוץ מהאיבר [k][k] עצמו שהוא 0).

פלט: האם קיים מספר k המהווה בור במערך? אם כן, הדפס את ערכו.

לדוגמא: במערך במערך B אין בור במערך A יש בור

A B

0 1 1 0 1 0 1 0 0 0 1 0

0 0 1 1 0 1 1 1 1 0 0 1

1 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1

0 0 1 1 0 1 1 0 1 0 1 0

1 1 1 0 1 0 0 1 0 0 0 1

נאמר [k][k] צריך להיות 0

תביטו על מערך A השורה של הבור היא 3 והעמודה היא 2 ( מתחילים מ 0 )

לכן במקרה שלנו הנקודה K,K היא 3,2 לפי ניסוח השאלה היית מצפה שהנקודה תיהיה 3,3

איזה מצחיק אני ;D הקופי פסט יצא הפוך למעשה הנקודה היא באמת 3,3

קראת את הת'רד לפני שהגבת?

הפתרון שנתת הוא הפתרון הפשוט ולא יעיל. אנחנו דיברנו על פתרון יעיל ב-(O(n.

קראתי, טעות שלי, חשבתי שהיה בלבול בנוסח השאלה כי התייחסתי למערכים משמאל לימין..

כמו שאמרתי, המספור מתחיל מימין ולא משמאל.

העמודה שמלאה ב-1 הוא עמודה 3, לא 2.

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

עשיתי copy paste וזה יצא הפוך

למעשה הנקודה באמת 3,3

עריכה

הבנתי

כמו שאמרתי, המספור מתחיל מימין ולא משמאל.

העמודה שמלאה ב-1 הוא עמודה 3, לא 2.

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

התחלתי לערוך לפני ששלחת את ההודעה שלך, לא הייתי עורך אם הייתי רואה את התגובה שלך.

סוף סוף הבנתי ...

שניצל קבל ח"ח על האלגוריתם הגאוני

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

לכן החלטתי להשקיע מעט ולהסביר את זה במצגת. קבלו:

אם ישנה בעיה בתאימות התצוגה תודיעו לי כדי שאוכל לתקן (2 גרסאות, אחת לאופיס 2007 ואחת ל-2003).

[attachment deleted by admin]

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

אז אם למישהו יש לינקים לשאלות ותשובות מהסוג הזה אשמח

http://vlib.eitan.ac.il/ds1/

http://www.underwar.co.il/library.asp?Page=CS

והכי טוב מכולם לדעתי : www.dsdb.co.nr/