בבקשה עזרה בשאלה ב-JAVA...

[tvi]

בבקשה עזרה בשאלה ב-JAVA...

תודה מראש!

 

[vicz]

תפרט במה אתה מתקשה

כי בפורום לא נותנים פתרונות שלמים האם אתה מתקשה לפתח אלגוריתם לתוכנית? מה הרעיונות שלך?

 

[h a j b i]

מצטרף לשאלה, הממ"ן הזה קשה במיוחד

הקושי הוא הוא כמובן לפתח את האלגורתים בסיבוכיות של N. אם מוצאים פיתרון בסיבוכיות של N^2 (דבר שהצלחתי לעשות) מאבדים 15 נקודות. כדי להגיע לסיבוכיות של N אני צריך מספר מסויים של לולאות (כנראה 3) לא מקוננות. הרעיון העיקרי לפי מה שהבנתי זה להתחיל לחפש על האלכסונים הראשיים כי ה"בור" חייב" לעבור שם אבל מעבר לזה גם לי אין ממש רעיונות. נסמך לסיוע (כן, אני יושב על הממ"ן הזה עכשיו בשעה כזאת...)

 

[h a j b i]

נסמך = נשמח ../images/Emo163.gif

 

[vicz]

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

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

 

[h a j b i]

תראה, מעכשיו מי שיטען שהרמה בפתוחה נמוכה

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

 

[Maha Vailo]

דווקא לא הייתי מסתכל על האלכסון הראשי

שים לב שלא יכולים להיות שני בורות באותה מטריצה - מה שאומר שבמקום לבדוק כל מספר אם הוא בור, עדיף לבדוק אם הוא לא בור - כלומר אפשר עם k-1 השוואות של שתי אפשרויות לבור, להראות שלפחות אחת מהאפשרויות לא יכולה להיות בור. ככה נשארים עם אפשרות אחת שצריך לבדוק אם היא בור.

 

[HaifaMan]

../images/Emo45.gifזה גם הרעיון שלי

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

 

[tvi]

לא הבנתי את התשובה, אפשר דוגמא קצרה?

תודה!

 

[Maha Vailo]

דוגמית

אם תבדוק למשל את התא בשורה 1 עמודה 2 (מתחיל משמאל למעלה, ללא שורה ועמודת אפס) - אם התא הוא שווה לאפס אז k=2 לא יכול להיות בור. אם הוא שווה לאחד אז k=1 לא יכול להיות בור. נניח שבתא היה 0, אז התא הבא שתבדוק יהיה בשורה 1 עמודה 3 - שבעצם בודק את k=1,3 ופוסל אחד משניהם.

 

[tvi]

אתה מציע בעצם ללכת בשתי אלכסונים אחד מכל

צד של האלכסון הראשון ולבדוק את התנאים שלהם?

 

[Maha Vailo]

זה לא בהכרח אלכסון

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

 

[tvi]

שכחתי איזה משהו אם נגיד יש לי מערך [A[k

אז i זה מספר עמודה או שורה?..שכחתי כבר.

 

[Maha Vailo]

לפי החלטה שלך (או לפי מה שרשום בתרגיל)

 

[HaifaMan]

הרעיון הוא כמו למצוא את המכסימום בסדרה

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