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

[c5123]

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

רוצים להושיב K סטודנטים הנבחנים בבחינה בשורה אחת המכילה N כסאות. ידוע ש N>= 2K-1

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

מערך students באורף N שאבריו הם 0 ו 1

מסמן ב students=0 אם הכסא ה i ריק ו- 1= אם קיים נבחן היושב בכסא ה- i כתבו פונקציה המקבלת את המערך students ואת הפרמטרים n ,k ומדפיסה את כל האפשרויות למקם את הנבחנים

לדוגמא עבור k=2 N=5 על הפונקציה להדפיס את כל הישיבות האפשריות של הסטודנטים

00101

01001

01010

10001

10010

10100

כתבתי תוכנית שעבדה טוב אבל רק על 2 סטודנטים וזה קצת מתחיל לשגע איתי

אני צריך כיוון חדש

אני לא יודע אך לעשות את זה בלי משתנים

ב 2 זה קל יש לי a b וקידמתי את b עד הסוף ואז הוספתי ל a ++ ומהתחלה

הבעיה היא שאני לא יכל לדעת כמה סטודנטים היו אז אין סוף משתנים .. אני לא בכיוון הנכון בכלל

תרגילים ברקורסיה

[שניצל]

א. תאמר באיזו שפת תכנות אתה כותב.

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

ג. תערוך את הטקסט לפונט נורמלי שיהיה קריא יותר...

[Armageddon26]

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

במקרה הזה:

אתה רוצה לפתור עבור n,k.

אז יש 2 אפשרויות:

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

או שבכיסא הזה לא יושב אף אחד ואז ניפתור בעזרת הפיתרון של n-1, k.

נשאר רק להוסיף תנאי בסיס כדי שהרקורסיה תעצר.

[c5123]

ממ לא ממש עזר לי

אני יודע איפה זה מתחיל ואיפה זה ניגמר

אבל יש עוד 1000 אפשרויות ואני צריך את כולם

[Armageddon26]

יצא לך אי פעם להשתמש ברקורסיה?

תנסה לכתוב פונקצייה רקורסיבית שמחשבת את מספרי פיבונצ'י בשביל להתחיל להבין מה זה רקורסיה.

כשתצליח תגיב ונמשיך משם.

[c5123]

כן יש עוד כמה תרגילים במטלה

עשיתי 4 מהם

באחד הזה יש לי קצת בעיה (לא יודע למה זה לא מתחבר לי בראש)

כמו

מחשב את סכום איברי המערך שספרת העשרות שלהם היא 7

(אני צריך למחוק כמה שורות בדיקה לפני שאני שלוח את זה )

#include<stdio.h>
#define N 6
int sumseven(int arr[],int n);
int main()
{
 int i,arr[N]={8,4,73,71,170,5},sum=0;
 printf("enter 6 numbers\n");
 for(i=0;i<6;i++)
 scanf("%d",&arr[i]);
 sum=sumseven(arr,N); 
 printf("sum=%d\n",sum);

 return 0;
}
int sumseven(int arr[],int n)
{
 int calc;
 if(n<=0)
 return 0;
 //printf("arr:%d\nn=%d\n",arr[n-1],n);
 calc=arr[n-1]/10;
 calc=calc%10;
 //printf("calc=%d\n",calc);
 if(calc==7)
 return arr[n-1]+sumseven(arr,n-1);
 else
 return sumseven(arr,n-1);

}

[Armageddon26]

סבבה, אז אני אנסה להסביר שוב.

אם נסמן ב-

f(n, k)

את כמות הפתרונות אז

f(n, k) = f(n-2, k-1) + f(n-1, k)

לא היה לי כוח לכתוב ב-C אבל הנה פיתרון בפייתון.

חשוב שתבין אבל למה הוא עובד

def f(arr, pos, students):
  if students==0:
    print arr
    return
  if pos>=len(arr):
    return

  f(clone(arr), pos+1, students)
  b = clone(arr)
  b[pos] = 1  
  f(b, pos+2, students-1)

def clone(arr):
  return [x for x in arr]


n = 6
k = 3
arr = [0]*n
f(arr, 0, k)

[c5123]

טוב בו ניראה אם הבנתי (Python חדש לי אז יכל להיות שלא הבנתי טוב למרות שזה דומה ל C)

תנאי if הראשון נותן סוף ל

f(b, pos+2, students-1)

השני סוף ל

 f(clone(arr), pos+1, students)

אני מנחש ש len(arr) is like strlen for strings נותן את הגודל של המערך

b = מצביע למערך

b pos = 1

זה לא יתן שורה של 1 ?

אתה מקדם את pos+1 עד לגודל של המערך

ואחרי זה Pos+2 students-1

מממ את החלק הזה אני לא כל כך מבין

ואני חושב שאולי יש פה בעיה

pos רץ עד הסוף ואני חושב פעמים הראשונות הוא יעבור את גודל המערך (f(b, pos+2, students-1))

וגם אם לא אז זה ינסה להוסיף 1 בקפיצות של 2 (גם בלי זה הרקורסיה הראשונה שינתה את כל התאים ל 1)

??

[Armageddon26]

הנה ב-C++

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> arr) {
  for (int i = 0; i < arr.size(); i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

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

}


int main() {
  const int n = 5;
  const int k = 2;
  vector<int> arr(n);
  for (int i = 0; i < arr.size(); i++) {
    arr[i] = 0;
  }
  f(arr, 0, k);

}

הבנת את הרעיון הבסיסי שאו שלא משתמשים בכיסא הכי שמאלי ואז מתבזבז מקום אחד - זה מה שהקוד הבא אומר:

f(arr, pos+1, students);

או שכן משתמשים בכיסא הזה ואז מתבזבזים 2 מקומות ויש סטודנט פחות.

arr[pos] = 1;
  f(arr, pos+2, students-1);

בכל מקרה פעם הבאה ממשיכים מהמיקום pos שהוא המיקום שתמיד רלוונטי להמשיך ממנו.

כותבים 1 איפה שיהיה סטודנט.

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

[שניצל]

יש לך באג קטן - לא מספיק לשים 1 איפה שיש סטודנט, צריך גם לשים 0 איפה שאין.

[Armageddon26]

אני מאתחל את זה באפסים לפני שאני שולח לפונקצייה.

אפשר היה לחסוך את האיתחול ולשים 0 או 1 בהתאם למקרה..

[שניצל]

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

[c5123]

זה עובד

אני לא ישקר שאני מבין עד הסוף (רקורסיה )

אבל אני יוסיף כמה שורות printf

כדי לראות אך בדיוק זה עובד

תודה

על העזרה

אני ישתגע אם יתנו לנו רקורסיה במבחן מה"ט

[שניצל]

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

[Armageddon26]

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

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

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