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, ...)
13 gru 22:59
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
14 gru 01:15
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.
15 gru 00:05
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.
15 gru 00:42
makuchowski: Słowo Abba występuje w X 300 razy
15 gru 01:09
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 xi = 0, n≤4 x5 = 1 xi = xi−1 + xi−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: x5 = F1 x6 = F2 x7 = F3 + F1 x8 = F4 + F2 x9 = F5 + F3 + F1 ... x100 = F96 + F94 + ... + F2 = ∑k=196/2(F2k) https://www.wolframalpha.com/input/?i=sum+k%3D1..%2896%2F2%29+of+fibonacii%282k%29 https://ideone.com/oLJSLd
15 gru 12:20