תרגיל בC

[פטרובר]

תרגיל בC

כתוב פונקציה המקבלת מספר טבעי n ומדפיסה את האיבר ה n בסדרת פיבונצ'י מישהו יכול לתת לי רמז?

 

[גיל14]

איך היית עושה את זה על נייר?

 

[פטרובר]

גם את זה אני לא יודע

 

[מתכNET]

איך מוגדרת סדרת פיבונאצ'י אתה

יודע?

 

[פטרובר]

כן

 

[evgi91]

למדת כבר רקורסיה ?

כך את ההגדרה של סדרת פיבנאצ'י fib(0) =1 fib(1) =1 fib = fib(n-1) + fib(n-2) תפתח את זה רמז, השתמש ברקורסיה בהצלחה

 

[פטרובר]

עם לולאה זה בלתי אפשרי?

 

[igalln007]

בטח שאפשרי. אפילו עדיף

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

 

[neko]

בעעע... לא חבל על הCPU?

 

[freak2100]

כשזה לצרכים לימודיים - לא...

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

 

[neko]

נכון שזה מתאים לרקורסיה,

אבל מכיוון שרקורסיה בד"כ לומדים אחרי לולאות, סביר שהוא היה אומר שאסור לו לולאה אם זה היה תרגיל ברקורסיה

 

[freak2100]

יש לפחות 5 דרכים שונות לעשות את זה

בלי רקורסיה אפשר לרוץ בלולאה מ2 עד n ולשמור שני משתנים - מספר פיבונאצי' באיטרציה הiית והמספר הקודם (ששווה למספר פיבונאצי' באיטרציה הi-1, כמובן)

 

[גיל14]

אגב, שימו לב ש

זה רץ במהירות ליניארית (בהנחה שחיבור כל שני מספרים הוא פעולה אטומית), בעוד שהדרך הרקורסיבית רצה בזמן אקספוננציאלי (ספציפית עם מעריך phi≈1.618).

 

[freak2100]

כמובן...

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

lim(a(n+1)/a) = phi​

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

בכל מקרה, אלה כמה אלגוריתמים שחשבתי עליהם לאחרונה

זה התחיל מזה שמישהו סיפר לי שהוא שאל אנשים את השאלה הזאת בראיון עבודה והרבה לא ידעו :-O