מספר הדרכים להחזיר עודף שערכו n.

[aaaaa139]

מספר הדרכים להחזיר עודף שערכו n.

חשבתי על הפתרון הבא..אבל נאמר לי שהוא לא פולינומיאלי.
לא מבין מה לא פולינומיאלי פה..זה אפילו פולינומיאלי לינארי...אבל כנראה בכל זאת אני טועה..

בשאלה אני צריך לחשב את מספר הדרכים להחזיר עודף בגודל n כאשר המטבעות שעומדים לרשותי הם מטבעות שערכיהם: 1,2,5,10 ומכל מטבע יש כמות אינסופית.
כמו כן, הסדר משנה. כלומר עודף 1,1,2 שונה עודף 2,1,1.


הגישה שניסיתי זה תכנות דינאמי .
הגדרתי פונקציה F = מספר האפשרויות שבעזרתן ניתן להחזיר עודף n.

די ברור שאפשר להגדיר את (F(n ע"H הנוסחה הרקורסיבית הבאה:
zz F = F(n-1) + F(n-2) + F(n-5) + F(n-10) zz
הקטע שאני צריך לחשב ידנית את (F(1),F(2),F(3),...,F(10.
ואז בלולאה
(for i in range (11,n+1
[F=F[i-1]+F[i-2]+F[i-5]+F[i-10
ומחוץ ללולאה אחזיר את [F[n
סה"כ זמן זה O
סה"כ מקום זה O

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

 

[עריסטו]

אז ככה

לגבי הזמן - אולי הבעיה היא שהחישוב שלך לא פולינומיאלי בגודל הקלט. שים לב שגודל הקלט הוא log ולא n. צריך לברר אם מה שדורשים ממך הוא אלגוריתם פולינומיאלי ב-n או פולינומיאלי בגודל הקלט.
לגבי חישוב הערכים הראשונים - אפשר לחשב אותם על ידי אותה רקורסיה:
F=F(n-1)+F(n-2)+F(n-5)+F(n-10)
כאשר zzz F(0)=1 zzz
ו - F=0 עבור n שלילי.

 

[aaaaa139]

בקשר לתשובה שלך בנוגע לזמן

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

האמת שחשוב לי להבין את זה טוב כיוון שנראה לי שלמשל אלגוריתם פולינומיאלי ל-subset sum או לבעיות NP שלמות נוספות, לא גורר שP=NP, כנראה בדיוק בגלל אותו עניין שעליו אי שואל

 

[ןן גיל ןן]

ואם פולינומיאלי בגודל הקלט

כלומר פולינומיאלי ב-log n, אז אפשר בעזרת מטריצות:

הוקטור (F(n-9),F(n-8),...,F(n מתקבל מהוקטור (F(n-10),F(n-9),...,F(n-1 ע"י הכפלה במטריצה קבועה. לכן מספיק לחשב את וקטור 10 הערכים הראשונים ולהכפיל אותו בחזקת n של המטריצה הקבועה (מגודל 10X10). ויש אלגוריתמים לחישוב חזקה של מטריצה בזמן לוגריתמי.