שפת ab

[הנהלת המפרומים]

שפת ab

יש שפה שמורכבת רק מהאותיות a ו-b כמה מילים אפשר להרכיב מרצף אותיות באורך n, אשר אין בהן שתי אותיות a סמוכות?

 

[MaD PenGuiN]

...

יכולים להיות מקסימום N/2 פעמים A. לפי מספר הaים: 0: אפשרות אחת 1: n אפשרויות 2: n*(n-1) 3: n*(n-1)*(n-2) . . . n: n(n-1)(n-2)...*1 סכום האפשרויות 1+n+n(n-1)+n(n-1)(n-2)+...+n אני יכול להמשיך אבל זה די מסובך! בטח יש פתרון יותר קל...

 

[איייייל]

פתרון

נחפש נוסחה רקורסיבית: נסמן את מספר האפשרויות ב f. אם המלה מתחילה ב a, אז מספר האפשרויות הוא f(n-2) אם המלה מתחילה ב b, אז מספר האפשרויות הוא f(n-1) תנאי התחלה: f(0)=1, f(1)=2 כלומר הפתרון הוא סדרת פיבונצ'י שמתחילה מהאיבר השלישי (,2,3,5,8,13,...)