היי

[fr!$h]

היי

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

 

[עידית_]

פיבונאצ´י

הנה אפשרות לדוגמה (יש כל מיני דרכים לעשות את זה). מקווה שאין לי טעות... void fib( n, m ) { int k = n+m; printf("%d, ", k); fib( m, k); } int main() { printf("0, 1, "); fib(0, 1); }

 

[fr!$h]

זאת גם דרך...

אבל אני זוכר שראיתי פעם עוד דרך.

 

[@זהר@]

לא מצאתי בתוכנית שכתבת

תנאי עצירה. התוכנית תמשיך לקרוא לעצמה שוב ושוב ושוב עד שהמחסנית של התוכנית תגמר (בדומה ללולאה אין סופית).

 

[ihovav]

נו, ברור !!!

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

 

[@זהר@]

1. אני לא בן!

2. פשוט הערתי מה לא בסדר בתוכנית שהיא כתבה. 3. כשאנשים לומדים תכנות בכלל ורקורסיות בפרט, מלמדים אותם בעיקר תכניקה ומעט מאוד יעילות לצערי. אחת הדרכים ללמוד רקורסיות היא לעשות את סדרת פיבונאצ´י שקודם הם עשו אותה עם לולאה עם רקורסיה. 4. לשמחתי הרבה אני וסדרת פיבונאצ´י נפרדנו לפני די הרבה שנים.

 

[@זהר@]

ועוד נקודה

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

 

[ihovav]

את צודקת, אבל...

לא ביקשו כאן פונקציה שמביאה את הסדרה עד מספר מסויים - אלא פונקציה שמביאה את הסידרה בכללי אמנם - הפונקציה תיכנס ל OVERFLOW מהר מאוד - אבל זה כבר לא מעניננו - התשובה ניתנה במלואה

 

[עידית_]

אתה צודק. יחד עם זאת, שימו לב

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

 

[עידית_]

נכון, סתם לא טרחתי...

הוא ביקש פונקציה שמדפיסה את הסדרה, אז זה מה שנתתי... הסדרה היא אינסופית כמובן.

 

[באפט]

אין דרכים שונות..

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

 

[עידית_]

יש דרכים שונות

לא אמרתי שיש הגדרות שונות לפונקציה... אמרתי שיש דרכים שונות לממש אותה.

 

[באפט]

fair enough ../images/Emo13.gif

 

[fr!$h]

נזכרתי!!!

אבל.. יש לי בעיה אני חדש בC++ ו... אני לא מבין מה הבעיה ב

#include<iostream.h> int fibo(int n){ if ((n==1)||(n==2)) return n; return fibo(n-1)+fibo(n-2); }; void main(void){ cout<<fibo(5); };​

הפונקציה מחזירה את המספר בסדרת הפיבונצי במקום n. לדוגמא: התוכנית הזאת תחזיר 8, כי המספר שמונה הוא החמישי בסדרת פיבונצי (1,2,3,5,8)

 

[עידית_]

זה בסדר גמור. למה אתה חושב שיש

בעיה? אגב, בסוף בלוק של פונקציה אין צורך בנקודה-פסיק (לא שזה משנה משהו).

 

[hazgul]

זה דווקא כן

וזו הבעיה.

 

[philips]

ה נקודה פסיקה הרגה את החתול

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

 

[עידית_]

פיליפס, אני בטוחה שאני לא מחדשת לך

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

while (whatever stop-condition) { k = n+m print k n=m m=k } אבל גם לי מנקר במוח שלימדו אותנו פעם דרך ישירה יותר עם איזו נוסחה...

 

[@זהר@]

את עידית

שהיתה עידית ב IOL זכרונו לברכה ?

 

[עידית_]

כנראה שכן... ../images/Emo82.gif

אמנם היתה שם עוד עידית, אבל כנראה שאת מתכוונת אלי. הייתי שם בפורום תכנות די הרבה (והאמת שאני עדיין שם מידי פעם...מה לעשות, קשה להתנתק...)