שאלה במדעי המחשב - דחוף

[banan123]

שאלה במדעי המחשב - דחוף

נתון מערך דו-מימדי בגודל NXN. המערך מכיל מספרים. צריך למצוא את הסדרה הארוכה ביותר הקיימת במערך. הסדרה יכולה להיות במאונך, במאוזן או באלכסון.

 

[ron369]

תגדיר סדרה

 

[banan123]

סדרה = סדרה חשבונית עולה

 

[ron369]

זה כבר יותר טוב... ../images/Emo13.gif

נראה לי שמצאתי פתרון שעובד ב: (רמז) T = 4 T(n/2) + O (אני חושב) הבנת את הרמז?

 

[banan123]

אשמח אם תפרט יותר,

 

[ron369]

עדיף שתנסה לבד

בכל אופן, תחשוב איך אפשר לחלק את הבעיה הגדולה, לכמה בעיות קטנות יותר. בפרט, תחשוב איך אפשר לקחת בעיה של מטריצה בגודל NXN, ולחלק אותה לארבע מטריצות בגודל חצי אן X חצי אן. (כלומר, השטח הוא רבע מהשטח הקודם) כך מתקבל אלגוריתם שזולל זכרון, אבל הוא יוצא מאר מהיר, אסימפטוטית. עכשיו, שים לב שבשביל שזה יצא מהיר, אתה חייב לשמור על כל מטריצה לא O(NXN) מידע, אלא פחות, למשל O(N). וכך, בעזרת 4 פעמים O(N) המידע על כל אחת מתת-המטריצות (יש 4), תקבל את המידע של המטריצה הגדולה יותר. אל תפחד להסתבך. הפתרון שיצא לי קצת מסובך ומגעיל, אבל אני די בטוח שאין טוב ממנו (כי הוא ב-O(N^2) כקודל הקלט). אולי רק יש פתרון עם פחות זיכרון, או משהו דומה.

 

[banan123]

תודה, אבל עדיין אין לי פתרון

 

[vinney]

מה הדבר הכי טריויאלי שאתה יכול

לחשוב עליו?

 

[copaste]

לדעתי יותר פשוט

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

 

[ron369]

צריך יותר מידע מכך, צריך מידע על

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