05-03-2015, 12:55
|
|
|
חבר מתאריך: 18.07.05
הודעות: 3,884
|
|
עזרה בניתוח יעילות פונקציה רקורסיבית
היי,
נתונה הבעיה הבאה:
נתון סכום אותו יש לפרוט למספר קטן ככל האפשר של מטבעות.
הפונקציה מקבלת מערך Xשל מטבעות ,את הגודל שלו n (מערך ממוין בסדר עולה)
ומקבל סכום N אותו יש לפרוט.
תנאי העצירה הם אם הסכום שווה 0 או 1.
בכל קריאה רקורסיבית מתבצעת בדיקה האם האיבר האחרון במערך (המטבע הגדול ביותר )גדול מהסכום, אם כן אז נבצע קריאה רקורסיבית על אותו הסכום ונקטין את גודל המערך ב-1.
אחרת נחזיר את המינימום מבין 2 קריאות- האחת לוקחת את המטבע הגדול ביותר ומקטינה את הסכום, השניה משאירה את הסכום כשהיה ומקטינה את גודל המערך ב-1 (כלומר או שבחרנו את המטבע הנוכחי או שלא).
השאלה שלי היא מה יעילות האלגוריתם, ואשמח גם להסבר בבקשה.
תודה מראש
|