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

[sharonbn]

הפתרון שלך דורש לולאות (למצוא את הרצף הארוך ביותר.... איך אפשר בלי לולאה?) וכמו כן ספירות דורשות לולאה

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

בלי רצפים בלי ספירות

לפי דעתי זה מה שהתכוון המשורר

[karpatzio]

הדרך לפתור רקורסייה (ע"פ סיקסיק) זה לבצע את העבודה שלך, ולסמוך על החבר שלך שיודע להמשיך משם, וגם לחבר הזה יש חבר שימשיך מאיפה שהוא הפסיק.

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

2) אם כן, אני אתן לחבר שלי להמשיך מהתו הבא במחרוזת השנייה.

3) אם לא, אז אבדוק אם התו במחרוזת השנייה זהה לתו הבא במחרוזת 1, במידה וכן אתן לחבר שלי להמשיך את הבדיקה מהתו הבא במחרוזת 1

4) אם גם זה לא, אז המחרוזת לא שוכפלה.

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

[karpatzio]

הפתרון שלך דורש לולאות (למצוא את הרצף הארוך ביותר.... איך אפשר בלי לולאה?) וכמו כן ספירות דורשות לולאה

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

בלי רצפים בלי ספירות

לפי דעתי זה מה שהתכוון המשורר

אפשר לממש לולאות ע"י רקורסייה. אפשר למשל להוסיף פרמטר לפונקצייה, או להשתמש במשתנים סטטיים כמונים. זה מאוד לא יעיל, מאוד מכוער אבל זה תקין.

[tomeryh]

הפתרון שלך דורש לולאות (למצוא את הרצף הארוך ביותר.... איך אפשר בלי לולאה?) וכמו כן ספירות דורשות לולאה

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

בלי רצפים בלי ספירות

לפי דעתי זה מה שהתכוון המשורר

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

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

KARPATZIO לא הבנתי את הפתרון שלך... אני לא בטוח שהוא עובד

[karpatzio]

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

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

2

[tomeryh]

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

האלגוריתם שלך לא נכון ואני לא מדבר על תנאי סיום.

האלגו' שלך כל עוד התווים שוים מקדם רק את מחרוזת 2. ומה קורה אם מחרוזה אחת מתחילה ביותר משני תווים זהים?

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

[karpatzio]

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

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

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

בוא נסתכל על זה ככה:

אילו מצבים אנו יכולים לבדוק? בוא נשתמש רגע בסינטקס C

*s1 == *s2
*(s1+1) == *s2
*s1 == *(s2+1)
*(s1+1) == *(s2+1)

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

[tomeryh]

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

עדיין לא הבנתי איך זה אפשרי.

אתה יכול לכתוב את האלגו' מחדש כי מקודם זה לא היה ברור

[karpatzio]

שלחתי לך מימוש די צולע של האלגוריתם.

[sharonbn]

karpatzio צודק במאה אחוז. זה כיף גדול בשבילי לראות שיש עוד בן אדם אחד שעלה על הפתרון המדויק שאני הגעתי אליו ואכן הפתרון שלו הוא במדויק הפתרון שהצעתי לפותח השירשור.

tomeryh

לא רק שהפתרון שלנו הוא אפשרי, אלא הוא גם הכי יעיל ו(לפי דעתי) הכי אלגנטי = מכיוון שהוא לא דורש שום משתנה בקרה, שום תוספת ארגומנט לפונקציה ושום לולאה. אני מימשתי את הפתרון בג'אווה והוא עובד יפה מאד.

[Gil28]

אין שום בעייה עם לולאה בתוך רקורסיה, זה לא נוגד שום רעיון.

[karpatzio]

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

[sharonbn]

אין שום בעייה עם לולאה בתוך רקורסיה, זה לא נוגד שום רעיון.

נו באמת...

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

[Gil28]

מה הקשר? יש הבדל בין לפתור את התרגיל בלולאות לבין להשתמש בפונקציית עזר שהיא בתורה, משתמשת בלולאה.

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

[karpatzio]

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