gshhar פורסם 2012 ביוני 24 Share פורסם 2012 ביוני 24 יש לי תרגיל ברקורסיה שאני לא מצליח אפילו לחשוב איך להתחיל ולפתור אותו, אני שם לב שיש לי בעיה עם סוגי תרגילים ברקורסיה והייתי שמח לעזרה בתרגיל הנ"ל: נתונה מחרוזת תוים 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 /ת 3public 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 אחרת. השיטה צריכה להיות רקורסיבית ללא קישור לתוכן שתף באתרים אחרים More sharing options...
Gil28 פורסם 2012 ביוני 24 Share פורסם 2012 ביוני 24 ראשית תחשוב כיצד אתה מפרק את הבעייה לחלקים קטנים יותר. קישור לתוכן שתף באתרים אחרים More sharing options...
gshhar פורסם 2012 ביוני 24 מחבר Share פורסם 2012 ביוני 24 אני חושב וחושב ולא מצליח, יש לי בקרוב מבחן ואני חייב לשפר את עניין הרקורסיה, פשוט לא הולך לי בתרגילים האלה. קישור לתוכן שתף באתרים אחרים More sharing options...
sharonbn פורסם 2012 ביוני 25 Share פורסם 2012 ביוני 25 אולי תתחיל בזה שתגיד לנו איך אתה היית פותר את הבעיה עם לולאות רגילות קישור לתוכן שתף באתרים אחרים More sharing options...
gshhar פורסם 2012 ביוני 25 מחבר Share פורסם 2012 ביוני 25 אם למשל ה-string שאני שלחתי הוא aabccd ומה ההתקבל הוא aaabbcccd:הייתי בודק שהאותיות מסודרות לפי הסדר שאני שלחתי ומופעיות לפחות כמספר הפעמים ב-string המקורי שאני שלחתי. קישור לתוכן שתף באתרים אחרים More sharing options...
sharonbn פורסם 2012 ביוני 25 Share פורסם 2012 ביוני 25 בוא תנסה לתאר את זה בצורה יותר מפורטת:אתה עובר בלולאה על המחרוזת המקורית או שהתקבלה או שתיהן? איך אתה מגלה שסדר האונתיות זהה ואיך אתה סופר מופעים כפוליםאני רוצה שתתאר בעברית ממש את האלגוריתם שלך:אני קורא אות מהמחרוזת המקוריתאני קורא...אני משווה...אני סופר בצד את.... קישור לתוכן שתף באתרים אחרים More sharing options...
gshhar פורסם 2012 ביוני 25 מחבר Share פורסם 2012 ביוני 25 אני רץ על המחרוזה המקורית:בודק כמה פעמים יש את התו הראשון ומשווה אל מול המחרוזת שהתקבלה - אם התו מופיע פחות פעמים או לא מופיע בכלל אני מחזיר false, אם הכל בסדר עובר לתו הבא וחוזר חלילה. קישור לתוכן שתף באתרים אחרים More sharing options...
sharonbn פורסם 2012 ביוני 25 Share פורסם 2012 ביוני 25 בוא ננסה ככה - ניקח את המקרה הכי פשוט -המחרוזת המקרוית היא תו אחד בלבד - "a"המחרוזת שהתקבלה היא "aaa"תגיד לי איך אתה פותר את זהכדי שנוכל לתרגם את הפתרון לרקורסיבי אתה צריך לתאר לי את המעבר תו אחרי תו קישור לתוכן שתף באתרים אחרים More sharing options...
gshhar פורסם 2012 ביוני 25 מחבר Share פורסם 2012 ביוני 25 נתקעתי: 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) { } קישור לתוכן שתף באתרים אחרים More sharing options...
sharonbn פורסם 2012 ביוני 26 Share פורסם 2012 ביוני 26 אתה ממש לא בכיוון (לא צריך את המתודה השניה שלך)על מנת להצליח להסביר לך טוב יותר, כתבתי לעצמי את הפתרון. זו באמת שאלה לא קלה אבל לא בלתי אפשרית.אני חוזר לשאלה המקורית שלי:תנסה לתאר לי את הפתרון תוך שימוש בלולאות ולא רקורסיה.המגבלות הן שאין לך שום משתנים שאתה שומר בצד (כמו מונה שתוכל לספור מופעים)כמו כן הלולאות על שני הרשימות מתקדמות באופן עצמאי (לא לולאה בתוך לולאה)הקיצר מה שאתה עושה זה שני מעברים מקבילים על שתי הרשימות, בכל פעם יש לך char node "נוכחי" מכל רשימה, ומותר רק להציץ ל next שלו. בלי מונים ובלי הצצות על איברים אחרים.החוכמה היא לדעת מתי מקדמים את האיבר הנוכחי - לא תמיד הוא בכלל יתקדם (ככה תצליח לגלות כפילויות)אתה צריך לחשוב על מעין מכונת מצבים: (תזכור שמותר להציץ על next)"אם התו הנוכחי שווה לתו הבא אז ...."וכולי.לי עזר שהשארתי לסוף מקרי קצה (למשל הגעה לסוף הרשימה).זה פתיר, תאמין לי, בצורה שתיארתי זה פתיר. קישור לתוכן שתף באתרים אחרים More sharing options...
gshhar פורסם 2012 ביוני 27 מחבר Share פורסם 2012 ביוני 27 אין אין אני יושב וחושב ופשוט לא הולך לי, אני חייב לתרגל את הרקורסיות האלו כי זה לא פשוט לי ואין לי מושג איך לגשת לשאלה הזאת. קישור לתוכן שתף באתרים אחרים More sharing options...
sharonbn פורסם 2012 ביוני 27 Share פורסם 2012 ביוני 27 טוב, הודעה כזו לא משאירה לי הרבה אפשרויות.אתה מסרב להיענות להצעות עזרה שלימה אתה מציע? שאני אתן לך את הפתרון? ומה יקרה בשאלה הבאה?לי נגמרו הרעיונות. קישור לתוכן שתף באתרים אחרים More sharing options...
gshhar פורסם 2012 ביוני 27 מחבר Share פורסם 2012 ביוני 27 לא מסרב פשוט לא מסתדר לי מה לעשות, אם אפשר אז הייית שמח לקבל לפחות התחלה של משהו שאוכל לפחות לנסות ושוב הרבה תודה על העזרה קישור לתוכן שתף באתרים אחרים More sharing options...
sharonbn פורסם 2012 ביוני 27 Share פורסם 2012 ביוני 27 מה שאני יכול להציע זה שתחזור לפוסט שלי עם השאלה ותתן נסיון רציני לענותתנסה לענות בצורה יותר מפורטת משורה אחת כללית של "הייתי סופר ורואה מה כפול וזהו"זה מצחיק אותי שהפוסטים שלי הרבה יותר ארוכים משלך... היה צריך להיות ההיפך... קישור לתוכן שתף באתרים אחרים More sharing options...
tomeryh פורסם 2012 ביוני 28 Share פורסם 2012 ביוני 28 הדרך לפתור שאלות רקורסיה זה לחלק לשני מקרים, אחד זה הבעייה הפשוטה והשאר לפתור ע"י קריאה רקורסיבית.S1 S2 שני רשימות, S1 זאת המקוריתאלגוריתם:1. אם S1 וS2 ריקות תחזיר TRUE אם אחת מהן ריקה תחזיר FALSE אחרת עבור ל2.2. קח את רצף האותיות ההתחלתי הארוך ביותר בS1 כך שכל האותיות זהות ותספור את מספר המופעים.3. קח את רצף המופעים הראשון של S2 כנ"ל. אם מדובר ברצפים של אותה אות ואם הרצף של S2 גדול שווה לרצף של S1 תקרא קריאה רקורסיבית עם שאר הרשימותאחרת תחזיר FALSE קישור לתוכן שתף באתרים אחרים More sharing options...
Recommended Posts
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.