Rekurencyjna funkcja na słowach Wcale nie Makuchowski: Ile razy w X(100) występuje słowo ABBA? X = (A, B, BA, BAB, BABBA, BABBABAB, ...)

Blee: Nie wiem czemu, ale trochę 'zalatuje' mi tym 'telewizyjnym' bądź jakimś konkursem/zadaniem na dodatkową ocenę. Zanim podam pomysł na rozwiązanie (nie jest to skomplikowane), chciałbym się dowiedzieć jaka jest geneza tego zadania. Oraz czy BABBABABBABBA czyli 7'my wyraz posiada w sobie dwa słowa ABBA czy trzy słowa ABBA (dwa słowa ABBA 'nachodzą' na siebie) oczywiście − odpowiedź na to pytanie powoduje, że i wynik (ale samo rozumowanie już nie do końca) będzie zupełnie inny

Wcale nie Makuchowski: Te zadanie jest na dodatkowe punkty na uczelni. Nie wiem, czy wyrazy ABBA mogą się zazębiać. W przypadku nie zazębiana się, w obliczeniach wyszło mi, że ilością wyrazów ABBA jest 96ty numer ciągu fibonacciego. W przypadku zazębiania się nie mogłem znaleźć sensownego wyniku.

Blee: Dokładnie tak będzie .... 100'tny wyraz będzie miał tyle słów ABBA w sobie tyle ile wynosi 96'ta liczba ciągu Fibonacciego. Jeżeli zazębianie wchodzi w grę czyli BABBABABBABBA traktujemy jako 3 wyrazy to należy zauważyć, że: tak jak i w poprzednim przypadku: liczba słów ABBA będzie równa sumie występowań w dwóch poprzednich + 1 (lub 0) zauważ, że 'dodatkowe' ABBA otrzymamy w X(n) tylko gdy X(n−1) kończy się ba AB (bo każdy X(j) od j>2 zaczyna się na BA) natomiast X(j) kończy się na AB gdy j = 2k (dla k>1) więc mamy: taką tabelkę 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 0 0 0 0 1 1 2 3 5 8 13 21 34 55 ... 0 0 0 0 0 0 1 1 2 2 3 3 4 4 ... gdzie mamy kolejno: X(i) liczba Fibonacciego (odpowiednio przesunięta) liczba 'dodatkowych' ABBA* <−−−− to nie jest ostateczna liczba dodatkowych ABBA musisz teraz obliczyć SUMĘ trzeciego ciągu od X(1) do X(100) i tą wartość dodać do 96'tej liczby Fibonacciego.

makuchowski: Słowo Abba występuje w X 300 razy

Pytający: Blee, trochę pogmatwałeś na koniec. Sumowanie tego trzeciego ciągu nie da Ci poprawnej liczby dodatkowych ABBA. Sprawdź chociażby dla i=8. Tu w 3 lnijice jest ostateczna liczba "dodatkowych" ABBA: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 0 0 0 0 1 1 2 3 5 8 13 21 34 55 ... 0 0 0 0 0 0 1 1 3 4 8 12 21 33 ... Ogólnie x_i = 0, n≤4 x₅ = 1 x_i = x_i−1 + x_i−2 + (i mod 2), i≥6 I można zauważyć, że 3 linijkę z mojej tabelki można rozbić na sumę: 0 0 0 0 0 0 1 1 3 4 8 12 21 33 ... = 0 0 0 0 0 0 1 1 2 3 5 8 13 21 ... + 0 0 0 0 0 0 0 0 1 1 3 4 8 12 ... itd. Znaczy: x₅ = F₁ x₆ = F₂ x₇ = F₃ + F₁ x₈ = F₄ + F₂ x₉ = F₅ + F₃ + F₁ ... x₁₀₀ = F₉₆ + F₉₄ + ... + F₂ = ∑_k=1^96/2(F_2k) https://www.wolframalpha.com/input/?i=sum+k%3D1..%2896%2F2%29+of+fibonacii%282k%29 https://ideone.com/oLJSLd