הוסטס - פורום אחסון האתרים הגדול בישראל - שפת C

- פורום תיכנות (https://hosts.co.il/forums/forumdisplay.php?f=14)

- - שפת C - פיתרון אלטרנטיבי לבעיה? (https://hosts.co.il/forums/showthread.php?t=56152)

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

שלום!

קיבלתי לש.ב בשפת 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.

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

תודה!

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

תודה על האתגר לשעת ערב זו ;)

למיטב הבנתי את השאלה, אתה צריך לטפל גם במקרה כזה:
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 (פרסם 576221)

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

בלי מצביעים:

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. (ז"א מבחינתנו זה עכשי והתו
הראשון)