מישהו יכול לתת לי את הקוד לשאלה 2:
http://webcourse.cs.technion.ac.il/...Files/C_hw6.pdf

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

בברכה, מתן.
www.MatanNarkiss.com

הי

רקורסיה, אף פעם לא קל,

יש כמה סוגי פיתרון לכל מיני בעיות ברקורסיה.

בעיית המדרגות היא בעיית (אני קורא לה) רקורסיה קומבינטורית.

אני אראה לך שתי בעיות שונות שהם ממש אותו פיתרון.

כמה כללים שכדאי לדעת על רקורסיה:
1) רקורסיה צריכה תנאי עצירה.
בתנאי העצירה אפשר רק לסיים, או להדפיס תוצאת ביניים, או לבצע איזו חישוב לשלב הבא, או איפוס
של משתנים לפני שממשיכים.
2) כל משתנה בתוך הפונקציה או משתנה שמועבר לפונקציה , במידה והפונקציה לא תסתיים כי היא קראה לעצמה יידחף למחסנית.
3) כל הקריאות לפונקציות אחרות וכל קוד שלא בוצע בהמשך הפונקציה כי קראו לפונקציה שוב
יידחף למחסנית.
4) כאשר הפונקציה הקוראת לעצמה תעצר בתנאי העצירה, היא תמשיך בביצוע שאר התוכנית על ידי שליפה של המשתנים והקוד מהמחסנית.

בעיית המדרגות דומה מאד לבעייה קומבינטורית אחרת.

נתון מערך בגודל 3 - {}=[3]my_array
מאותחל ב a,b,c

צריך להדפיס את כל החזרות האפשריות.
שהם בעצם 3 בחזקת 3 = 27 אפשרויות שונות עם חזרות - כלומר צריך גם aaa , bbb וכדומה.

זה הפתרון ל 4 אברים , a,b,c,d -
כלומר 4 בחזקת 4 = 256 אפשריות


int count = 0;
void kmbinatorics(char* my_array, int curPlace)
{
if (my_array[curPlace] == '\0')
{
printf("%s\t",my_array);
count++;
return;
}

my_array[curPlace] = 'a';
kmbinatorics (my_array,curPlace+1);

my_array[curPlace] = 'b';
kmbinatorics (my_array,curPlace+1);

my_array[curPlace] = 'c';
kmbinatorics (my_array,curPlace+1);

my_array[curPlace] = 'd';
kmbinatorics (my_array,curPlace+1);
}


int main(int argc, char* argv[])
{
char str[5];
str[4]= '\0';
kmbinatorics(str,0);

printf("count = %d\n" , count);

return 0;
}

בעיית המדרגות היא בדיוק אותו דבר.
תנסה את הדברים הבאים:
1) תקמפל ותריץ את התוכנית.
תעקוב אחרי curPlace

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

במדרגות: אתה צריך את כל האפשרויות למשל:

2,2,2,3
2,3,2,3,
2,3,3,3
3,2,3,2
וכך הלאה.

רמז: אתה קורא לפונקציה פעם עם התקדמות ב 2 ופעם עם התקדמות ב 3.

תחשוב גם מה אתה רוצה לעשות בכל איטרציה לפני שאתה קורא לפונקציה ומה בתנאי העצירה

easp13 at walla.com
easp13 at gmail.com

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

במקרה שלך - אם היו לך הפתרונות לחלק הסולם המתחיל 2 מדרגות מעליך ולחלק הסולם שמתחיל 3 מדרגות מעליך - היית יכול לפתור את הבעיה ע"י הוספת לפתרונות הללו את ערך המדרגה בה אתה כרגע נמצא ובדיקה של מי מהם גדול יותר.

הבעיה הפשוטה ביותר פה, היא סולם באורך הקטן מ-3:
אם יש 2 מדרגות הפתרון הוא פשוט מספר הכדורים במדרגה ה-2.
אם יש פחות מ-2 מדרגות - הפתרון הוא פשוט 0.

הבעיה המצומצמת הזו שאותה אנו יודעים לפתור נקראת בד"כ תנאי עצירה. התנאי בו בודקים אם אורך הסולם הנותר הוא פחות מ-3 צריך להיות התנאי הראשון בפונקציה הרקורסיבית.
אם התנאי לא התקיים - חוזרים למה שאמרתי קודם:
משווים בין הפתרון של עליה ב-2 צעדים (קריאה רקורסיבית)
לבין הפתרון של עליה ב-3 צעדים (קריאה רקורסיבית)

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

קוד:

Count( startIndex, array)
{
  if(array.End - startIndex < 2) 
    return array[startIndex]
  else 
  { x=0; y=0;
    if (array.End - startIndex >= 2)
      x = Count(startIndex + 2, array)
    if (array.End - startIndex >= 3)      
      y = Count (startIndex + 2, array)
    return array[startIndex] + Bigger(x,y)
}

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