שפת C - פיתרון אלטרנטיבי לבעיה?

[phpyo]

שלום!

קיבלתי לש.ב בשפת C את השאלה הבאה:

שרשרת סימטרית של '$' היא סדרה של תווים המתחילה ומסתיימת ב-'$ד ובדיוק באמצעיתה נמצא התו '$'. כתוב פונקציה המקבלת מערך תווים שאורכו max ואורך של שרשת len ומחיזרה 1 אם יש במערך שרשרת סימטרית של $, או 0 אם אין.

דוגמאות לשרשראות סימטריות

ds4$$$444

abc$xxx$yyy$zzz

אני פתרתי את זה כך:

PHP קוד:

#include <iostream.h>
#include <conio.h>
#define len 7

char str(char string[len])
{
    int i,mik1=-1,mik2,mid;


    for(i=0;i<len;i++)
    {
        if(string[i] == '$')
        {
            if(mik1 == -1)
            {
                mik1 = i;
            }
            else
                mik2 = i;
        }

        }


    mid = mik1+mik2;

    if(mid/2 != mid/2.0)
        return 0;
    else
        if(string[mid/2] == '$')
            return 1;

                else
                                    return 0;
  

}

void main()
{

    int i;
        char string[len];

    for(i=0;i<len;i++)
        string[i] = getche();

                cout<<endl<<(int)str(string);
} 


לשם ניסיון נתתי ל-Len אורך 7.

אשמח לדעת אם יש למישהו פיתרון טוב יותר או פשוט יותר.

תודה!

[mayden]

למדתם פונקציות רקורסיביות?

[phpyo]

לא למדנו.

[SDF]

למיטב הבנתי את השאלה, אתה צריך לטפל גם במקרה כזה:
ab$abe$ab$ab$adsg

כלומר יש מחרוזת סימטרית... פשוט לא עם ה$ ה-1.
כמוכן אין סיבה ממשית לרוץ על כל המחרזות של 100 תווים (למשל) אם מצאנו
את השרשרת ב10 הראשונים...

הנה מימוש שלי:

PHP קוד:

#include <stdio.h>
#include <stdlib.h>


int sim(char **st, int len) {
    int ok = 0, i = 0, fst = 0, next = 0;

    while (!ok && i < len) {
        //printf("%c\n", (*st)[i]);
        if ((*st)[i] == '$') 
            if (!fst) fst = i;
                else {
                    next = (i - fst)+i;
                    if (next < len) {
                        if ((*st)[next] == '$') ok = 1;
                        }
                    else fst = i;
                }
        i++;
    }
    return ok;
}

int main() {
    char* st;
    int st_size = 0;
    printf("Enter ST size: ");
    scanf("%d", &st_size);
    st = (char *) malloc(sizeof(char) * st_size);
    printf("Enter ST(%d): ", st_size);
    scanf("%s", st);

    printf("Result of SIM: %d\n", sim(&st, st_size));
    return 0;

} 


הקוד רץ על GCC, כמובן טל"ח.

פלט:

yury@moon ~ $ gcc sim.c -o sim
yury@moon ~ $ ./sim
Enter ST size: 20
Enter ST(20): abcd$dg$asdg$adgd$dsgsg
Result of SIM: 1
yury@moon ~ $

[phpyo]

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


אשמח לפיתרון שאוכל להבין

תודה!

[O-B]

תגיד איזה נושאים למדתה עד עכשיו כי אפשר לפתור את זה בהרבה דרכים...

[SDF]

נכתב במקור על ידי phpyo

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


אשמח לפיתרון שאוכל להבין

תודה!

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

בלי מצביעים:

PHP קוד:

     while (!ok && i < len) {
        if ((st)[i] == '$') 
            if (!fst) fst = i;
                else {
                    next = (i - fst)+i;
                    if (next < len) {
                        if ((st)[next] == '$') ok = 1;
                        }
                    else fst = i;
                }
        i++;
    }
    return ok; 


ובמילים:
כל עוד ok הוא שקר ולא הגעת לסוף המחרזות בצע:
בדוק תו-תו:
אם התו הנוכחי הוא התו $:
אם זה התו הראשון מהסוג $ שמור את מיקומו למשתנה fst
אחרת
(כניראה זה התו השני שאנחנו מוצאים... המיקום הנוכחי הוא אמצע המחרוזת הסימטרית)
תו ה-$ הבא צריך להיות ב: מיקום נוכחי פחות המיקום של התו הראשון (ההפרש בין
הראשון לאמצע) ועוד המיקום הנוכחי.
אם המיקום הבא לא חורג מאורך המחרוזת, בדוק האם התו אכן שם.
אם כן שנה את ok ל1.
אם לא, הכנס את המיקום הנוכחי למשתנה fst. (ז"א מבחינתנו זה עכשי והתו
הראשון)