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

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

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

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

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

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

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

נערך 2013 בדצמבר 2511 שנים על-ידי gshhary

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

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

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

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

זה למה.

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

תודה רבה.

הצלחת ? הגשת ?

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

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

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

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

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

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

נערך 2014 בינואר 411 שנים על-ידי shashaa