| כותב |
|
אסף
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 14 December 2007 בשעה 22:19 | | IP רשוּם
|
|
|
|
מישהו יכול בבקשה לעזור לי עם השאלה הזאת, ממש ניתקעתי איתה, צריך לפתור אותה ברקורסיה ואין לי מושג איך עושים את זה...
שאלה 5
רוצים להושיב
k סטודנטים הנבחנים בבחינה
בשורה אחת המכילה n
כסאות. ידוע ש 1-n ≥ 2k.
על מנת למנוע העתקות בבחינה הוחלט שבין כל שני נבחנים יהיה לפחות כסא ריק אחד. את סדר
הישיבה יתאר מערך, students,
באורך n
שאבריו הם 0 ו-1.
נסמן ב Students[i]=0 אם הכסא ה-
i י ריק, ו- Students [i]=1 אם קיים נבחן היושב בכסא
ה--i-י. (הכיסאות
ממוספרים מ 0 עד n-1).
כתבו פונקציה
המקבלת את המערך students ואת הפרמטריםn ו- k ומדפיסה את כל האפשרויות
למקם את הנבחנים.
לדוגמא, עבור
n=5, k=2 על
הפונקציה להדפיס את כל הישיבות האפשריות של הסטודנטים.
00101
01001
01010
10001
10010
10100
הפונקציה
יכולה לקבל פרמטרים נוספים אם יש צורך.
אם
לא ניתן למצוא סידור כזה הפונקציה לא מדפיסה דבר.
יש לי את התוכנית עצמה במחשב אז אם מישהו לא מבין את השאלה בבקשה תפנו אלי ואני ישלח לכם את התוכנה, אפשר לפנות אלי דרך המסנג'ר.
asi_malki1@walla.com
תודה מראש.
אסף.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 15 December 2007 בשעה 09:46 | | IP רשוּם
|
|
|
|
כתבתי ב-CPP, נקווה שאתה יודע איך להמיר...
קוד:
void PrintPossibilitiesInner(bool* arr, int n, int k, int i)
{
if(k == 0)
{
for (int i = 0 ; i < n ; ++i)
cout << arr[i] << ' '; // replace with printf
cout << endl; // replace with printf
return;
}
if ((n+1-i)/2 < k) // this also includes i >= n
return;
PrintPossibilitiesInner(arr, n, k, i+1);
arr[i] = true;
PrintPossibilitiesInner(arr, n, k-1, i+2);
arr[i] = false;
} |
|
|
הקריאה הראשונה לפונקציה היא בערך כזאת:
קוד:
void PrintPossibilities(int n,int k)
{
bool* arr = new bool[n];
for (int i = 0 ; i < n ; ++i)
arr[i] = false;
PrintPossibilitiesInner(arr, n, k, 0);
} |
|
|
|
| חזרה לתחילת העמוד |
|
| |
אסף
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 15 December 2007 בשעה 09:51 | | IP רשוּם
|
|
|
|
מצטער, שכחתי להגיד שאסור להשתמש בלולאות בכלל...
אבל תודה על התגובה.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 15 December 2007 בשעה 13:30 | | IP רשוּם
|
|
|
|
הלולאות פה זה רק בשביל ההדפסה והאתחול של המערך.
את ההדפסה אין לי רעיון איך אתה יכול להכניס בפורמט הנוכחי להכניס לפונקציה
הרקורסיבית, אבל אולי תממש גם אותה בעזרת רקורסיה...
את האתחול אתה מוזמן לעשות ע"י ההקצאה של C שמאתחלת גם את הערכים בזכרון
שהוקצה (calloc).
|
| חזרה לתחילת העמוד |
|
| |
אסף
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 15 December 2007 בשעה 19:03 | | IP רשוּם
|
|
|
|
טוב, אז אחרי שהימרתי את זה לC והוספתי פונקציה שמדפיסה בצורה רקורסיבית, הגעתי לדבר הזה
קוד:
#include<stdio.h>
void PrintArray(int students[], int n);
void CheckSeats(int students[], int n, int k, int i);
#define MAX 100
void main(){
int students[MAX] = {0}, k, n;
printf("Please enter number of students: ");
scanf("%d", &k);
printf("Please enter number of seats: ");
scanf("%d", &n);
CheckSeats(students, n - 1, k, 0);
}
void CheckSeats(int students[], int n, int k, int i)
{
if(k == 0)
{
PrintArray(students, n);
printf("\n");
return;
}
if ((n+1-i)/2 < k)
return;
CheckSeats(students, n, k, i+1);
students = 1;
CheckSeats(students, n, k-1, i+2);
students = 0;
}
void PrintArray(int students[], int n){
if (n > 0)
PrintArray(students, n - 1);
printf("%d", students[n]);
}
|
|
|
אולם זה עדיין לא עובד לי לגמרי, רק כמעט, למשל עבור קלט של 2 סטודנטים ו5 כיסאות, במקום
00101
01001
01010
10001
10010
10100 זה מדפיס לי רק את האפשרויות הבאות 01010 10010 10100
יש לך אולי מושג למה זה קורה?
ושוב, תודה על העזרה, ממש תרגיל מעצבן.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 15 December 2007 בשעה 20:02 | | IP רשוּם
|
|
|
|
כי לא היית צריך להעביר N-1 אלא פשוט N
אגב, תרגיל נחמד ואני מקווה שהבנת את הפתרון.
|
| חזרה לתחילת העמוד |
|
| |
זה עובד!!!
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 15 December 2007 בשעה 20:41 | | IP רשוּם
|
|
|
|
אחי, אתה תותח.
ישבתי באמת הרבה על הדבר הזה אבל שום דבר לא זז...
תודה רבה.
|
| חזרה לתחילת העמוד |
|
| |
11010010110
פורומיסט על
הצטרף / הצטרפה: 23 April 2006
משתמש: מנותק/ת
הודעות: 2621
|
| נשלח בתאריך: 16 December 2007 בשעה 00:37 | | IP רשוּם
|
|
|
|
קוד:
# include <stdio.h>
# define N 11
# define K 5
int x (int ,int ,int) ;
void w (int) ;
int main ( )
{
if (!x (4 ,N ,K)) printf ("no possible combinations") ;
return 1 ;
}
int x (i ,n ,k)
{
if (k > (n + ! (i % 2)) / 2) return 0 ;
if (n < 1) { w (i) ; return 1 ; }
return (x (2 * i ,n - 1 ,k) + (k && !(i % 2) && x (2 * i + 1 ,n - 1 ,k - 1))) ;
}
void w (i)
{
if (i == 4) { printf ("\n\n") ; } else { w (i / 2) ; printf ("%d" ,i % 2) ; }
return ;
} |
|
|
|
| חזרה לתחילת העמוד |
|
| |
אסף
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 16 December 2007 בשעה 09:31 | | IP רשוּם
|
|
|
|
זאת עוד דרך?
|
| חזרה לתחילת העמוד |
|
| |
אסף
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 20 December 2007 בשעה 12:19 | | IP רשוּם
|
|
|
|
shoshan, שמתי לב שבתוכנית שרשמת פה, זה מדפיס אפס אחד מיותר, כאילו במקום להדפיס למשל 00101, זה מדפיס 001010, האפס הימני מיותר, יש לך מושג למה זה עושה את זה ואיך אפשר להיפתר מזה?
תודה מראש.
|
| חזרה לתחילת העמוד |
|
| |
אסף
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 20 December 2007 בשעה 12:23 | | IP רשוּם
|
|
|
|
לא משנה, תיקנתי את זה, שלחתי לפונקצית הדפסה שלי n במקום n-1.
|
| חזרה לתחילת העמוד |
|
| |
|
|
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
