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

אשכול: רקורסיה

  1. #1
    הסמל האישי שלYair2597 משתמש רשום משתמש מתחיל

    פרטי משתמש

    ברירת מחדל רקורסיה

    חתימת השיטה : public static boolean findSum(int mat [ ] [ ] , int sum , int path [ ] [ ])l

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

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

    מותר להשתמש ב overloading .

    תודה מראש לפותרים .
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: jpg שאלה 2.jpg‏ (133.3 ק"ב , 20 צפיות) שאלה 2- 50 נקודות (להגשה) נתון מערך דו-ממדי ריבועי המכיל מספרים שלמים חיוביים בלבד. נגדיר מסלול (path) במערך כאוסף של תאים סמוכים. תאים סמוכים יכולים להיות שכנים מלמעלה, מלמטה, מימין ומשמאל. לא באלכסון. כתבו שיטה סטטית בוליאנית רקורסיבית, המקבלת כפרמטרים מערך דו-ממדי mat המכיל מספרים שלמים חיוביים ממש (גדולים מאפס), ומספר וsur שלם חיובי כלשהו. כמו כן, השיטה מקבלת כפרמטר מערך דו ממדי path באותו גודל של Tlat. השיטה צריכה לבדוק אם קיים מסלול במערך שסכום ערכיו הוא um$. אם קיים מסלול כזה השיטה תחזיר true, אחרת יוחזר הערך false. המערך path משמש לסימון המסלול שסכומו בsum. בתחילה, כשהמערך path מועבר כפרמטר, כל תאיו מכילים את הערך 0. בסיום השיטה, אם יש מסלול במערך mat שסכומו sum, המערך path יכיל 1 בתאים שמשתתפים במסלול, ו-0 בכל שאר התאים. אם אין מסלול כזה במערך mat, המערך path צריך להכיל בכל תאיו את הערך 0, אם קיים יותר ממסלול אחד שסכומו path, המערך path יכיל את אחד המסלולים שסכומו sum (באופן שרירותי). לדוגמא, בהינתן המערך mat הבא:41 13 142ד 24 ו 22| 2 | 15 | 10 | 5463 | 22 | 2 | 43והסכום 4, השיטה תחזיר true והמערך path יכול להיות אחד משלושת המערכים הבאים: () [1| 0 | 0 | 0 הסוסן321000 | 0 | 0 | 01|1| 0 | 0 | 0 |1| 0 | 0 | 0 | 0 | 0 | 032100 | 0 | 0 | 0 |0000 | 0 | 0 | 0 | 0010 | 6 |

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

    פרטי משתמש

    ברירת מחדל

    ראשית, הגדרתי פונקציה שנקראת findSumStartAt שבהינתן זוג אינדקסים התחלתיים (i, j) בודקת אם קיים מסלול שמתחיל באינדקסים אלה ומסתכם ל-sum ומסמנת אותו על המטריצה path. בעצם זו הבעיה המקורית מוקטנת למצב שצריך שהמסלול צריך להתחיל במקום מסויים. הפונקציה פועלת רקורסיבית וכל העקרון של הסימון על המטריצה path מתבצע באופן סטנדרטי ל-backtracking. זאת אומרת, ראשית היא מסמנת את התא הנוכחי ב-path שעליו היא נמצאת כרגע ב-1 - אם נמצא מסלול אז מצויין וזה לא ישתנה, אחרת, כלומר לא נמצא מסלול שמתחיל בתא הנוכחי, היא מנקה את הנוכחי ב-path על ידי סימון חזרה עם 0.

    המימוש שלה:
    findSumStartAt.PNG


    לאחר מכן הגדרתי את הפונקציה findSumAuxiliary שבעצם מנסה את כל ההתחלות האפשריות למסלולים. כלומר מנסה להתחיל בכל (i, j) בתחומי המטריצה mat. זה מתבצע בכך שהיא קוראת ל-findSumStartAt עם האינדקסים (i, j) - אם זה הצליח אז יש מסלול שמתחיל ב-(i, j) והיא מחזירה אמת. אם לא, היא מנסה לחפש מסלול שמתחיל תא אחד ימינה או תא אחד למטה באמצעות קריאות רקורסיביות. בנוסף, היא משתמשת במטריצה דו-מימדית בגודל של mat בשם tries שמציינת באילו אינדקסים כבר נוסה נסיון להתחיל למצוא מסלול. מבחינה אלגוריתמית זה לא משהו שחייב לעשות, אבל זה מייעל מאוד את הפתרון ומונע קריאות רקורסיביות מיותרות.

    המימוש שלה:
    findSumAux.PNG


    ולבסוף הגדרתי את findSum שכל מה שהיא עושה זה לייצר מערך tries עזר מאופס לצורך findSumAuxiliary וקוראת ל-findSumAuxiliary להתחיל לנסות למצוא מסלולים באינדקסים (0, 0).

    המימוש שלה:
    findSum.PNG


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


    הנה הקוד המלא עם דוגמת הרצה.
    נערך לאחרונה על ידי Yes, 25-05-2019 בשעה 12:15

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

Users Browsing this Thread

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

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

הרשאות

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

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