רוטר - |JAVA| ושוב פעם, תרגיל backtracking,

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"|JAVA| ושוב פעם, תרגיל backtracking,"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #10679	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10679

dvir8
חבר מתאריך 13.5.02
5929 הודעות, דרג אמינות חבר זה

00:09 01.05.12

|JAVA| ושוב פעם, תרגיל backtracking,

השאלה:

Given an array of ints, is it possible to choose a group of
some of the ints, beginning at the start index, such that the group
sums to the given target? However, with the additional constraint that
all 6's must be chosen. (No loops needed.)
groupSum6(0, {5, 6, 2}, 8) → true
groupSum6(0, {5, 6, 2}, 9) → false
groupSum6(0, {5, 6, 2}, 7) → false
קישור לקומפיילר אונליין יחד עם השאלה:
http://codingbat.com/prob/p199368

ניתן לפתור ללא העמסה? מה אתם אומרים?

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אם הבנתי נכון זה פשוט רקורסית subset עם סכימה של ה6-שיות	Yariv-H	01.05.12 11:28	1
כן אבל אתה חייב להתיחס לכל ה 6.	dvir8	01.05.12 13:42	2
לכן אמרתי עם שינוי קל .	Yariv-H	01.05.12 19:07	5
תקרא את השאלה באתר	dyermaker	01.05.12 19:34	6
לא הייתה שום כוונה ללולאות , הכול ברקורסיות.	Yariv-H	02.05.12 08:48	11
הנה הפתרון	dyermaker	01.05.12 15:06	3
עוד לא קראתי כדי לא לקטוע את החשיבה,	dvir8	01.05.12 15:30	4
כל הכבוד אחי! נעזרתי בך באחת השורות,	dvir8	01.05.12 21:10	8
פתרון קצת יותר נקי וברור (בעיניי)...	ldan192	01.05.12 20:49	7
יפה עידן! שאלה לי,	dvir8	01.05.12 21:13	9
למה שהשורה הזו תהיה נכונה תמיד? לא כל-כך ברורה לי האינטואיציה מאחוריה	ldan192	01.05.12 23:06	10
היא בעצם שואלת,	dvir8	02.05.12 13:24	12
אה צודק, לא הסתכלתי על הקוד שכתבת למעלה בהקשר שלו	ldan192	03.05.12 13:52	13
הבנתי, בכל מקרה חזרתי ממבחן עכשיו (מועד ב'),	dvir8	03.05.12 20:06	14

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

11:28 01.05.12

1. אם הבנתי נכון זה פשוט רקורסית subset עם סכימה של ה6-שיות
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dvir8
חבר מתאריך 13.5.02
5929 הודעות, דרג אמינות חבר זה

13:42 01.05.12

2. כן אבל אתה חייב להתיחס לכל ה 6.
בתגובה להודעה מספר 1

כלומר, אם יש לך מערך:
4,2,6,6 אתה חייב להשתמש בכל ה 6.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

19:07 01.05.12

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

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

אם הם קיימות בסכום , אתה מפרסם אותו.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dyermaker
חבר מתאריך 4.2.03
1644 הודעות, דרג אמינות חבר זה

19:34 01.05.12

6. תקרא את השאלה באתר
בתגובה להודעה מספר 5

רשום לא להשתמש בלולאות

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

08:48 02.05.12

11. לא הייתה שום כוונה ללולאות , הכול ברקורסיות.
בתגובה להודעה מספר 6

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dyermaker
חבר מתאריך 4.2.03
1644 הודעות, דרג אמינות חבר זה

15:06 01.05.12

3. הנה הפתרון
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 01.05.12 בשעה 15:25 בברכה, dyermaker

לקח לי 3 עריכות אבל לבסוף פתרתי אותו
אתה יכול אולי להציג גירסה יותר אלגנטית

public boolean groupSum6(int start, int[] nums, int target) {
if (start==nums.length && target==0) return true;
if (start==nums.length && target!=0) return false;
if (target==0 && nums[start]==6) return false;
if (target==0 && nums[start]!=6) return
groupSum6(start+1,nums,target);

if (nums[start]==6)
return (groupSum6(start+1,nums,target-6));
else
return
groupSum6(start+1,nums,target-nums[start]) ||
groupSum6(start+1,nums,target);

}

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dvir8
חבר מתאריך 13.5.02
5929 הודעות, דרג אמינות חבר זה

15:30 01.05.12

4. עוד לא קראתי כדי לא לקטוע את החשיבה,
בתגובה להודעה מספר 3

אני אסתכל בערב אחרי שאחזור מהעבודה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dvir8
חבר מתאריך 13.5.02
5929 הודעות, דרג אמינות חבר זה

21:10 01.05.12

8. כל הכבוד אחי! נעזרתי בך באחת השורות,
בתגובה להודעה מספר 3

הקוד שלי הוא כזה:

public boolean groupSum6(int start, int nums, int target) {
if(nums.length == start) return target==0;
if(target==0 && nums==6) return false;
if(nums==6)
return groupSum6(start+1,nums,target-nums);
return groupSum6(start+1,nums,target-nums) ||
groupSum6(start+1,nums,target);
}

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

20:49 01.05.12

7. פתרון קצת יותר נקי וברור (בעיניי)...
בתגובה להודעה מספר 0

public boolean groupSum6(int start, int[] nums, int target) {
if (target == 0 && nums.length == start) return true;
if (target < 0 || start >= nums.length) return false;
if (nums[start] == 6) return groupSum6(start + 1, nums, target - 6);
return (groupSum6(start + 1, nums, target - nums[start]) || groupSum6(start + 1, nums, target));
}

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dvir8
חבר מתאריך 13.5.02
5929 הודעות, דרג אמינות חבר זה

21:13 01.05.12

9. יפה עידן! שאלה לי,
בתגובה להודעה מספר 7

איך זה שנמנעת מלשאול:

if(target==0 && nums[start]==6) return false;

לא הצלחתי בקוד שלך למצוא משהו שמכסה את זה, והוא בכל זאת עובד!

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

23:06 01.05.12

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

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dvir8
חבר מתאריך 13.5.02
5929 הודעות, דרג אמינות חבר זה

13:24 02.05.12

12. היא בעצם שואלת,
בתגובה להודעה מספר 10

האם הגעת למטרה מבלי להשתמש באיבר הנוכחי שהוא כרגע 6? ולכן זה לא טוב כי צריך לנצל את כל ה 6 שיש לנו

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

13:52 03.05.12

13. אה צודק, לא הסתכלתי על הקוד שכתבת למעלה בהקשר שלו
בתגובה להודעה מספר 12

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

אבל בסה"כ הבדיקה הזו מיותרת, כי אם אכפה את הוספת ה-6, בצומת הבא בעץ התנאי שלי גם ככה מתקיים (כי 0-6 = 6-).
עבור מערכים קצרים - הגיזום שלך משתלם,
אבל עבור קלטים מאוד ארוכה, הבדיקה הזו הרבה יותר יקרה מאשר להכנס חד פעמית לעוד היררכיה בעץ.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dvir8
חבר מתאריך 13.5.02
5929 הודעות, דרג אמינות חבר זה

20:06 03.05.12

14. הבנתי, בכל מקרה חזרתי ממבחן עכשיו (מועד ב'),
בתגובה להודעה מספר 13

היה לי די קשה. ז"א 5 שאלות היו סבבה לגמרי.
השאלות המאסיביות של 25 נק' כל אחת היו לי ממש קשות.
הראשונה היתה backtracking שעשיתי שם איזה משהו מוזר שאני מקווה שאני אקבל על זה ניקוד.
ובשאלה ה 2 פתרתי ביעילות לא הכי טובה, מניסיון יתחכו לי יותר מ 50% מהניקוד.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד