צריך עזרה אם תרגיל שפת c רקורסיה

[c5123]

befor f pos=0 stud=2
 arr print=0 0 0 0 0
befor f pos=1 stud=2
 arr print=0 0 0 0 0
befor f pos=2 stud=2
 arr print=0 0 0 0 0
befor f pos=3 stud=2
 arr print=0 0 0 0 0
befor f pos=4 stud=2
 arr print=0 0 0 0 0
after f pos=4 stud=2
 arr print=0 0 0 0 1
after f pos=3 stud=2
 arr print=0 0 0 1 0
after f pos=2 stud=2
 arr print=0 0 1 0 0
befor f pos=4 stud=1
 arr print=0 0 1 0 0
after f pos=4 stud=1
 arr print=0 0 1 0 1
0 0 1 0 1
after f pos=1 stud=2
 arr print=0 1 0 0 0
befor f pos=3 stud=1
 arr print=0 1 0 0 0
befor f pos=4 stud=1
 arr print=0 1 0 0 0
after f pos=4 stud=1
 arr print=0 1 0 0 1
0 1 0 0 1
after f pos=3 stud=1
 arr print=0 1 0 1 0
0 1 0 1 0
after f pos=0 stud=2
 arr print=1 0 0 0 0
befor f pos=2 stud=1
 arr print=1 0 0 0 0
befor f pos=3 stud=1
 arr print=1 0 0 0 0
befor f pos=4 stud=1
 arr print=1 0 0 0 0
after f pos=4 stud=1
 arr print=1 0 0 0 1
1 0 0 0 1
after f pos=3 stud=1
 arr print=1 0 0 1 0
1 0 0 1 0
after f pos=2 stud=1
 arr print=1 0 1 0 0
1 0 1 0 0

אני רואה אך זה עובד

עולה עד 4 וזה יוצר כמו 5 תוכנות ניפרדות, בדרך חזרה

ב 4 ו 3 +2 עובר את התנאי וב 2 זה מפעיל את הפונקציה השניה

00101

הכל הפוך על הפוך לא חושב שהיתי מגיע לפתרון הזה גם אחרי שבוע

אני לא אוהב רקורסיה.

[שניצל]

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

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

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

arr[pos] = 0;

[Armageddon26]

צודק למעט תיקון קטן. אחרי הקריאה הראשונה גם arr[pos+1] יכול להכיל 1 ואז אנחנו נדלג עליו בקריאה השניה והוא יישאר שם.

ככה תיראה הפונקציה אחרי תיקון:

void f(vector<int>& arr, int pos, int students) {
  if (students==0) {
    print(arr);
    return;
  }
  if (pos>=arr.size()) {
    return;
  }
  arr[pos] = 0;
  f(arr, pos+1, students);
  arr[pos] = 1;
  if (pos+1 < arr.size()) {
    arr[pos+1] = 0;
  }
  f(arr, pos+2, students-1);
}

c5123 - תנסה להבין את הקוד כמו באינדוקציה, תניח שזה פשוט עובד על כל מה שקטן מ- n,k ותבין למה זה עובד עבור n,k.

כי הרעיון הבסיסי פשוט - או לקחת את הכיסא או שלא.

[שניצל]

צודק או לחילופין, אפשר לעשות arr[pos]=0 אחרי הקריאה השנייה (כדי "לבטל" את זה ששמנו 1).

[Armageddon26]

או להחליף את סדר הקריאות הרקורסיביות (ולאפס את המערך לפני הכניסה לפונקצייה).

[Ghosthunter]

ד.א. במקום להשתמש ב- clone אפשר לבצע arr[:].

עריכה: או אפילו להשתמש במודול copy. (http://docs.python.org/library/copy.html)