תראד עזרה לקראת המבחן במבוא ג'אווה *עדכון* ע"מ 5 שאלה ברקורסיה !

[Yehudaa]

חברים יש לי שאלה ברקורסיה , ויש לי את הפתרון שלה

השאלה כזאת :

כתוב מתודה רקורסיבית שתקבל מערך דו מימדי int [][] a ותגיד , אם סכום כל שורה ושורה , אותו סכום

לדוגמא מערך

444

822

228

סכום כל שורה שווה ל 12 לכן יש להחזיר חיובי

הפתרון הוא כזה

/**
 * Test: 2005A-b
 * Question: 1
 * Note: Made it static so I can test it easier.
 */
public class Question1
{
  public static boolean what(int[][] a){
    int sum = sum( a[0], 0, 0 );
    return what(a, 1, sum );
  }

  private static boolean what(int[][] a, int rowInd, int sum)
  {
    if(rowInd == a.length)
      return true;

    if(sum != sum(a[rowInd], 0, 0))
      return false;

     return what(a, rowInd+1, sum);
  }

  private static int sum(int[] row, int index, int sum){
    if(index == row.length)
      return sum;

    sum += row[index];
    return sum(row, index+1, sum);
  }
}

לא הבנתי את הקוד הזה בכלל .

למישהו יש לו פתרון יותר ברור ?

תודה

[שניצל]

הפונקציה sum קצת מסורבלת. אפשר לפשט אותה ככה:

  private static int sum(int[] row, int index){
    if(index >= row.length || index < 0)
      return 0;

    return row[index] + sum(row, index+1);
  }

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

[Yehudaa]

הבנתי , אבל זה נראה לי קצת מסורבל

למישהו יש פתרון יותר אלגנטי ?

אני תמיד מתבלבל בין ROW ל COL

לדוגמא במערך כזה

int a[9][1]

מה ה ROW ומה ה COL ?

[exercise]

תחשוב על זה שאתה ניגש לשורה 9 עמודה 1.

[Yehudaa]

אז השורה זה ROW נכון ?

[exercise]

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

[שניצל]

קודם כל:

row = שורה, col = column = עמודה. (אלה מילים באנגלית...)

בד"כ האינדקס הראשון הוא מספר השורה, והשני הוא מספר העמודה.

ולגבי הפתרון - הפונקציה sum באמת מסורבלת, ונתתי מימוש קצת יותר פשוט בשבילה.

הפונקציה what דווקא בסדר גמור, ואני לא חושב שיש מה לשפר בה.

[Yehudaa]

שאלה נוספת ברשותכם :

נתון ה INTERFACE הבא :

public interface A

{

public int what (int [] data);

}

ונתון מחלקה B המממשת אותה

 public class B implements A
{

public int what(int[] data) 
{    
 int h1 = 0;
 int h2 = 1;

 for (int i = 0; i < data.length; i++) 
 {
    int v = data[i];
    int c = 1;

    for (int j = i+1; j < data.length; j++) 
    {
      if (data[j] == v) 
   	        c++;
    }

    if (c > h2) 
    {
      h2 = c;
      h1 = v;
    }
 }
 return h1;
}

}

הפתרון אומר :" השיטה מחזירה את המספר שמופיעה הכי הרבה פעמים במערך יותר מפעם אחת. אם קיים, תחזיר אותו, אם קיימים שתים או יותר, תחזיר את הראשון מבינהם, אם לא קיים, תחזיר 0. "

שאלה : כתבו מחלקה C הממשת את A ועושה את אותה העבודה של B בזמן ריצה של פחות מ N^2

ניתן להשתמש בquick sort , כלומר אין צורך לכתוב את הקוד של המיון המהיר , אבל ניתן להשתמש בו .

הפתרון הוא כזה :

 public class C implements A
{
	public int what (int [] data)
	{
		Sort.quicksort(data);
		int count = 1;
		int seq = 1;
		int num = 0;
		for(int i = 1; i < data.length; i++)
		{
			if(data[i] == data[i-1]){
				count++;
				if(count > seq){
					seq = count;
					num = data[i];
				}
			}
			else		
				count = 1;
		}
		return num;
	}
} 

שוב פעם לא הבנתי בשיט את הקוד הזה ,

מישהו יכול להסביר לי את האלגו' ? תודה .

[exercise]

זה בדיוק התשובה שרשמתי פה לפני כמה ימים....

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

[Yehudaa]

אוקי הבנתי

[Yehudaa]

שאלה ברקורסיה מאתגרת :

כתבו שיטה סטטית רקורסיבית cover שחתימתה היא:

public static boolean cover (int [] values, int amount)

המקבלת מערך int[] values מלא במספרים, ומספר שלם amount. השיטה תבדוק האם ישנו סכום מספרים כלשהו מהמערך values ששווה למספר amount.

אם קיים סכום כזה השיטה תחזיר true אחרת היא תחזיר false.

שימו לב שהשיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל.

רמז: ניתן להגדיר שיטה cover (int [] values, int i, int amount) אשר בודקת אם ניתן לכסות את הערך amount כסכום של חלק מאיברי המערך values החל באינדקס i.

לדוגמא, אם נתון המערך הבא: int[] values = {5, 22, 13, 5, 7, -4};

אם amount = 42, השיטה שתכתבו צריכה להחזיר true כי 22+13+7 = 42

אם amount = 31, השיטה שתכתבו צריכה להחזיר true כי 22+13+(-4)= 31

אם amount = -5, השיטה שתכתבו צריכה להחזיר false כי במערך לא קיימים מספרים שסכומם הוא -5

אם amount = 17, השיטה שתכתבו צריכה להחזיר true כי 5+5+7 = 17

אם amount = 13, השיטה שתכתבו צריכה להחזיר true כי 13 = 13

הפתרון :

 public class Question1
{
	public static boolean cover (int [] values, int amount){
		return cover(values, amount, 0);
	}

	private static boolean cover(int[] values, int amount, int index)
	{
		if(index == values.length)
			return false;

		if(amount - values[index] == 0)
			return true;

		if(amount - values[index] > 0
			&& cover(values, amount - values[index], index+1) )
				return true;

		if( cover(values, amount, index+1) )
			return true;
		else 
			return false;
	}
} 

עוד פעם לא הבנתי את הפתרון . מישהו יכול להסביר לי את האלגו' ?

תודה

[exercise]

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

אם הוא הגיע לסוף ולא החזיר TRUE עד עכשיו זה אומר שאין פתרון.

אם הסכום הנוכחי פחות התא הנוכחי הוא 0 אזי יש פתרון.

אם הסכום הנוכחי פחות התא הנוכחי גדול מ 0 ויש פתרון שכולל את התא הזה, תחזיר TRUE.

אם התא הזה לא משתתף בכיסוי, אז תנסה רקורסיבית להמשיך לבדוק את התאים הבאים (ותחזיר את מה שהם אמרו לפי התנאים הקודמים).

[Yehudaa]

כל הקוד הבנתי למעט הקטע הזה

 if(amount - values[index] > 0
			&& cover(values, amount - values[index], index+1) )
				return true; 

כלומר הבנתי את הפרוש , אבל לא הבנתי למה זה ככה .

[exercise]

זה אומר סה"כ שאם יש אופציה להכניס את התא הנוכחי לכיסוי (החלק הראשון של הif), אז תבדוק באמת שיש כיסוי שהוא מתאים לו (החלק השני של הif), ואם כן, אז תחזיר true (יש כיסוי שהוא חלק ממנו).

[Niseg]

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

התנאי הראשון ברור - אם הגעתי לסוף המערך אין פיתרון ל"ענף" של עץ הסכומים הקיים

התנאי השני בודק הצלחה של הענף כי אם מחסירים את הערך בindex הקיים מגיעים לסכום

התנאי השלישי בודק את האפשרות שהערך הקיים משתתף בסכום - הוא שואל "יש עוד מה להחסיר?" אם כן "האם אפשר לאפס את מה שנשער אחרי כשמחסירים את הערך בindex הנוכחי?" .

האחרון די ברור - האם אפשר ליצר את הסכום ללא הערך בindex.

לשאלת הדגל וריאציה של counting sort כפונקצית C אבל זה סיבוכיות 2N למרות שאני עובר על המערך רק פעם אחת:

void flagSort (char * ar, int length)
{
unsigned char colors[3]={'r','w','b'};
unsigned char trans[256];
unsigned long count[3]={0,0,0};
unsigned char * ar2
int i,j;
ar2= (unsigned char * )ar;
	for (i=0;i<3;++i)
	{
	trans[colors[i]]=i;
	}

for(i=0;i<length;++i)
{
count[trans[ar2]]++;
}
j=0;
for(i=0;i<3;++i)
{
	for(;count[i]>0;++j)
	{
		ar2[j]=colors[i];
		--count[i];
	}
}

}