שאלה בC

[D a Z y]

שאלה בC

אני שובר את הראש כבר שבועיים על התוכניות (היא אמורה להיות פשוטה) ולא מצליח....

יש לי מטריצה 5X5 שמוזנת ע"י משתמש עם ערכים הנעים בין 99 למינוס 99.
איך אני יכול למצוא את תת המטריצה בעלת הסכום הגבוה ביותר??
אפשר להשתמש רק בלולאות ולא בפונקציות...

אשמח לכל עזרה... אפילו אם זה רק כיוון מחשבה...
תודה מראש!

 

[gonzila]

מצורף פתרון ב-java

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

לא כותב ב-C אז תאלץ להסתדר עם זה
את שאר ההערות כתבתי לך בקוד.

 

[Netanel w]

2 דברים:

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

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

 

[D a Z y]

תודה!

 

[D a Z y]

הבעיה היא במעבר על כל התת מטריצות

אני יודע שניתן ליישם זאת ב-4 FOR או אולי 6... רק איך אני עדיין לא קלטתי...

 

[gonzila]

ככה

דבר ראשון נתנאל צודק לא הבנתי טוב את השאלה בהתחלה, וכן יש דרכים לבצע הרבה יותר יעיל.
אפשר לבצע עם מערך עזר ששומר סכום של כל שורה ואז לבצע הצלבות ולראות איך מתקבל הסכום הכי גדול.
ויש אלגוריתמים יותר יעילים כמו Summed area table:
[Summed area table]

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

 

[D a Z y]

תודה רבה!

הצלת אותי!
שיהיה המשך שבוע מעולה... ושוב תודה : )