שלום,

יש לי תרגיל בית שקיבלתי באוניברסיטה ואני לא בדיוק מצליח להתמודד איתו...

כתבו תכנית מגדירה:

const unsigned int MAX = 20 ;

int matrix[MAX][MAX] ;

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

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

א. מספר השורה (שהנה גם מספר העמודה) של הפינה השמאלית העליונה של תת-המערך.

ב. גודלו של תת-המערך, כלומר כמה תאים נכללים בתת-המערך.

לדוגמה:

4# 3# 2# 1# 0#

16 16 16 2 1 0#

49 1 7 3 1 1#

19 4 8 2 4 2#

3879 5 9 6 5 3#

39 3879 17 5 16 4#

בתת-מערך הנ"ל (של המערך הדו-מימדי בגודל MAX על MAX):

א. התא 0 0 אינו עונה על הדרישות כי כבר מערך בגודל 2X2 יכיל את הערך 1 פעמיים (קל וחומר קטע מערך גדול יותר).

ב. התא 1 1 מהווה פינה שמאלית עליונה של תת-מערך בגודל 2X2 וכן של תת-מערך בגודל 3X3 העונים על הדרישות (כל ערך מופיע בהם פעם יחידה). קטע המערך בגודל 4X4 שפינתו השמאלית העליונה היא התא 1 1 כבר אינו עונה על הדרישות (שכן הערך 5 מופיע בו מספר פעמים).

ג. התא 2 2 מהווה פינה שמאלית עליונה של קטע מערך בגודל 2X2 העונה על הדרישות.

ד. התא 3 3 אינו עונה על הדרישות.

לכן פלט התכנית יהיה:

4 1

9 1

4 2

שימו לב:

א. סדר הופעת הריבועים בפלט הוא לפי המתואר בדוגמה מעל.

ב. בבדיקות אסור לחרוג מגבולות תת-המערך (כל הערכים חייבים להיות שייכים לתת המערך).

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

למישהו יש רעיון לקוד שיכול קצת לעזור לפתור התרגיל המפציץ הזה?

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

התרגיל סתם נראה הרבה יותר מסובך ממה שהוא באמת.

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

אח"כ, תכתוב סביבו קוד של לולאות שיעבור על כל התת-מערכים הקיימים.

קפיש?

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

לגבי התרגיל, תודה על ההכוונה שלך עכשיו הבנתי מה רוצים ממני בגדול..

הבעיה הגדולה שלי זה איך אני בודק אם מספר מופיע יותר מפעם אחת בתת מערך... מה עוד שמה קורה אם המשתמש בוחר לבדוק מערך של 20X20, עם 400

מספרים שונים.... איך אז אפשר לעשות את כל הבדיקות האלו?

מה זאת אומרת איך אפשר לעשות את כל הבדיקות האלו? באמצעות לולאות. הרי זה מחשב. הוא יכול לעשות דברים מהר מאוד.

הדרך הכי פשוטה לבדוק אם איבר מופיע פעמיים בתת-מערך, היא פשוט לעבור על כל התת-מערך, ועבור כל איבר שיש בו לעבור על כל התת-מערך שוב, ולמצוא אם קיים איבר ששווה לו.

הנה דוגמה עבור מערך חד מימדי - נניח שיש לך מערך בגודל 10:

int arr[10];

ואתה רוצה לבדוק אם יש איבר שמופיע בו פעמיים. הדרך הכי פשוטה היא ככה:

bool result = false;
for (int i = 0 ; i < 10 ; i++) {
 for (int j = 0 ; j < 10 ; j++) {
  if (arr[i] == arr[j] && i != j) {
   result = true;
  }
 }
}

עכשיו תחשוב איך להרחיב את הדוגמה הזו למערך דו מימדי.

תודה רבה לך, אני אלך לשבת על זה ונראה אם אצליח לכתוב קוד שיעבוד...

המון תודה!!

כדאי גם לעשות break כדי להפסיק לבדוק כפילויות אם נמצאה אחת כבר..

כמובן, כמובן. לא רציתי לסבך.

(רק שאי אפשר להשתמש ב-break, כיוון ש-break ייצא רק מהלולאה הפנימית ביותר, וצריך לצאת מ-2 לולאות. צריך לעשות את זה באמצעות משתנה נוסף שיהווה תנאי ל-for)

או עם GOTO מחוץ לשתי הלולאות (או שאתה אומר שהרווח ביעילות וכו' לא שווה את זה?).

איכס, GOTO.

נגיד את זה ככה - קיימים מעט מאוד מקרים שבהם אתה תרצה לכער את הקוד עם GOTO על מנת לייעל אותו כל כך קצת.

אני סתם אובססיבי בקשר ליעילות לפעמים..

חבל שאין ב-C משהו כמו break all או break N.

יש את setjmp ו setcontext ב posix שיכולים לקפוץ חזרה למקום מסוים.

זה לגמרי overkill. במקרה המדובר עדיף goto. בהנחה שאתה מטורף ביצועים כ"כ.

אפילו לא ברור ש-goto ישפר את הביצועים...

לגבי הקוד ששניצל כתב,

אני חושב שעדיף במקום על כל המערך עבור כל איבר, עדיף לעבור מהאיבר הנבדק עד הסוף.

מכיוון שבדקנו כבר את האיברים הקודמים לו במערך ואם הם לא הופיעו פעמיים, אין טעם לבדוק אותם שוב.

תקנו אותי אם אני טועה..

bool result = false;
for (int i = 0 ; i < 10 ; i++) {
 for (int j = i+1 ; j < 10 ; j++) {
  if (arr[i] == arr[j]) {
   result = true;
  }
 }
}

צודק, אבל הסיבה שכתבתי את הקוד שכתבתי היא כי:

א. הוא יותר פשוט.

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