שאלה מתוך תירגול 3

מנהל: TA_Isana

שלח תגובה
betite85
הודעות: 14
הצטרף: 20:05 09/11/2009

שאלה מתוך תירגול 3

שליחה על ידי betite85 » 16:03 21/04/2010

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

הנוסחב נראת כך:
t(n) = t(n-1 ) + t(n-2) +1
ומה שעשינו בתירגול היה לחסום אותה מלמעלה ומלמטה.

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: שאלה מתוך תירגול 3

שליחה על ידי TA_Yoni » 19:25 21/04/2010

כשיש לך נוסחת נסיגה שמגדירה את האיבר ה - n באמצעות יותר מאיבר אחד ( כמו בדוגמה שנתנו בתרגול - הגדרנו את האיבר ה n בעזרת האיבר ה n-1 ובעזרת האיבר ה n-2 ) .
המתרגל יוני

eliranyo
הודעות: 25
הצטרף: 17:24 02/12/2009

Re: שאלה מתוך תירגול 3

שליחה על ידי eliranyo » 22:55 21/04/2010

אשמח להבין למה מוסיפים אחד והנוסחת נסיגה היא לא פשוט:
t(n) = t(n-1 ) + t(n-2)

TA_Lena
הודעות: 141
הצטרף: 14:46 22/04/2009

Re: שאלה מתוך תירגול 3

שליחה על ידי TA_Lena » 11:50 22/04/2010

באופן כללי, T(n) מייצג את כמות הפעולות שהקוד מבצע עבור קלט בגודל n. עבור קלט בגודל n, יש לנו שתי קריאות רקורסיביות עם קלט קטן יותר ועוד אנו מוסיפים 1 כ"תשלום" על הפעולות הנוספות שמתבצעות, כמו הסכימה וה - if.

שלח תגובה

חזור אל “- מבני נתונים 2010”