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

[Second Edition]

בור יכול להיות רק באלכסון .

[שניצל]

בתרגיל הזה בור הוא מספר בין 0 ל-n-1. לא תא במערך. בור מציין גם שורה וגם עמודה. לדוגמה 5 הוא בור אם כל התאים בשורה 5 הם 0 וכל התאים בעמודה 5 (פרט לזה שבשורה 5) הם 1.

[gshhary]

אז בור יכול להיות רק באלכסון הראשי ? איך אני יודע את זה ?

[שניצל]

תגיד, אתה קראת את השאלה בכלל?

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

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

[gshhary]

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

[שניצל]

כי בור זה לא תא, בור זה מספר יחיד בין 0 ל-n-1.

[gshhary]

זה בדיוק מה שלא הבנתי: מספר יחיד בין 0 ל-n-1

אפשר בבקשה הסבר ?

[Gil28]

בתרגיל הזה בור הוא מספר בין 0 ל-n-1. לא תא במערך. בור מציין גם שורה וגם עמודה. לדוגמה 5 הוא בור אם כל התאים בשורה 5 הם 0 וכל התאים בעמודה 5 (פרט לזה שבשורה 5) הם 1.

זה למה.

[karpazi0]

תקרא את הדוגמא. ב-A יש בור ב-3

[gshhary]

תודה רבה.

[Second Edition]

הצלחת ? הגשת ?

[gshhary]

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

[shashaa]

רמז 1: תחשוב איזה תנאי חייב אבל לא מספק כדי להתקיים על תא אחד של בור(כלומר על תא ספציפי חייב להתקיים תנאי X כדי שהוא יהיה בור, אבל אם הוא מתקיים זאת לא ערובה לכך שזה יהיה בור. אני מדבר על תנאי לתא ולא לשורה/עמודה)

רמז 2: לא חייבים לסרוק תאים שאין טעם לסרוק אותם, או שלא נחוץ לסרוק אותם

ספויילר:פתרון(כתבתי בפייתון): http://pastebin.com/gyxvhHRj

[שניצל]

הפתרון שלך לא באמת יעיל... אני סבור שהוא גם בסיבוכיות של n בריבוע.

[shashaa]

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