שאלה ב JAVA דחוף !!!!

[Guy Yafe]

הפיתרון הזה לא נכון

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

 

[bla agin]

כמו שאמרתי לו זה 99% פתרון

זה יעבוד על כל N אי זוגי
וכן במקרה הזה התשובה תמיד תהיה 0 או חצי (INT) של N
n=5 תשובה יכולה להיות רק 0 או 2 או n=7 רק 0 או 3
אני מקווה שהוא יבין אך זה עובד ויוסף תיקון לכל N זוגי
"האם קיים מערך דו-ממדי ריבועי חלקי בפינה הימנית התחתונה של המערך"
אם הבנתי נכון רוצים לדעת אם הריבוע הפינתי שווה למטריצה יחידה
ממרכז (אמצע אלכסון ראשי) לפינה

 

[Guy Yafe]

לא 9 ולא 99

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

 

[bla agin]

תיקון לפתרון

יש מצב טוב שלא הבנתי נכון את התרגיל אז תיקון


public static int square2(int[][] mat,int n)
{
int count=0;
for(int i=n-1;i>=0;i--)
{
if(mat==1)
{
for(int j=1;j<=count;j++)
{
if(mat[i+j]!=0 || mat[i+j]!=0)
{
return count;
}
}
}
else
return count;

count++;
}
return count;
}

 

[bla agin]

999 חחח

 

[Netanel w]

עשו לך חיים קלים פה,

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

 

[nocgod]

פיתרון - נראה לי

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

package test;

public class Driver
{
public static int method(int[][] arr)
{
int count = 0;

// check if the last element of the main diagonal meets the minimal criteria
if (arr[arr.length -1][arr.length - 1] != 1)
{
return count;
}

// take steps back, counting the number of steps taken back that creates a sub-matrix
// that meets the criteria
for (int i = arr.length - 1; i >= 0; --i)
{
// if the first element of the sub-matrix doesn't equal one -> exit
if (arr != 1)
{
return count;
}
else
{
boolean bugFound = false;

for (int k = i; k < arr.length; k++)
{
for (int l = i ; l < arr.length; l++)
{
// try to fail the number the 2 criteria tests
if (k == l && arr[k][l] != 1)
{
// main diagonal criteria failed
bugFound = true;
}
else if (k != l && arr[k][l] != 0)
{
// surrounding null elements criteria failed
bugFound = true;
}

// if the number had failed the test - the current sub-matrix
// doesn't meet the criteria, thus the later matrices will not
// meet them as well - return what we've counted thus far.
if (bugFound)
{
return count;
}
}
}
// no test failed - this sub-matrix is OK, count it.
count++;
}
}
// we've successfully iterated over the whole matrix and it meets the criteria.
return count;
}

public static void main(String[] args)
{
int[][] badArray = {{1,0,2,0,0},{0,1,0,0,0},{2,3,4,5,6},{1,2,3,4,5},{0,1,0,2,5}};
int[][] goodArray = {{0,0,1,2,3},{0,0,2,0,3},{1,5,3,0,0},{0,1,2,1,0},{0,1,0,0,1}};
int[][] bestCase = {{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}};
int[][] bestCase2 = {{0,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}};

System.out.println("bad array: " + method(badArray));
System.out.println("good array: " + method(goodArray));
System.out.println("best array: " + method(bestCase));
System.out.println("best2 array: " + method(bestCase2));
}
}


כמו שאתה רואה הבדיקה שלי לא הייתה מי יודע מה רגורוזית - לדעתי זה אמור לעבוד, עבור מערכי הבדיקה שהזנתי זה עובד
וכמובן אם זה עובד נכון עבור מערך 5 על 5 סביר מאוד שזה עובד נכון גם עבור כל מערך ריבועי בגודל n על n

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

 

[nocgod]

מסתתר שם באג קטן...

הבאג נובע מזה שהספירה מתחילה מ - 0 אבל בתחלס צריכה לייצג גודל, כלומר ספירה שמתחילה ב 1

package test;

public class Driver
{
public static int method(int[][] arr)
{
int count = 0;

// check if the last element of the main diagonal meets the minimal criteria
if (arr[arr.length -1][arr.length - 1] != 1)
{
return 0;
}

// take steps back, counting the number of steps taken back that creates a sub-matrix
// that meets the criteria
for (int i = arr.length - 2; i >= 0; --i)
{
// if the first element of the sub-matrix doesn't equal one -> exit
if (arr != 1)
{
// if it is the second element from the end of the main diagonal
if (i == (arr.length - 2))
{
return count;
}
else
{
return count + 1;
}
}
else
{
boolean bugFound = false;

for (int k = i; k < arr.length; k++)
{
for (int l = i ; l < arr.length; l++)
{
// try to fail the number the 2 criteria tests
if (k == l && arr[k][l] != 1)
{
// main diagonal criteria failed
bugFound = true;
}
else if (k != l && arr[k][l] != 0)
{
// surrounding null elements criteria failed
bugFound = true;
}

// if the number had failed the test - the current sub-matrix
// doesn't meet the criteria, thus the later matrices will not
// meet them as well - return what we've counted thus far.
if (bugFound)
{
return count + (i == arr.length - 2 ? 0 : 1);
}
}
}
// no test failed - this sub-matrix is OK, count it.
count++;
}
}
// we've successfully iterated over the whole matrix and it meets the criteria.
return count + 1;
}

public static void main(String[] args)
{
int[][] badArray = {{1,0,2,0,0},{0,1,0,0,0},{2,3,4,5,6},{1,2,3,4,5},{0,1,0,2,5}};
int[][] goodArray = {{0,0,1,2,3},{0,0,2,0,3},{1,5,3,0,0},{0,1,2,1,0},{0,1,0,0,1}};
int[][] bestCase = {{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}};
int[][] bestCase2 = {{0,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}};
int[][] bugcheck = {{0,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,1,1}};
int[][] bugcheck2 = {{1,1,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,1,0,1}};

System.out.println("bad array: " + method(badArray) + " expected : 0");
System.out.println("good array: " + method(goodArray) + " expected : 2");
System.out.println("best array: " + method(bestCase) + " expected : 5");
System.out.println("best2 array: " + method(bestCase2) + " expected : 4");
System.out.println("bugcheck array: " + method(bugcheck) + " expected : 0");
System.out.println("bugcheck2 array: " + method(bugcheck2) + " expected : 2");
}
}

 

[nocgod]

ופיתרון יותר יעיל

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

package test;

public class Driver
{
public static int method(int[][] arr)
{
int count = 0;

// check if the last element of the main diagonal meets the minimal criteria
if (arr[arr.length -1][arr.length - 1] != 1)
{
return 0;
}

// take steps back, counting the number of steps taken back that creates a sub-matrix
// that meets the criteria
for (int i = arr.length - 2; i >= 0; --i)
{
// if the first element of the sub-matrix doesn't equal one -> exit
if (arr != 1)
{
// if it is the second element from the end of the main diagonal
if (i == (arr.length - 2))
{
return count;
}
else
{
return count + 1;
}
}
else
{
for (int k = i + 1; k < arr.length; k++)
{
if (arr[k] != 0 || arr[k] != 0)
{
return count + (i == arr.length - 2 ? 0 : 1);
}
}
// no test failed - this sub-matrix is OK, count it.
count++;
}
}
// we've successfully iterated over the whole matrix and it meets the criteria.
return count + 1;
}

public static void main(String[] args)
{
int[][] badArray = {{1,0,2,0,0},{0,1,0,0,0},{2,3,4,5,6},{1,2,3,4,5},{0,1,0,2,5}};
int[][] goodArray = {{0,0,1,2,3},{0,0,2,0,3},{1,5,3,0,0},{0,1,2,1,0},{0,1,0,0,1}};
int[][] bestCase = {{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}};
int[][] bestCase2 = {{0,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}};
int[][] bugcheck = {{0,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,1,1}};
int[][] bugcheck2 = {{1,1,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,1,0,1}};

System.out.println("bad array: " + method(badArray) + " expected : 0");
System.out.println("good array: " + method(goodArray) + " expected : 2");
System.out.println("best array: " + method(bestCase) + " expected : 5");
System.out.println("best2 array: " + method(bestCase2) + " expected : 4");
System.out.println("bugcheck array: " + method(bugcheck) + " expected : 0");
System.out.println("bugcheck2 array: " + method(bugcheck2) + " expected : 2");
}
}

 

[bla agin]

ציון 55

בלגןןןןןןןןן

j/k

 

[Guy Yafe]

סיבכת שלא לצורך.

אין סיבה לעשות sanity. גודל 0 הוא מקרה פרטי.

int square(int[][] matrix){
int returnSize = 0;
int matrixSize = matrix[0].length();
int diagonalIndex = matrixSize - 1; //Assuming the matrix is square ,and starting from the bottom
while(diagonalIndex >=0){
if(matrix[diagonalIndex][diagonalIndex] != 1){
//We need 1 on the diagonal
return returnSize;
}
for(int index = diagonalIndex + 1 ; index < matrixSize ; index++){
//Moving on the row and column of the current index: To the right and to the bottom.
//We need zeros off the diagonal
if(matrix[diagonalIndex][index] != 0 || //Checking the row
matrix[index][diagonalIndex] !=0){ //Checking the column
return returnSize;
}
}
returnSize++;
diagonalIndex--;
}
return returnSize;
}

 

[nocgod]

זה יצא קצת מסובך - אחרי הכל 1 בלילה

אבל בגרסא האחרונה יצא לי סבבה...בתחלס על אותו רעיון - רק שאני מתעלם מהמקרה של תת-מטריצה בגודל אחד על אחד ומחזיר 0 במקום...