ג'אווה - בעיה ברקורסיה

[gshhar]

יש לי תרגיל ברקורסיה שאני לא מצליח אפילו לחשוב איך להתחיל ולפתור אותו, אני שם לב שיש לי בעיה עם סוגי תרגילים ברקורסיה והייתי שמח לעזרה בתרגיל הנ"ל:

נתונה מחרוזת תוים s. במהלך שליחתה ברשת האינטרנט קרתה תקלה וחלק מהתווים במחרוזת

הוכפלו והופיעו ברצף מספר לא ידוע של פעמים. כלומר במחרוזת t שהתקבלה הופיעו כל התווים

של s, לפי הסדר במחרוזת המקורית, אבל לפעמים תו מסוים לא הופיע פעם אחת כמו במחרוזת s

אלא ברצף מספר לא ידוע של פעמים.

נגדיר שמחרוזת תוים t עברה-טרנספורמציה ממחרוזת התווים s , אם כל תו של s נמצא ב- t (לפי

הסדר ב- s) לפחות פעם אחת.

שימו לב שאם תו מופיע במחרוזת s כמה פעמים (נניח k), אז במחרוזת t שעברה טרנספורמציה

הוא יופיע לפחות k פעמים.

לדוגמא:

אם המחרוזת " s = "abbcd

אז כל המחרוזות הבאות עברו-טרנספורמציה ממחרוזת זו:

"abbcd" , "aaaabbcd" , "abbcdddddd" , "aabbccdd" , "abbbccd"

וכל המחרוזות הבאות לא עברו-טרנספורמציה מהמחרוזת

אנו נייצג מחרוזת תווים באמצעות רשימה מקושרת חד-סטרית, כך שכל צומת ברשימה מכיל תו

אחד מהמחרוזת.

public class CharNode {
private char _value;
private CharNode _next;
public CharNode(char val, CharNode n) {
_value = val;
_next = n;
}

2010 – -92 ב 3 / 20441 /ת 3
public char getValue() {
return _value;
}
public CharNode getNext() {
return _next;
}
public void setValue(char v) {
_value = v;
}
public void setNext(CharNode node) {
_next = node;
}
}

המחלקה CharList הנתונה להלן מייצגת מחרוזת תווים על ידי שימוש ברשימה מקושרת:

public class CharList {
private CharNode _head;
public CharList( ) {
_head = null;
}
}

התרגיל:

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

הוסיפו למחלקה CharList שיטה סטטית בוליאנית רקורסיבית שחתימתה היא:

public static boolean isTrans (CharList list1, CharList list2)

המקבלת כפרמטרים שתי רשימות list1 ו- list2 , המייצגות בהתאמה את מחרוזות התווים s ו- .t

השיטה צריכה להחזיר true אם t עברה- טרנספורמציה מהמחרוזת s, ו- false אחרת.

השיטה צריכה להיות רקורסיבית ללא

[Gil28]

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

[gshhar]

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

[sharonbn]

אולי תתחיל בזה שתגיד לנו איך אתה היית פותר את הבעיה עם לולאות רגילות

[gshhar]

אם למשל ה-string שאני שלחתי הוא aabccd ומה ההתקבל הוא aaabbcccd:

הייתי בודק שהאותיות מסודרות לפי הסדר שאני שלחתי ומופעיות לפחות כמספר הפעמים ב-string המקורי שאני שלחתי.

[sharonbn]

בוא תנסה לתאר את זה בצורה יותר מפורטת:

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

אני רוצה שתתאר בעברית ממש את האלגוריתם שלך:

אני קורא אות מהמחרוזת המקורית

אני קורא...

אני משווה...

אני סופר בצד את....

[gshhar]

אני רץ על המחרוזה המקורית:

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

[sharonbn]

בוא ננסה ככה -

ניקח את המקרה הכי פשוט -

המחרוזת המקרוית היא תו אחד בלבד - "a"

המחרוזת שהתקבלה היא "aaa"

תגיד לי איך אתה פותר את זה

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

[gshhar]

נתקעתי:

   public static bool isTrans(CharList list1, CharList list2)
    {
      if (list1._head.getValue() != list2._head.getValue())
      {
        return false;
      }
      else
      {
        return (isTrans(list1._head.getNext(), list2._head.getNext()));
      }
    }


    private static bool isTrans(CharNode list1, CharNode list2)
    {

    }

[sharonbn]

אתה ממש לא בכיוון (לא צריך את המתודה השניה שלך)

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

אני חוזר לשאלה המקורית שלי:

תנסה לתאר לי את הפתרון תוך שימוש בלולאות ולא רקורסיה.

המגבלות הן שאין לך שום משתנים שאתה שומר בצד (כמו מונה שתוכל לספור מופעים)

כמו כן הלולאות על שני הרשימות מתקדמות באופן עצמאי (לא לולאה בתוך לולאה)

הקיצר מה שאתה עושה זה שני מעברים מקבילים על שתי הרשימות, בכל פעם יש לך char node "נוכחי" מכל רשימה, ומותר רק להציץ ל next שלו. בלי מונים ובלי הצצות על איברים אחרים.

החוכמה היא לדעת מתי מקדמים את האיבר הנוכחי - לא תמיד הוא בכלל יתקדם (ככה תצליח לגלות כפילויות)

אתה צריך לחשוב על מעין מכונת מצבים: (תזכור שמותר להציץ על next)

"אם התו הנוכחי שווה לתו הבא אז ...."

וכולי.

לי עזר שהשארתי לסוף מקרי קצה (למשל הגעה לסוף הרשימה).

זה פתיר, תאמין לי, בצורה שתיארתי זה פתיר.

[gshhar]

אין אין אני יושב וחושב ופשוט לא הולך לי, אני חייב לתרגל את הרקורסיות האלו כי זה לא פשוט לי ואין לי מושג איך לגשת לשאלה הזאת.

[sharonbn]

טוב, הודעה כזו לא משאירה לי הרבה אפשרויות.

אתה מסרב להיענות להצעות עזרה שלי

מה אתה מציע? שאני אתן לך את הפתרון? ומה יקרה בשאלה הבאה?

לי נגמרו הרעיונות.

[gshhar]

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

[sharonbn]

מה שאני יכול להציע זה שתחזור לפוסט שלי עם השאלה ותתן נסיון רציני לענות

תנסה לענות בצורה יותר מפורטת משורה אחת כללית של "הייתי סופר ורואה מה כפול וזהו"

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

[tomeryh]

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

S1 S2 שני רשימות, S1 זאת המקורית

אלגוריתם:

1. אם S1 וS2 ריקות תחזיר TRUE אם אחת מהן ריקה תחזיר FALSE אחרת עבור ל2.

2. קח את רצף האותיות ההתחלתי הארוך ביותר בS1 כך שכל האותיות זהות ותספור את מספר המופעים.

3. קח את רצף המופעים הראשון של S2 כנ"ל. אם מדובר ברצפים של אותה אות ואם הרצף של S2 גדול שווה לרצף של S1 תקרא קריאה רקורסיבית עם שאר הרשימות

אחרת תחזיר FALSE