תרגיל למציאת פולינדרום במערך חד-מימדי - C++

[roy_daklon]

היי,

אני צריך עזרה דחופה בתרגיל מטורף שקיבלתי לעשות, ואני אפילו לא יודע איך להתחיל אותו... :

פלינדרום הוא סדרת תאים סימטרית במערך, כלומר כזו שקריאתה מימין לשמאל וקריאתה משמאל לימין נותנות אותה תוצאה. לדוגמה: {1, 5, 7, 5, 1} או:

{1, 5, 5, 1} או {2, 2} (בתכנית זאת לא נתעניין בפלינדרום שאורכו קטן משני תאים).

כתבו תכנית המגדירה מערך בן עשרה תאים, קוראת לתוכו מספרים שלמים חיוביים מהמשתמש, ואחר סופרת ומציגה כמה פלינדרומים מכיל המערך. שימו לב כי סדרת התאים {1, 5, 5, 1} מכילה שני פלינדרומים, שכן גם: {5, 5} הוא פלינדרום. באופן כללי: בין שני פלינדרומים תיתכן חפיפה, בפרט הכלה.

שימו לב: יש לבדוק שהקלט תקין ואם הוא לא יש לפלוט הודעת שגיאה מתאימה.

הודעת השגיאה היא "bad input". יש להמשיך לבקש קלט בלולאה עד שהקלט תקין.

דוגמא: נניח שהיה לנו מערך בין 4 תאים. אזי עבור הקלט {1, 5, 5, 1}

ניתן פלט של 2. (אבל בתרגיל אורך הקלט הוא 10 תאים).

שימו לב: 1) יש להניח שכל תא במערך הוא מספר חד-ספרתי דהיינו שלם , בין 0 ל9.

2) במקרים שאין אף פולינדרום יש לפלוט 0

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

תודה

[a_lk]

אסור פונ' גם שאתה כותב? (לכתוב פונ' שבודקת אם מערך הוא פולינדרום ואז לשלוח כל פעם חלקים מהמערך)

[roy_daklon]

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

השאלה היא איך אני בכל זאת עושה זאת? עם המון לולאות?

[a_lk]

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

השאלה היא איך אני בכל זאת עושה זאת? עם המון לולאות?

כן אני מניח..

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

ואז עובר לאיבר השני וכו

3 לולאות לדעתי

[TaZeR]

כן אני מניח..

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

ואז עובר לאיבר השני וכו

3 לולאות לדעתי

אני חושב שיש דרך יותר יעילה:

int counter = 0;

for (int i=2; i<=array.len; i++)

{

for (int j=0; j<array.len - i; j++)

{

for (int k = 1; k<=(i +1)/2; k++)

{

if (array[j+k]==array[j+(i-1)-k])

{

if ((k==(i+1)/2)||(k==i/2))

{

counter++;

}

else

continue;

}

else

{

break;

}

}

}

}

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

[a_lk]

אני חושב שיש דרך יותר יעילה:

int counter = 0;

for (int i=2; i<=array.len; i++)

{

for (int j=0; j<array.len - i; j++)

{

for (int k = 1; k<=(i +1)/2; k++)

{

if (array[j+k]==array[j+(i-1)-k])

{

if ((k==(i+1)/2)||(k==i/2))

{

counter++;

}

else

continue;

}

else

{

break;

}

}

}

}

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

הקוד שלך בודק את המצב של 1551 ומחזיר בו 2?

אין לי כוח לעבור על זה ולהבין בדיוק מה עשית אבל אם כן אז יופי : )

[שניצל]

אגב, יש דרך יותר יעילה מזו.

הדרך הזו היא ב-(O(n^3, יש דרך ב-(O(n^2.

[LazyBoy]

אגב, יש דרך יותר יעילה מזו.

הדרך הזו היא ב-(O(n^3, יש דרך ב-(O(n^2.

ויש סיבה שאתה לא מגלה לנו אותה?

[שניצל]

כי אני מניאק

זה די פשוט - הפתרון ש-TaZeR הציע פשוט עובר על כל תתי המערכים שבמערך, באמצעות j (תחילת התת-מערך) ו-i (סוף התת-מערך), ועבור כל אחד מהם הוא בודק אם הוא פלינדרום. יש פה הרבה כפילויות - אם המערך מ-3 עד 5 אינו פלינדרום, אז ברור שהמערך מ-2 עד 6 אינו פלינדרום, אבל הפתרון לא בודק את זה.

הפתרון הוא במקום ש-i יציין את תחילת (או סוף) תת המערך, i יציין את אמצע תת המערך, וכל פעם נרחיב את המערך בעוד תא מכל צד. על כל תא שהוספנו והתת-מערך עדיין נשאר פלינדרום, נגדיל את counter ב-1, וכשמוסיפים תא מכל צד והתת-מערך כבר לא פלינדרום, ממשיכים הלאה (מגדילים את i).

[LazyBoy]

אשכרה הבנתי אותך

[exercise]

אגב, יש דרך יותר יעילה מזו.

הדרך הזו היא ב-(O(n^3, יש דרך ב-(O(n^2.

שים לב שהתרגיל בכלל מגביל את מרחב הקלט, אז אפשר לחשב פעם אחת מראש את כל האפשרויות ואז לתת פתרון ב O של אחת כל פעם