היי

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

לדוגמא abcd ו- dcba, עכשיו חשבתי לקחת את הפוינטר של אחד מהמחרוזות לסוף המחרוזת ולהשוות אותו לפוינטר השני שמצביע על תחילת המחרוזת השניה, הבעיה שבפונקציה רקורסיבית זה קצת קשה לעשות את זה.

מישהו מכיר דרך אחרת? או אולי פונקציה שמריצה את הפוינטר לתו האחרון?

תודה

יש את strlen שמחזירה את אורך המחרוזת.

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

היי omri123

הכנתי בשבילך את הפונקציה: היא משווה בכל סיבוב בית התו האחרון ב2 לתו הראשון ב1.

מחזירה 1 אם המחרוזות שוות ו0 אם הם לא שוות.

int fuction(char *str1, char *str2)
{
  int i=strlen(str2);//אורך המחרוזת בסיבוב הנוחכי

  if(str1[0] == str2[i-1] &&)//השוואה בין הצו האחרון במחרוזת2 לתו הראשון במחרוזת1
   if(str1 != NULL || str2 != NULL)//בדיקה שהמחרוזת לא הסתיימה
   {
     str2[i-1]='\0';//קיצור מחרוזת2 מהסוף
     fuction(str1++, str2)//קיצור מחרוזת1 מההתחלה וקיראה רקורסיבית
   }
   else if(str1 == NULL || str2 == NULL)
     return 1;//אם התווים שווים וזה סוף המחרוזת יוחזר 1
  else 
   return 0;//אם התווים לא שוום יוחזר 0
}
[code/]

לוטם 

^ראשית, המטרה כאן אינה לתת את התשובות אלא לעזור לחשוב ולכוון.

שנית, כשכותבים קוד על גבי הפורום, יש להשתמש בתג "הוסף קוד"

מה גם שיש בקוד באגים:

א. מי אמר שמותר לשנות את המחרוזות?

ב. ההשוואות ל-NULL לא נכונות בכלל.

ג. הקריאה ל-strlen בכל איטרציה של הפונקציה הופכת את הקוד ללא יעיל בעליל.

מה גם שיש בקוד באגים:

א. מי אמר שמותר לשנות את המחרוזות?

ב. ההשוואות ל-NULL לא נכונות בכלל.

ג. הקריאה ל-strlen בכל איטרציה של הפונקציה הופכת את הקוד ללא יעיל בעליל.

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

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

נקדם את כתובת תחילת str1 (המחרוזת המקורית לא תושפע! str1 של הפונקציה הוא לא str1 של הmain)

ונשלח את str2 ללא התו האחרון לכן אני משווה אותו לNULL (המחרוזת המקורית תשתנה).

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

static int i=strlen(str2);

שורה זו תרוץ רק בפעם הראשונה וכל סיבוב תוכל לשנות את i ע"י i--.

ב. בסוף מחרוזת יש זקיף שזה '/0' או 0 או NULL

ג. יש בזה צדק עדיף להשתמש במשתנה סטטי.

לוטם

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

לוטם:

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

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

ב. נכון, אבל הקוד שלך משווה את המצביע (str) ולא את התו (str*).

ג. ממש לא, והסברתי למה.

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

קיצר צריך לשנות להשתמש באופרטור [] או ב-* כדי לבדוק אם המחרוזות הסתיימו.

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

bool recursive_mirror(const char* forward, const char* backward, size_t len)
{
  /*                                                  
   Some checks and comparisons                                    
   ...                                                
   ...                                                

   Then the recursive call                                      
  */
  return recursive_mirror(++forward, --backward, --len);
}

קודם שאלת לגבי ה-counter שים לב שגם בדוגמה שלי הוא קיים (המשתנה len) וגם הוא עובר ברקורסיה.

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

שניצל:

א: אז אפשר לשים את התנאי הבא:

if(*str1 != '/0') //תנאי עצירה: סיום אחת המחרוזות
	if(str1[0] == func(str1++, str2--));
	else return 0;
return 1;

ב.

str[x]==*(str+x)

אם יש סוגריים מרובעים זה במקום *

קצת יותר טוב, למרות שהקוד שלך לא מתקמפל (עשית if בלי שום קוד שרץ אחריו, ובכלל לא ברור מה המשמעות של התנאי שבו). חוץ מזה, גם השימוש שלך ב++ וב-- לא נכון: ++x מקדם את הערך של x באחד, אבל מחזיר את הערך שהיה לפני שהוא קודם. כלומר, הקוד הבא:

int x = 0;
printf("%d", x++);

ידפיס 0, לא 1.

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

בכלל, לדעתי זה תכנות רע להשתמש בערך ההחזרה של אופרטור ++. אם רוצים רק לשנות את x אז משתמשים ב-++x. אם רוצים רק את התוצאה של הפעולה (נגיד, בשביל להעביר אותה כפרמטר לפונקציה), אז משתמשים ב-x+1 כמו שציינתי. אם רוצים גם וגם - מפרידים לשתי פקודות, כי זה הרבה יותר קריא והרבה פחות מועד לבאגים. לדוגמה, אחד קטעי הקוד שאנשים אוהבים להתלהב ממנו הוא המימוש של הפונקציה strcpy:

void strcpy(char *dst, const char *src) {
 while (*dst++ = *src++);
}

הבעיה בקוד הזה היא שהוא דורש המון מאמץ כדי להבין אותו (מה מעתיקים בדיוק? מתי? מה קורה קודם, הקידום של המצביעים או ההעתקה? מתי הלולאה נגמרת?)

לעומת זאת, קוד דומה שעושה אותו דבר, אבל הרבה הרבה יותר קריא:

void strcpy(char* dst, const char* src) {
 while (*src != '\0') {
  *dst = *src;
  src++;
  dst++;
 }
 *dst = *src;
}

כאן ברור במאה אחוז בדיוק מה קורה בכל איטרציה של הלולאה, מתי היא מסתיימת וכו'.