שימוש ברקוריסה בג'ווה למציאת כל האפשרויות במערך

[Dimka]

לולאה 1-I =N עד 1

{אם [ בדוק (מערך' date= I, מכפלה חלקי מערך N ] ) ] אמת החזר אמת}

החזר שקר

סוף פונקציה------

לא בדיוק הבנתי מה עשית שם... אתה יכול להראות את זה? (גם C אבין...)

אגב, איך עושים את זה בלי לולאות כלל (זו הייתה אחת הדרישות במבחן)

[שניצל]

Dimka, נתתי לך כבר מקום להתחיל ממנו את הפתרון (בלי לולאות).

[Dimka]

Dimka, נתתי לך כבר מקום להתחיל ממנו את הפתרון (בלי לולאות).

אני יודע איך משתמשים ברקוריסה בצורה הבסיסית.

השאלה איך אני מצליח להגיע למצבים האלה:

2,3,4,5,6

כאשר אני רוצה למצוא מכפלה רק של האדומים.

עריכה:

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

משהו שאני יודע לעשות:

1,2,3,4,5,6

משהו שאני לא יודע לעשות:

1,2,3,4,5,6

[שניצל]

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

אני אחזור על עצמי:

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

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

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

[Dimka]

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

נראה אם אני בכיוון:

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

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

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

(או שסתם לא הבנתי אותך נכון...)

[שניצל]

עזוב את הרעיון של השורש. מה גם שבשביל לחשב אותו אתה צריך לולאה (או רקורסיה מיותרת).

[Dimka]

עזוב את הרעיון של השורש. מה גם שבשביל לחשב אותו אתה צריך לולאה (או רקורסיה מיותרת).

אוקיי נזרום איתך

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

1. האם הערך שייך לקבוצה או לא שייך לקבוצה.

2. האם יש מערך/מרחק מהאינדקס באורך 1 (ולכן זה שקר? או אמת?).

3. אם יש מערך באורך 2, אז אם שני הערכים זהים, אמת, אחרת שקר.

[שניצל]

אני אחזור שוב על מה שאמרתי קודם:

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

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

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

[Ghosthunter]

מה הכוונה "האיברים הנגדיים של Y"?

[שניצל]

נו, האיברים בקבוצה המשלימה. די להיות קטנוני

[amitbl]

bool mult(int arr[], int arrSize)
{
//initialize variables
	int firstGroupMult = 1;
	int secondGroupMult = 1;
	int arrIndex = 0;

	return mult(arr, arrSize, arrIndex, firstGroupMult, secondGroupMult);
}

bool mult(int arr[], int arrSize, int arrIndex, int firstGroupMult, int secondGroupMult)
{
	//halting condition we checked all array members
	if (arrIndex==arrSize) 
	{
		if (firstGroupMult==secondGroupMult) return true;
		else retrun false;
	}

	//general situation - multiply current array integer and advance
	else
		return 	mult(arr, arrSize, arrIndex++, firstGroupMult*arr[arrIndex], secondGroupMult) ||
			mult(arr, arrSize, arrIndex++, firstGroupMult, secondGroupMult*arr[arrIndex]);

}

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

לכן הקוד הזה נראה לי צריך להיות די ברור. אני לא זוכר את הסינטקס המלא של ג'אווה, אז כתבתי במעין פסאודו קוד פרוצדורלי. לדעתי בג'אווה יש למערך יש את הפרופרטי size או length או משהו כזה ואז אין צורך להעביר את הפרמטר arrSize, ומשתנה בולאיני מוגדר ממש boolean.

לא קימפלתי בשום שפה אבל זה נראה לי צריך לעבוד. יצא לי הרבה יותר קצר ממה שחשבתי שייצא, וזה היה תאכלס די פשוט.[br]פורסם בתאריך: 23.07.2010 בשעה 16:32:54

---

התרגיל עניין אותי.

אז מצורפים 2 פתרונות

נ.ב:

כתבתי ב-C#. אבל היא מאוד קרובה ל-JAVA כך שמאוד קל לתרגם.

כמובן שאם משהוא לא ברור שאל....

אחי עברתי על הקוד שלך.... תהיה לי בריא אתה התפזרת לאללה.

[שניצל]

יש לך באג קטן - צריך להיות arrIndex+1 ולא ++arrIndex.

חוץ מזה זה בדיוק המימוש שכיוונתי אליו (למרות שניסיתי לגרום לפותח הת'רד להגיע אליו בעצמו...)

[Dimka]

תודה amitbl,

ראיתי את המימוש והבנתי, מאוד אלגנטי.... (יעבוד אחרי תיקונים קטנים לפקודות)

הייתי בכיוון רק שעשיתי את זה בשלבים (ולא סיימתי נכון לעכשיו, עבודה וזה...).

אנסה לממש את זה בדרך שלי ואשתמש במה שעשית כ-reference אם אתקע

תודה!!!

[amitbl]

יש לך באג קטן - צריך להיות arrIndex+1 ולא ++arrIndex.

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

[שניצל]

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