עזרה בשפת C

[הלני]

שלום ,

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

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

howManyCoins(int*coins, int sum, int size

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

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

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

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

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

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

[iwantdell]

מה ההגיון ?

[הלני]

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

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

[iwantdell]

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

[הלני]

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

[Access Denied]

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

[iwantdell]

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

[הלני]

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

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

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

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

[iwantdell]

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

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

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

[iwantdell]

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

[Access Denied]

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

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

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

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

[iwantdell]

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

[Access Denied]

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

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

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

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

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

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