מציג תוצאות 1 עד 9 מתוך 9

אשכול: שיטת פתרון רקורסיה ו-BackTracking

  1. #1
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל שיטת פתרון רקורסיה ו-BackTracking

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

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

    חשבתי אולי תוכלו להמליץ לי, איך לגשת לפתרון תרגילי רקורסיה ו-BackTracking בצורה הטובה ביותר.

    תודה רבה.

    נ.ב. - ואם להיות קונקרטי יותר, צירפתי שאלת רקורסיה ממבחן מסכם בקורס מבוא למדעי המחשב, שלדוגמה לא ידעתי איך לגשת אליו וכו'...
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: png תרגיל אינטרו.png‏ (36.1 ק"ב , 33 צפיות) 4. ערך ברשימה יקרא "עמק" אם הוא לא יותר גדול מהערכים בתאים השכנים (לתא הראשון והאחרון ברשימה יש שכן אחד בלבד, לכל יתר התאים יש שני שכנים). כתבו פונקציה (find _valley (lst שמקבלת רשימה לא ריקה של מספרים עם בדיוק עמק אחד, ומחזירה את המיקום (האינדקס) של העמק. דגשים והנחות על הקלט: הפתרון חייב להיות רקורסיבי, והוא צריך להיות יעיל ככל האפשר כדי לקבל את מלוא הנקודות. ניתן להניח שהקלט תקין ושכל שני תאים סמוכים ברשימה מכילים ערכים שונים. מותר כמובן לעשות שימוש בפונקציות עזר בפתרון (כמו בכל שאלה במבחן). קריאה לפונקציה: ([10 ,9 ,1 ,2 ,3 ,4 ,5 ,7]) find _valley תחזיר את הערך 4 (כיוון שהעמק, 2, נמצא באינדקס 4 ברשימה).
    נערך לאחרונה על ידי Helpme, 26-01-2019 בשעה 14:09


  2. #2
    הסמל האישי שלאריאל מנהל כללי חבר Emath בכיר

    פרטי משתמש

    ברירת מחדל

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

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

    וכמובן להתחיל מהאיבר השני עד אחד לפני האחרון ולעצור ברגע שמוצאים עמק ראשון או כשאנחנו בסוף.
    אהבתי Helpme אהב \ אהבו את התגובה
     
    מנהל כללי - www.Emath.co.il
    לפניות : [email protected]

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

  3. #3
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

    בשאלה שנתת, אין צורך ב-Backtracking, כי כמו שהיית פותר את זה בצורה ידנית - אפשר לעבור בזה אחר זה אחר האיברים ולזהות היכן העמק. כלומר, קיים פתרון ב-$O(N)$, כאשר $N$ מספר האיברים במערך.
    קל היה לפתור את זה בצורת לולאה, ולכן נראה לי שיהיה קל להעביר את הרקורסיה לצורה שיותר דומה ללולאה, כלומר לשמר מצב. בשביל זה צריך לקרוא לפונקצית מעטפת בדרך כלל. הנה למשל פתרון כזה ב-++C של רקורסית זנב(כאן אין שימוש בפונקצית מעטפת בזכות זה שאפשר לתת ערך ברירת מחדל ב-++C, אבל ב-C למשל זה לא היה אפשרי):
    עריכה: עכשיו אני רואה שהקלט הוא רשימה, ולא מערך. זה דורש שינוי קל מאוד לפתרון שרשמתי. זה אפילו יותר טוב כי זה ידרוש ממך לחשוב לבד איזה שינוי נדרש לפתרון הנ"ל כדי להתאים אותו לקלט כזה.
    נערך לאחרונה על ידי Yes, 26-01-2019 בשעה 21:33
    אהבתי Helpme אהב \ אהבו את התגובה
     

  4. #4
    הסמל האישי שלאריאל מנהל כללי חבר Emath בכיר

    פרטי משתמש

    ברירת מחדל

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

    אתה משווה פעמיים את אותם איברים (לדוג' 4 עם 5 ואז 5 עם 4)
    אהבתי שיטת פתרון רקורסיה ו-BackTrackingYes, Helpme אהב \ אהבו את התגובה
     
    מנהל כללי - www.Emath.co.il
    לפניות : [email protected]

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

  5. #5
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

  6. #6
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

    זה הולך ומתברר לי עם ענייני הרקורסיה, אני צריך לתרגל.
    אני אתן משהו מוכוון BackTracking:

    לכתוב פונקציה רקורסיבית שמקבלת שתי מחרוזת a1 ו-a2, ועושה Merge:
    כלומר אם a1 זה המחרוזת ab
    ו-a2 זה המחרוזת 12
    אז הרקורסיה תדפיס:
    ab12
    a12b
    12ab
    1a2b
    1ab2
    a1b2

    אגב, אני בפיית'ון אבל מה שנוח לכם...


  7. #7
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    כלומר מדפיסה את כל הפרמוטציות האפשריות או שחייב להישמר הסדר המקורי של המחרוזות כמו בדוגמאות שרשמת? למשל, האם "21ab" הוא פלט חוקי?

  8. #8
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    ציטוט פורסם במקור על ידי Yes צפה בהודעה
    כלומר מדפיסה את כל הפרמוטציות האפשריות או שחייב להישמר הסדר המקורי של המחרוזות כמו בדוגמאות שרשמת? למשל, האם "21ab" הוא פלט חוקי?
    חייב להישמר הסדר המקורי. מה שכתבת למשל אינו חוקי.
    חשוב לי שתתאר לי את צורת החשיבה שבה אתה ניגש לפתרון הבעיה, שלב-שלב.
    כדי שאני אדע איך לחשוב.
    תודה רבה!


  9. #9
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

    אני ניגשתי לשאלה שלך ככה: אני אסמן ב-$s1$ וב-$s2$ את המחרוזות. מחרוזת פלט חוקית היא בעצם לדחוף את התווים של $s1$ בזה אחר זה בין התווים של $s2$. לשם המחשה, נניח ש-$s2=\text{"abc"}$, אז הרווחים של $s2$ שאני מציין הם הכוכביות ב-$\text{"*a*b*c*"}$ (על אותו משקל של כדורים ותאים בקומבינטוריקה, אם זה עוזר לך). ואז החשיבה הרקורסיבית היא כזו: נניח שהכנסתי את $i$ התווים הראשונים של $s1$ ל-$s2$ והכנסתי בפעם האחרונה לאינדקס $j$, אז התו הבא שאני מכניס צריך להיכנס במקום ה-$(j+1)$ והלאה, כלומר זה בדיוק כמו הקריאה הראשונה כשאנחנו מתחילים מהתו ה-$j+1$ במקום התו ה-$0$ עם יתר התווים של $s1$ שעוד לא הכנסנו. ומתי אנחנו מדפיסים, או במילים אחרות, מה תנאי העצירה? כשהכנסו את כל התווים של $s1$.

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

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


    הערה: שים לב שזה לא בדיוק backtracking, כי הפתרון לא בודק אם הגענו לאיזשהו מצב ואז אם הוא לא מתאים אז פוסל אותו וממשיך עם אחרים. זה פשוט לא משהו שנדרש בתרגיל הזה.
    נערך לאחרונה על ידי Yes, 30-01-2019 בשעה 01:37
    אהבתי אריאל אהב \ אהבו את התגובה
     

מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 6

הרשאות

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

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו