סולמות

[היחיד במינו]

סולמות

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

 

[נ פ ו ל י א ו ן]

../images/Emo62.gifפתרון

התשובה היא האיבר ה N בסדרת פיבונאצ'י שמתחילה ב 1,2. (עבור מי שלא יודע: סידרת פיבונאצ'י היא סידרה שבה כל איבר שווה לסכום שני קודמיו. הסדרה המקורית מתחילה ב 1,1 אבל זו כאן מתחילה בהזזה אחת קדימה: 1,2,3,5,8,13,21,34,55,89...) באופן רקורסיבי: (Fib(N) = Fib(N-1) + Fib(N-2