שלום ,

נתקלתי בשאלה ( מתחילה בתחום התכנות)

לא מצאתי כאן אפשרות להעלות תמונה אז אני אתאר באופן כללי:

howManyCoins(int*coins, int sum, int size

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

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

חובה להשתמש בbacktracking , יש להשתמש בלולאות רק לצורך קבלת הקלט.

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

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

המון תודה למי שיצליח

מה ההגיון ?

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

אין לי מושג איך רושמים את זה בקוד.

יש לך ניסיון כלשהו עם כתיבת קוד רקורסיבי / BT ?

bt ? כמו שאמרתי אני ממש "בחיתולים" , אתה יודע לכתוב לזה קוד?

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

כמובן רשום שהמערך ממוין. (ואם לא היה אפשר לעשות זאת). הלני, אפשר לעשות הכל, השאלה האם לעשות פשוט לעשות את השיעורים בשביל, או למשל שתכתבי רעיונוית איך זה (בפירוט) ונסתכל על איך לממש.

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

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

אם מישהו יכול להראות לי קוד , יופי ואם לא, אז לא.

לא הצלחתי להבין מה פשר התחקור.

זה נראה לי כמו פתרון שיעבוד על כל קלט ?

def howManyCoins(coins, sum, index=0, amount=0, howmany=0):
  if index >= len(coins):
    return -1
  coin = coins[index]  
  if amount + coin > sum:
    return -1
  if amount + coin == sum:
    return howmany + 1
  optiona = howManyCoins(coins, sum, index, amount + coin, howmany + 1)
  optionb = howManyCoins(coins, sum, index+1, amount, howmany)
  if optiona == -1:
    return optionb
  if optionb == -1:
    return optiona
  return optiona if optiona < optionb else optionb

והלני, אין לי כח להתווכח, אבל הרעיון שכתבת די לא קשור לכלום..

נערך 2015 במאי 710 שנים על-ידי iwantdell

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

אם המערך לא ממויין זה לא יהיה backtracking אלא רקורסיה רגילה.

היא ביקשה מימוש שהוא רקורסיה עם backtracking אז חשוב לוודא שהקלט לרקורסיה מוכן בצורה מתאימה

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

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

נערך 2015 במאי 910 שנים על-ידי Access Denied

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

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

אם ברקורסיה רגילה אתה בודק את כל עץ האפשרויות, ב-backtracking אתה עוצר בצמתים שאין טעם להמשיך לבדוק מהם הלאה (גם אם יש להם בנים)

מאין - "גיזום ענפים" שמייצגים מצבים לא אפשריים לבעיה.

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

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

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