פורסם 2007 בדצמבר 717 שנים היי,אני צריך עזרה דחופה בתרגיל מטורף שקיבלתי לעשות, ואני אפילו לא יודע איך להתחיל אותו... :פלינדרום הוא סדרת תאים סימטרית במערך, כלומר כזו שקריאתה מימין לשמאל וקריאתה משמאל לימין נותנות אותה תוצאה. לדוגמה: {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מי שיודע או יש לו רעיון כללי איך להתחיל, בבקשה ליצור קשר דחוף! דרך אגב, מי שכתב את התרגיל רצה לעשות לי חיים קשים ואומר שאי אפשר להשתמש בפונקציות או במערך מימדיים אחרים... כל הבאסה לי...תודה
פורסם 2007 בדצמבר 717 שנים אסור פונ' גם שאתה כותב? (לכתוב פונ' שבודקת אם מערך הוא פולינדרום ואז לשלוח כל פעם חלקים מהמערך)
פורסם 2007 בדצמבר 717 שנים מחבר לא לצערי אסור לגמרי פונקציות... זה כל הקושי בתרגיל... לבדוק את המיומנות הבסיסית שלך להתמודד עם תרגיל קשה בלי שלמדת פונקציות....השאלה היא איך אני בכל זאת עושה זאת? עם המון לולאות?
פורסם 2007 בדצמבר 717 שנים לא לצערי אסור לגמרי פונקציות... זה כל הקושי בתרגיל... לבדוק את המיומנות הבסיסית שלך להתמודד עם תרגיל קשה בלי שלמדת פונקציות....השאלה היא איך אני בכל זאת עושה זאת? עם המון לולאות?כן אני מניח..מתחיל מהאיבר הראשון מחפש איבר דומה ואז בודק אם כל הדרך בינהם פולינדרום,מחפש עוד איבר דומה ואז בודק את כל הדרך..ואז עובר לאיבר השני וכו3 לולאות לדעתי
פורסם 2007 בדצמבר 717 שנים כן אני מניח..מתחיל מהאיבר הראשון מחפש איבר דומה ואז בודק אם כל הדרך בינהם פולינדרום,מחפש עוד איבר דומה ואז בודק את כל הדרך..ואז עובר לאיבר השני וכו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 ומחפש פולינדרום יותר ארוך.
פורסם 2007 בדצמבר 717 שנים אני חושב שיש דרך יותר יעילה: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?אין לי כוח לעבור על זה ולהבין בדיוק מה עשית אבל אם כן אז יופי : )
פורסם 2007 בדצמבר 717 שנים אגב, יש דרך יותר יעילה מזו. הדרך הזו היא ב-(O(n^3, יש דרך ב-(O(n^2. ויש סיבה שאתה לא מגלה לנו אותה?
פורסם 2007 בדצמבר 717 שנים כי אני מניאק זה די פשוט - הפתרון ש-TaZeR הציע פשוט עובר על כל תתי המערכים שבמערך, באמצעות j (תחילת התת-מערך) ו-i (סוף התת-מערך), ועבור כל אחד מהם הוא בודק אם הוא פלינדרום. יש פה הרבה כפילויות - אם המערך מ-3 עד 5 אינו פלינדרום, אז ברור שהמערך מ-2 עד 6 אינו פלינדרום, אבל הפתרון לא בודק את זה. הפתרון הוא במקום ש-i יציין את תחילת (או סוף) תת המערך, i יציין את אמצע תת המערך, וכל פעם נרחיב את המערך בעוד תא מכל צד. על כל תא שהוספנו והתת-מערך עדיין נשאר פלינדרום, נגדיל את counter ב-1, וכשמוסיפים תא מכל צד והתת-מערך כבר לא פלינדרום, ממשיכים הלאה (מגדילים את i).
פורסם 2007 בדצמבר 717 שנים אגב, יש דרך יותר יעילה מזו. הדרך הזו היא ב-(O(n^3, יש דרך ב-(O(n^2. שים לב שהתרגיל בכלל מגביל את מרחב הקלט, אז אפשר לחשב פעם אחת מראש את כל האפשרויות ואז לתת פתרון ב O של אחת כל פעם
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.