שאלה

[איוואן איליץ]

שאלה

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

 

[yossiea]

בעייה מוכרת...

נשאל אחרת: נתון מערך a בגודל n ו-s כלשהו. מצא האם קיימת תת-סדרה של a שסכום אבריה הוא s (לא לפי סדר כלשהו). אם נוסיף וקטור בוליאני x השאלה תראה בערך ככה:

s = a1*x1 + a2*x2 + a3*x3 + ... + an*xn​

כלומר כאשר xi=0 אתה מדלג על האלמנט וכאשר הוא 1 אתה לוקח אותו בחשבון. אתה כבר רואה שאפשר לבצע לולאה כזו (גם רקורסיבית) על כל הצירופים הבינאריים האפשריים של x בגודל n סיביות ולבדוק אם מתקיימת המשוואה האחרונה. מתי שהוא תגיע לתוצאה כלשהי. רק שהסיבוכיות כאן 2 בחזקת n שזה גבוה מאוד. יש דרכים יותר יעילות. אבל בעקרון זו בעיה שמוגדרת קשה (NP-complete). למדת את זה או לא? כי אם לא למדת על זה, "קצת" קשה לחשוב על פתרון לבד תוך כדי מבחן

לא?

 

[איוואן איליץ]

תודה על העזרה

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

 

[אמיר ל]

אני פתרתי את השאלה. להלן האלגוריתם

מה שעשיתי, הוא ליצור שני איטרטורים ברקורסיה, האחד מייצג את האיבר הנוכחי במערך, שאני בודק צירופים עבורו, והשני מייצג את המספרים שאחריו. כלומר, הוא רץ על המערך. בנוסף, העברתי כפרמטרים את הסכום (שאתחלתי לאיבר הראשון במערך ב-Pre Conditions) ואת המספר שצריך להגיע אליו, וכמובן המערך. היו לי שני שלושה תנאי סיום: 1. אם האיטרטור שמייצג את האיבר הנוכחי גדול מהמערך, סימן שלא מצאתי צירוף מספרים ששווה למספר, ואז אני מחזיר 0. 2. השני הוא כמובן, אם הסכום שווה למספר, ואז אני מחזיר 0. דרך אגב, יכול להיות גם שהאיבר עצמו, ללא צירוף נוסף יהיה שווה למספר. 3. אם האיטרטור שרץ על כל איברי המערך גדול מהמערך, אני בודק את צירוף המספרים עבור האיבר הבא. כלומר, אני קורא לפונקציה רקורסיבית עם קידום של האיבר הנוכחי ב-1, וקידום של האיטרטור שרץ על איברי המערך באיבר הנוכחי + 2 (1 אחרי האיבר הבא). הסיבה שקידמתי גם אותו, היא שממילא אני בדקתי את כל הצירופים עבור האיבר הבא עם המספרים שלפניו, ולכן אין טעם לבדוק את זה. 3. במקרה שלא נעצרתי, אני בודק האם הסכום + האיבר הבא קטן מהמספר שהעברתי כפרמטר. אם כן, אני מעביר כפרמטר, את הסכום + האיבר הבא, ומקדם את האיטרטור שרץ על המערך ב-1. 4. אם הסכום + האיבר הבא גדול מהמספר שהעברתי כפרמטר, אני קורא לפונקציה עם אותם פרמטרים, מלבד האיטרטור של המערך, שאני מעלה ב-1. 5. אם הסכום שווה למספר, אני מחזיר את אותם פרמטרים, ואז נעצר באיבר שבהתחלה, כי הסכום שווה למספר. הערה: יכולתי לחסוך בזמן ריצה, אם הייתי קובע תנאי, שאם האיבר הנוכחי (שהאיטרטור הנוכחי מצביע עליו) גדול מהסכום יש לעבור לאיבר הבא. מקווה שהבנת, אמיר.

 

[איוואן איליץ]

מה עם זה?

public static boolean f(int[] a, int b) { return f(a, 0, b); } private static boolean f(int[] a, int i, int b) { if (b == 0) { return true; } else if (i == v.length){ return false; } else { return f(a, i+1, b) || f(a, i+1, b-a); } }​

 

[אמיר ל]

לדעתי יש לך טעות בתנאי העצירה הראשו

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

//Pre: The function gets an array full with numbers. The array's //size is 6. The function also gets two counters, i and curr. i //equals 0 and curr equals 1. The function also gets an amount from //the user. The function also gets a sum that equals values[0]. int is_amount(int values [6], int i, int curr, int amount, int sum) { //If the I've passed the array, I return 0, because I haven't found //a combination in the array that equals the amount. if(i==6) return 0; //If I've reached a sum that equals the amount, I return 1. if(sum==amount) return 1; //If I've checked all the combinations for the current number //in the array or it's bigger than the amount, I check the //combinations for the next one. if(curr==6&&sum>amount) return is_amount(values,i+2,amount,values[i+1]); //If the current sum with the current values is smaller than amount //I upadte it, and check with the next number in the array. if(sum+values[curr]<amount) return is_amount(values,curr+1,amount,sum+values[curr]); //If the current sum with the next number in the array are bigger //than the amount, I check the sum with the next number in the //array. if(sum+values[curr]>amount) return is_amount(values,curr+1,amount,sum); }​

 

[yossiea]

יש לך טעות...

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

 

[אמיר ל]

אתה צודק. בקשר לשאלה שלך,

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

 

[yossiea]

עדיין לא ברור...

התיקון שהצעת לא ברור עדיין. אתה לא יכול להוריד את i מההצהרה כי אתה משתמש בו בתוך הפונקציה. מצד שני לא ברור איזה פרמטר אתה רוצה להוסיף בקריאה הרקורסיבית. בקיצור אתה בטוח שפעם שהרצת את הקוד הזה? או שזה רק תיאורתי? בכל מקרה הרעיון עצמו ברור. בודקים את כל הקומביצניות האפשריות של סכומי מספרים, אם יש. וזמן הריצה הוא O של 2 בחזקת n. אני חושב שאפשר לממש את זה בצורה יותר יעילה. אם כי לא נסיתי כיוון שיש אלגוריתמים יותר יעילים. אולי לא ברקורסיה. אם זה מעניין מישהו. זה לא הוזכר קודם. אבל הבעיה נקראת Knapsack או Subset sum. פעם המציאו אלגוריתם הצפנת מפתח פומבי שמבוסס על זה. אבל פיצחו אותו.

 

[אמיר ל]

הפתרון...

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

 

[Belgarath1]

אפשרות

bool f(int arr[], int size, int s) { if (s == 0) return true; if (size == 0) return false; return f(arr + 1 , size - 1, s - arr[0]) || f(arr + 1, size - 1, s) }​