נושא: עזרה בבקשה בפתירת תרגיל ברקורסיה - שפת C.

נשלח בתאריך: 19 February 2009 בשעה 23:39 | IP רשוּם

בצורה איטרטיבית, ממיין את המערך בסדר עולה,  רץ עליו ועבור כל ערך ממנו מחזיר

מהמשתנה SUM עד שערכו שווה לאפס (מצאתי) או קטן (לא קיים הסכום).

בקשר לרקורסיה, אם אתה מכיר את המושג מחסנית ?

הפיתרון לכל רקורסיה הוא לדמיין כיצד עובדת המחסנית !

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

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

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

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

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

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

נשלח בתאריך: 19 February 2009 בשעה 23:44 | IP רשוּם

בקשר לשורה הראשונה : "רץ עליו ועבור כל ערך ממנו מחזיר"

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

נשלח בתאריך: 27 February 2009 בשעה 22:47 | IP רשוּם

שני דברים, האחד - הפתרון הרקורסיבי לבעיה הוא די אינטואטיבי ופשוט, להלן האלג' -

תנאי עצירה -
אם גודל המערך == 0 וגם הסכום הרצוי != 0 החזר שקר.
אחרת אם הסכום הרצוי == 0 החזר אמת.

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

 || ([return subset(numbers + 1, size - 1, sum - numbers[0
;(subset(numbers + 1, size - 1, sum

הדבר השני אותו רציתי לציין היא שהבעיה עצמה ידועה כבעיית NP קשה, כלומר לא ידוע שום פתרון בזמן יעיל הפותר אותה, כאשר הכוונה לזמן יעיל היא לזמן לכל היותר מעריכי, כגון -(T(n^3. אז אתה יכול להרגיש בסדר עם זה שלא מצאת שום פתרון איטרטיבי לבעיה כי הוא לכשלעצמו מסובך ומסורבל לכתיבה.

אגב, הפתרון האיטרטיבי שגרשון הציע אינו נכון לדוגמא במערך הממוין -
1,2,3,4,5,6 עם הסכום 11 זה לא יעבוד כיוון שהסכום יגיע למס' שלילי לאחר הספרה 5, למרות שתת הקבוצה {5,6} מקיימת את הסכום.

נשלח בתאריך: 18 March 2009 בשעה 10:58 | IP רשוּם

לא הסברתי נכון את הפיתרון האיטרטיבי, ולכן להלן הפתרון:

void combi()
{
 int numbers[10] = {1,3,5,17};
 int a,b,c,d;
 for (a=0; a<4; a++)
 {
  cout<<numbers[a]<<endl;   // show the combi
  for (b=a+1; b<4; b++)
  {
   cout<<numbers[a]+numbers[b]<<endl;
   for (c=b+1; c<4; c++)
   {
    cout<<numbers[a]+numbers[b]+numbers[c]<<endl;
    for (d=c+1; d<4; d++)
    {
     cout<<numbers[a]+numbers[b]+numbers[c]+numbers[d]<<endl;
    }
   }
  }
 }
}

הפרוצדורה מציגה את כל צירופי הסכומים האפשריים של תאי המערך,

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

זמן הריצה של הפרוצדורה (או כל בעיה כזאת של צירופים) הוא !n (במקרה זה : !4 )

כל הכבוד לתגובה לעיל, אני אישית לא הצלחתי לפתור ברקורסיה (לא חשבתי על הטריק של ה OR ).

נשלח בתאריך: 28 March 2009 בשעה 04:37 | IP רשוּם

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

נשלח בתאריך: 13 April 2009 בשעה 04:00 | IP רשוּם

פתרתי גם רקורסיבית וגם איטרטיבית.

kotzkotz@gmail.com