רקורסיה

[supercalifragi]

רקורסיה

שלום אולי אפשר עזרה בשפת C צריך לכתוב פונקציה רקורסיבית שמקבלת מס' ומחזירה את האיבר בסדרת פיבונצ'י הקטן/שווה למספר שהתקבל למשל עבור המס' 7 יוחזר 5 תודה

 

[1ca1]

למה רקורסיה?

רקורסיה באופן כללי יקרה הרבה יותר מלולאה, ולכן כדאי לחסוך את זה, משהו בסגנון הקוד הבא:

function fibo(int num) { if (n==0) return 0; if (n==1) return 1; int current=0; int n1=1; int n2=1; while (n1+n2<=num) { current=n1+n2; n2=n1; n1=current; } return current;​

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

 

[HaifaMan]

למה רקורסיה?

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

 

[supercalifragi]

לא ממש הולך לי אם אפשר עזרה נוספת

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

 

[generala]

אז

אתה בונה שיטה/פונק' שבודקת האם המס' ייתכן בפיבו' ע"י ביצוע פיבו, במידה ולא אז בצע שנית פיבו רק הפעם תגיע הכי קרוב , זה יעלה הון תועפות אבל הנה לך פתרון רקורסיבי... אגב מימוש פיבו' לא צריך להיות יותר מ-5 שורות גג "עם תוספות" אם לקח לך יותר בהכרח הסתבכת...

 

[freak2100]

תרגיל קצת בעייתי לרקורסיה

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

 

[supercalifragi]

לא ממש מבין האמת

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

 

[freak2100]

טוב, ננסה לעשות את זה מסודר

הפונקציה מקבלת: fib_num_1 - מספר בסדרת פיבונאצי' fib_num_2 - המספר הבא בסדרת פיבונאצי' n - המספר שאנחנו מחפשים עבורו את המספר הכי קרוב בסדרת פיבונאצי' אם fib_num_2 > n, אז מחזירים את fib_num_1 אחרת, מחזירים את הפונקציה עם הפרמטרים הבאים:

the_function(fib_num_2, fib_num_1+fib_num_2, n)​

אחרי שיש לך פונקציה כזאת, ויש לך מספר n, בשביל למצוא את המספר הכי קרוב לn וכו' אתה פשוט עושה:

the_function(1, 1, n);​

כש1, 1 הם שני המספרים הראשונים בסדרת פיבונאצי', כמובן. אפשר לעשות פונקציית מעטפת כזאת שתקבל רק את n ותקרא לפונקציה הרקורסיבית.

 

[look4regev]

תשובה בשפת C

int fib(int n, int fib_a1, int fib_a2) { if(n<=fib_a2) return fib_a2; /*else*/ return fib(n,fib_a2,fib_a1+fib_a2); } /*function call (n is known): answer=fib(n,0,1);*/