רקורסיה על מערך דו מימדי ג'אווה .

[Yehudaa]

בלוח דו-ממדי בגודל m * n, אשר כל אחת ממשבצותיו יכולה להיות ריקה או מלאה, נקרא כתם לרצף משבצות מלאות בעלות צלע משותפת או קדקוד משותף.

גודל הכתם הוא מספר המשבצות המרכיבות את הכתם.

ייתכנו מספר כתמים בלוח.

דוגמה:

נסמן משבצת מלאה באמצעות התו  ומשבצת ריקה באמצעות תו רווח.

הלוח צורף בקובץ למטה

מכיל 3 כתמים:

כתם המורכב ממשבצות (1, 0), (0, 1) וגודלו 2.

כתם המורכב ממשבצות (3, 2), (2, 2), (4, 1), (3, 1), (4, 0) וגודלו 5.

כתם המורכב ממשבצות (2, 4), (1, 4), (0, 4), (0, 3) וגודלו 4.

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

חתימת השיטה תהיה:

public static int stain (char [][] mat, int row, int col)

לדוגמה: עבור המערך מהדוגמה הקודמת וזוג המספרים (3, 1) יוחזר 5, ועבור זוג המספרים (4, 4) יוחזר אפס.

עד כאן

???

[attachment deleted by admin]

[שניצל]

בעקרון אתה צריך שהפונקציה תעשה ככה:

אם המשבצת עצמה ריקה, להחזיר 0.

אם המשבצת עצמה מלאה, להריץ את הפונקציה על כל המשבצות שסובבות אותה, ולהחזיר את סכום התוצאות + 1.

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

[Yehudaa]

איך מריץ על הסובבים ? פעם זה למטה , פעם זה למעלה , פעם זה בצדדים ......

כלומר איך אני קורא רקורסיבית ל STAIN מה אני אעביר ל ROW ול COL ?

[שניצל]

אתה צריך לקרוא ל-stain עבור כל התאים שמסביב לתא:

row-1,col-1

row,col-1

row+1,col-1

row-1,col

וכן הלאה.

כמובן דאג ש-row ו-col לא יהיו פחות מ-0 או n ומעלה.

[Yehudaa]

ואחרי שעשיתי סיבוב אחד של 360 מעלות , איך אני עושה עוד סיבוב ברדיוס יותר גדול ?

[שניצל]

בשביל זה הרקורסיה.

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

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

[Yehudaa]

אני חושב שהבנתי אותך ,

הבעיה עכשיו איך אני מסמן תא שנקרא ...

[Component]

צור עוד מערך דו מימדי של בוליאנים.

[Jaman]

אם כל תא הוא הוא int (אפס לריק ו 1 למלא) אתה יכול לשים 2 איפה שביקרת ובדרך חזרה להחזיר את הערך שהיה. אם אתה רוצה להבדיל בין מלא וריק תשתמש ב 2 ו-3 בהתאם...

אם כל תא יכול ליהיות רק true או false אז אתה חייב מערך עזר (אלא אם יש שיטה מתוחכמת בלי אחד).

[Yehudaa]

אני מנסה להגדיר מערך בוליאני

 public static int stain (char[][] mat , int row , int col )
 {
  int m= mat.length;
   int n=mat[].length;
   boolean[][] test = new boolean[m][n] ;
  return 1;
}
} 

מה לא בסדר בזה ?

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

עריכה: כנראה לא הבנתם את השאלה .

השאלה שלי היא כזאת , אני רוצה לצור מערך בוליאני באורך n וברוחב m

האם זה חוקי לרשום ככה ?

int m= mat.length;

int n=mat[].length

כי אני מקבל על זה שגיאה משום מה

[שניצל]

אין משמעות לביטוי []mat.

אתה צריך לעשות את זה דרך אחת השורות ב-mat, כלומר mat[0].length.

[Yehudaa]

להתעלם סליחה...

[Yehudaa]

עדכון :

 public class Ex16_3
{
static int x=0; 
 public static int stain (char[][] mat , int row , int col )
 {

  if (row <0)
  return 0;
  else if(col<0)
  return 0;
  else if (mat[row%(mat.length-1)][col%(mat[0].length-1)]==' ')
  return 0 ;
  else
  {

   mat[row][col]=' ';
   x++;

  }
   stain(mat , row-1,col-1);
   stain(mat , row-1,col);
   stain(mat , row-1,col+1);
   stain(mat , row,col+1);
   stain(mat , row,col-1);
   stain(mat , row+1,col-1);
   stain(mat , row+1,col);
   stain(mat , row+1,col+1); 
 return x+1;  
}
} 
 [code] public class test
{
public static void main(String[] args)
{
char[][] b={
{'x','x','x' ,' ' ,' ' ,' ' },
{'x','x','x' ,' ' ,' ' ,' ' },
{'x','x','x' ,' ' ,' ' ,' ' },
{'x','x','x' ,' ' ,' ' ,' ' },
{'x','x','x' ,' ' ,' ' ,' ' },
{'x','x','x' ,' ' ,' ' ,' ' },


};


Ex16_3 a= new Ex16_3();
System.out.println(a.stain(b,3,0));
}
}

שתי בעיות :

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

2. יש שגיאת ביצוע , לדוגמא במערך הנ"ל הכתם הוא 18 , והפונקציה אומרת 16 מה לא בסדר ?

תודה .

[שניצל]

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

אין סיבה גם לשים את הבדיקה הזו ב-if-ים שונים - תעשה if אחד ארוך:

if (row < 0 || row >= mat.length || col < 0 || col >= mat[0].length)

(השגיאה שבגללה יצא 16 היא בגלל חישוב לא נכון של המודולו)

תעיף את x. במקום זה, תדאג שהפונקציה את סכום התוצאות של כל ה-stain שהיא מריצה + 1, כלומר:

return 1 + stain(mat , row-1,col-1) + stain(mat , row-1,col) + // and so on

שים לב שכמו שהתכנית עכשיו, אם תריץ את הפונקציה פעמיים ברצף אז x לא מאופס בין שתי ההרצות.

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

[Yehudaa]

 public class Ex16_3
{

 public static int stain (char[][] mat , int row , int col )
 {

  if (row < 0 || row >= mat.length || col < 0 || col >= mat[0].length)
  return 0;
  else
  {

   mat[row][col]=' ';
   return 1+
  stain(mat , row-1,col-1)+
   stain(mat , row-1,col)+
   stain(mat , row-1,col+1)+
   stain(mat , row,col+1)+
   stain(mat , row,col-1)+
   stain(mat , row+1,col-1)+
   stain(mat , row+1,col)+
   stain(mat , row+1,col+1) ;

}
} 
} 

יש שגיאת ביצוע

stack over flow

מה הבעיה ?

עריכה : נפתר התרגיל בהצלחה !!!

תודה שניצל !!

עריכה 2 :

פתרתי את התרגיל אבל על ידי שינוי המערך הנתון ,

איך אני מממש מערך בוליאני שימצא בתוך הפונקציה הרקורסיבית ?

הרי בכל קריאה רקורסיבית יווצר מערך חדש ....

אני רוצה מערך סטטי שיתעדכן בזמן אמת .

אבל אסור להצהיר על משתנה סטטי בתוך הפונקציה מה אני עושה ?