| כותב |
|
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 31 December 2007 בשעה 18:20 | | IP רשוּם
|
|
|
|
נתון תרמיל גב המסוגל לעמוד בעומס של num ק"ג, ונתונים X חפצים אותם רוצים לקחת לטיול. עבור כל אחד מהחפצים נתון משקלו. צריך לבדוק האם קיים צירוף כלשהו של חפצים המאפשר לנצל במלואו את העומס המותר לתרמיל.
כתבו שיטה רקורסיבית בוליאנית המקבלת כפרמטרים את העומס המותר של התרמיל - num ומערך שיכיל את משקלות החפצים. השיטה תחזיר ערך true אם ניתן לאסוף חפצים במשקל זהה לעומס המותר לתרמיל ו- false אם לא. כמו כן, השיטה תדפיס גם את משקלות החפצים המקיימים את התנאי (אם יש כאלה). אם יש יותר מצירוף אחד - יודפס אחד מהם.
חתימת השיטה -
public static boolean isFillBag (int[] arr, int num)
אינכם רשאים לשנות את חתימת השיטה, אבל אתם יכולים להיעזר בשיטה נוספת פרטית שעושה overload לשיטה זו.
אתם יכולים להניח שהמערך מלא במספרים שלמים חיוביים בלבד.
דוגמאות:
1. עבור M = 10 ורשימת החפצים 14 20 3 10 1
יוחזר true והשיטה תדפיס 10
2. עבור M = 20 ורשימת החפצים 9 3 12 7 15 1 4
יוחזר true והשיטה תדפיס (למשל) 12 7 1
3. עבור M = 12 ורשימת החפצים 11 3 5 18
יוחזר false.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות בכלל!
|
| חזרה לתחילת העמוד |
|
| |
Dark Phoenix
משתמש פעיל
הצטרף / הצטרפה: 22 December 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 50
|
| נשלח בתאריך: 31 December 2007 בשעה 22:21 | | IP רשוּם
|
|
|
|
בעקרון הרעיון הוא שתנאי העצירה של הרקורסיה הוא כשהמטען גדול או שווה למקסימום. במקרה הזה צריך להחזיר true/false בהתאם. אם עוד לא הגענו למצב הזה, צריך לקרוא לפונקציה פעם כשאתה כן שם את החפץ ה-iי, ופעם לא (לא לשים את החפץ, פשוט לעבור להבא). אתה תצטרך להשתמש בפונקצית עזר עם arr,num,i, כש-i מאותחל ל-M ומצביע על האיבר ה-i ברשימה.
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 01 January 2008 בשעה 17:43 | | IP רשוּם
|
|
|
|
Dark Phoenix כתב:
| בעקרון הרעיון הוא שתנאי העצירה של הרקורסיה הוא כשהמטען גדול או שווה למקסימום. במקרה הזה צריך להחזיר true/false בהתאם. אם עוד לא הגענו למצב הזה, צריך לקרוא לפונקציה פעם כשאתה כן שם את החפץ ה-iי, ופעם לא (לא לשים את החפץ, פשוט לעבור להבא). אתה תצטרך להשתמש בפונקצית עזר עם arr,num,i, כש-i מאותחל ל-M ומצביע על האיבר ה-i ברשימה. |
|
|
אם הבנתי נכון משהו כזה?
קוד:
public static boolean isFillBag (int[] arr, int num)
{
int sum;
if (sum == num)
{
return true;
System.out.println("+sum+");
}
else
tooverload(arr,num,i);
}
private int tooverload(int[] arr, int num, int i)
{
i=num;
arr[num]=num; |
|
|
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 04 January 2008 בשעה 21:09 | | IP רשוּם
|
|
|
|
לא הצלחתי:(
אפשר עזרה בבקשה
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 04 January 2008 בשעה 21:41 | | IP רשוּם
|
|
|
|
פתרון פשוט ולא יעיל בלי כל מיני בדיקות:
קוד:
bool func(arr, sum)
{
return inner(arr, 0, 0, sum);
}
bool inner(arr, index, sum, total)
{
if (index == arr.length)
return (sum == total);
if (inner(arr, index+1, sum+arr[index], total))
return true;
if (inner(arr, index+1, sum, total))
return true;
return false;
} |
|
|
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 04 January 2008 בשעה 22:04 | | IP רשוּם
|
|
|
|
shoshan כתב:
פתרון פשוט ולא יעיל בלי כל מיני בדיקות:
קוד:
bool func(arr, sum)
{
return inner(arr, 0, 0, sum);
}
bool inner(arr, index, sum, total)
{
if (index == arr.length)
return (sum == total);
if (inner(arr, index+1, sum+arr[index], total))
return true;
if (inner(arr, index+1, sum, total))
return true;
return false;
} |
|
|
|
|
|
תודה ,אני ניסיתי להבין שוב
ועשיתי זאת כתוכנית שלמה בלי רקורסיה ועם לולאות וזה עובד אבל השאלה
איך אני יכול לעשות זאת ללא לולאות ועם רקורסיה
הנה
קוד:
public static void main(String[] args) {
int[] x = { 11, 8, 7, 6, 5 }; // descendingly sorted inputs
int target = 20; // our target
boolean[] y = null; // y will be true if x is selected
boolean foundAnswer = false;
int sum = 0;
abc: for (int i = 0; i < x.length; i++) {
y = new boolean[x.length]; // all y(s) will be set default to 'false'
sum = x;
y = true; // x is selected
for (int j = i + 1; j < x.length; j++) {
if (sum + x[j] <= target) {
sum += x[j];
y[j] = true;
}
if (sum == target) {
foundAnswer = true; // now we found the answer.
break abc; // break out from outer most for loop
}
}
}
if (foundAnswer) {
System.out.println("Found Answer");
for (int i = 0; i < x.length; i++) {
if (y) {
System.out.println(x);
}
}
} else {
System.out.println("No Answer Found!!");
}
}
} |
|
|
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 04 January 2008 בשעה 22:26 | | IP רשוּם
|
|
|
|
הממ...בפתרון שלי זה בלי לולאות ועם רקורסיה, רק שכחתי להוסיף שמה את ההדפסה לפני שמחזירים true, אתה מוזמן להוסיף...
כל הקטע שבלי רקורסיה (או מבני נתונים) אתה לא יכול להציע פתרון שיבדוק את כל האפשרויות.
אגב, פתרון יעיל נדמה לי שיש באתר של אולימפיאדת מדעי המחשב, אני לא בטוח...
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 04 January 2008 בשעה 22:45 | | IP רשוּם
|
|
|
|
shoshan כתב:
הממ...בפתרון שלי זה בלי לולאות ועם רקורסיה, רק שכחתי להוסיף שמה את ההדפסה לפני שמחזירים true, אתה מוזמן להוסיף...
כל הקטע שבלי רקורסיה (או מבני נתונים) אתה לא יכול להציע פתרון שיבדוק את כל האפשרויות.
אגב, פתרון יעיל נדמה לי שיש באתר של אולימפיאדת מדעי המחשב, אני לא בטוח...
|
|
|
כן אבל הכוונה לרקורסיה בשיטה עצמה לא בשיטת העזר.
השיטה צריכה להיות רקורסיבית...הבנתי כי הפתרון מבוסס על אלגוריתם knapsack
ונכנסתי כעת לאתר האולימפיאדה וואו תודה אתר מצויין
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 04 January 2008 בשעה 23:30 | | IP רשוּם
|
|
|
|
אגב לא הבנתי כל כך ה num שמוגדר בחתימת השיטה
public static boolean isFillBag (int[] arr, int num)
זה הsum אצלך?
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 05 January 2008 בשעה 09:35 | | IP רשוּם
|
|
|
|
כן
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 05 January 2008 בשעה 09:57 | | IP רשוּם
|
|
|
|
טוב ניסיתי אבל זה לא עובד משום מה
קוד:
|
public static boolean isFillBag (int[] arr, int num)
{
int index=0,sum=0;
int total=num;
boolean res=inner(arr, 0, 0, sum);
return res;
}
public static boolean inner(int[] arr, int index, int sum, int total)
{
if (index == arr.length)
{
return (sum == total);
}
if (inner(arr, index+1, sum+arr[index], total))
{
System.out.println("The answer was found: "+sum);
return true;
}
if (inner(arr, index+1, sum, total))
{
System.out.println("The answer was found: "+sum);
return true;
}
System.out.println("The answer was not found ");
return false;
}
} |
|
|
זה הטסטר שלי
קוד:
public class Test4 extends Ex16_4
{
public static void main(String[] args)
{
System.out.println("******************************");
int[] a = new int[5];
int tar=10, i=0;
a[0] = 1;
a[1] = 2;
a[2] = 0;
a[3] = 8;
a[4] = 16;
for (int i = 0 ; i<= 5; i++)
{
isFillBag(a,tar);
}
}
|
|
|
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 05 January 2008 בשעה 10:10 | | IP רשוּם
|
|
|
|
תוריד את
The answer was not found בפעמיים ב-inner
ואם אתה רוצה תוסיף את הבדיקה הזאת בקריאה מהתכנית הראשית.
לא הבנתי את הלולאה בתכנית הראשית ואת ההגדרת משתנים ב-isFillBag
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 05 January 2008 בשעה 10:26 | | IP רשוּם
|
|
|
|
shoshan כתב:
תוריד את
The answer was not found בפעמיים ב-inner
ואם אתה רוצה תוסיף את הבדיקה הזאת בקריאה מהתכנית הראשית.
לא הבנתי את הלולאה בתכנית הראשית ואת ההגדרת משתנים ב-isFillBag |
|
|
טוב הורדתי אני מקווה שאת הנכון.
מחקתי את הגדרת המשתנים כי חשבתי ש ה-num אצלי שזה המספר שאליו צריך להגיע
זה לא ה-sum אצלך.
קוד:
|
public static boolean isFillBag (int[] arr, int num)
{
int index=0;
boolean res=inner(arr, 0, 0, num);
return res;
}
public static boolean inner(int[] arr, int index, int num, int total)
{
if (index == arr.length)
{
return (num == total);
}
if (inner(arr, index+1, num+arr[index], total))
{
return true;
}
if (inner(arr, index+1, num, total))
{
System.out.println("The answer was found: "+num);
return true;
}
return false;
}
}
|
|
|
ומחקתי את הלולאה בראשית
קוד:
public class Test4 extends Ex16_4
{
public static void main(String[] args)
{
System.out.println("******************************");
int[] a = new int[5];
int tar=10, i=0;
a[0] = 1;
a[1] = 2;
a[2] = 0;
a[3] = 8;
a[4] = 16;
isFillBag(a,tar);
}
}
|
|
|
אבל זה עדיין לא עובד עבור הערכים ששמתי זה מדפיס לי התשובה היא 10
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 05 January 2008 בשעה 10:35 | | IP רשוּם
|
|
|
|
את
קוד:
int index=0;
boolean res=inner(arr, 0, 0, num);
return res; |
|
|
תחליף ב-
קוד:
| return inner(arr, 0, 0, num); |
|
|
והורדת את ההדפסה הלא נכונה, מה שקורה זה שהפונקציה מנסה להגיע לסכום הרצוי עם ובלי ההערך במקום ה-index, בקריאה הרקורסיבית עם, ואז צריך להדפיס, ובשנייה בלי, ואז אין צורך להדפיס.
ובתכנית הראשית, תבדוק מה isFillBag מחזיר ואם זה false תדפיס שהפונקציה לא מצאה פתרון.
ואתה מוזמן להגיד מה זה מדפיס ונראה אם יש איזה באג לוגי.
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 05 January 2008 בשעה 10:49 | | IP רשוּם
|
|
|
|
אוקיי שיניתי
קוד:
|
public static boolean isFillBag (int[] arr, int num)
{
return inner(arr, 0, 0, num);
}
public static boolean inner(int[] arr, int index, int num, int total)
{
if (index == arr.length)
{
return (num == total);
}
if (inner(arr, index+1, num+arr[index], total))
{
System.out.println("The answer was found: "+num);
return true;
}
if (inner(arr, index+1, num, total))
{
return true;
}
return false;
}
} |
|
|
והתוכנית הראשית כך
קוד:
public static void main(String[] args)
{
System.out.println("******************************");
int[] a = new int[5];
int tar=10, i=0;
a[0] = 1;
a[1] = 2;
a[2] = 0;
a[3] = 8;
a[4] = 16;
if(isFillBag(a,tar))
System.out.println("answer is : "+isFillBag(a,tar));
else System.out.println("answer is : "+isFillBag(a,tar));
}
|
|
|
וזה הדפיס לי דבר כזה
*********
the answer was found:2
the answer was found:2
the answer was found:0
the answer was found:2
the answer was found:2
the answer was found:0
answer is: true
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 05 January 2008 בשעה 11:04 | | IP רשוּם
|
|
|
|
הממ...ההדפסה לא טובה:
קוד:
| System.out.println("The answer was found: "+num); |
|
|
צריך להיות משהו כזה:
קוד:
| System.out.println("The answer was found: "+arr[index]); |
|
|
ויש בעיה בתכנית הראשית, אתה קורא לפונקציה פעמיים...
השימוש אמור להיות כזה:
קוד:
if(!isFillBag(a,tar))
System.out.println("sorry, no possible answere ):"); |
|
|
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 05 January 2008 בשעה 11:18 | | IP רשוּם
|
|
|
|
אוקיי עובד מצויין תודה רבה!
קוד:
|
public class Ex16_4
{
public static boolean isFillBag (int[] arr, int num)
{
return inner(arr, 0, 0, num);
}
public static boolean inner(int[] arr, int index, int num, int total)
{
if (index == arr.length)
{
return (num == total);
}
if (inner(arr, index+1, num+arr[index], total))
{
System.out.println("The answer was found: "+arr[index]);
return true;
}
if (inner(arr, index+1, num, total))
{
return true;
}
return false;
}
} |
|
|
והראשית
קוד:
public static void main(String[] args)
{
System.out.println("******************************");
int[] a = new int[5];
int tar=12, i=0;
a[0] = 18;
a[1] = 5;
a[2] = 3;
a[3] = 11;
a[4] = 16;
if(!isFillBag(a,tar))
System.out.println("no answer it is:"+isFillBag(a,tar));
} |
|
|
רק שאלה קטנה איך אני יכול להעביר את עניין ההדפסה לשיטה.
אני רוצה שהשיטה תדפיס הכל ולא התוכנית הראשית
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 05 January 2008 בשעה 11:51 | | IP רשוּם
|
|
|
|
זה מה שקורה כרגע ):
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
זיו1
משתמש פעיל
הצטרף / הצטרפה: 30 November 2007
משתמש: מנותק/ת
הודעות: 66
|
| נשלח בתאריך: 05 January 2008 בשעה 12:18 | | IP רשוּם
|
|
|
|
אוקיי:(
תוכל לעזור לי בעוד שאלה בבקשה
בלוח דו-ממדי בגודל m X n, אשר כל אחת ממשבצותיו יכולה להיות ריקה או מלאה, נקרא כתם לרצף משבצות מלאות בעלות צלע משותפת או קדקוד משותף.
גודל הכתם הוא מספר המשבצות המרכיבות את הכתם.
ייתכנו מספר כתמים בלוח.
דוגמה:
נסמן משבצת מלאה באמצעות התו x ומשבצת ריקה באמצעות תו רווח.
הלוח
מכיל 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 (int [][] mat, int row, int col) ddd
לדוגמה: עבור המערך מהדוגמה הקודמת וזוג המספרים (3, 1) יוחזר 5, ועבור זוג המספרים (4, 4) יוחזר אפס.
ראיתי שניסו לפתור את התרגיל
קוד:
public static int stain(char[][] a, int i, int j)
{
int Counter = 0;
if (a[j] == 'x')
{
if ((i == 0) || (i == a.length - 1) || (j == 0) || (j == a.length - 1))
{
a[j] = ' ';
return 1;
}
else
{
a[j] = ' ';
Counter++;
Counter+=stain(a,i-1,j-1);
Counter+=stain(a,i-1,j);
Counter+=stain(a,i-1,j+1);
Counter+=stain(a,i,j-1);
Counter+=stain(a,i,j+1);
Counter+=stain(a,i+1,j-1);
Counter+=stain(a,i+1,j);
Counter+=stain(a,i+1,j+1);
}
}
return Counter;
}
} |
|
|
אבל ישנה בעיה
השינוי בערכי המערך מה שאסור היה(מ-x ל- ' ')
וגם בהחזרה הראשונה שזה לא מבצע בדיקה על 8 התאים הבאים
|
| חזרה לתחילת העמוד |
|
| |
|
|
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
