Witam,
Mamy wyprowadzić wzór na ilość ciągów. Wiemy, że ilość ciągów to (długości n).
Przy czym ciągi budowane są z zastosowaniem liter A B C z zastrzeżeniem, że litery A i B nie mogą wystąpić koło siebie.
Jakiejś wskazówki na początek ?
Napisano 02.04.2014 - 12:50
Witam,
Mamy wyprowadzić wzór na ilość ciągów. Wiemy, że ilość ciągów to (długości n).
Przy czym ciągi budowane są z zastosowaniem liter A B C z zastrzeżeniem, że litery A i B nie mogą wystąpić koło siebie.
Jakiejś wskazówki na początek ?
Napisano 25.09.2011 - 17:55
Napisano 02.04.2014 - 20:07
Bardzo fajne zadanie Ale trudno mi podać jakąkolwiek wskazówkę. Generalnie sprowadza się to do ułożenia odpowiedniej zależności rekurencyjnej, której ogólną postać będziesz później wyznaczał. Ale wskazówkę mogę dać taką, bo z tego faktu potem skorzystałem podczas liczenia: spróbuj obliczyć najpierw, ile ciągów o wyrazach, gdzie A i B nie mogą stać obok siebie, kończy się kolejno na literę A, ile na B i ile na C? Nie chodzi mi oczywiście o konkretne liczby, spróbuj odwołać się w tych wzorach właśnie do , itd.
Użytkownik Tomalla edytował ten post 02.04.2014 - 20:12
Napisano 02.04.2014 - 23:42
Niewiele mi to podpowiedziało, pokażę jak w ogóle to rozumiem.
No chcesz, żebym wyprowadził wzór (na razie tylko ten jeden podetap) na
Gdzie mam wyrazić w zależności od poprzednich wyrazów tego ciagu (rekurencja). Co ma to znaczyć ?
Ilość ciągów kończących się na literę A takich, że A nie stoi obok B.
I teraz ta informacja jedyne co mi daje, to to, że tej litery A już nie mogę "dokleić" na koniec - bo mam informację że tam jest A - nie mogę też dać między ostatnią i przedostatnią ( z oczywistych względów). Mogę też wyciągnąć wniosek że przedostatnia litera to C. Ale nic poza tym o tych ciągach nie wiem.
Napisano 03.04.2014 - 10:02
Pytanie, czy rozwiązywałeś już podobne zadania i wiesz mniej więcej, jak je rozwiązywać? Na wszelki wypadek pokażę ci bardzo łatwe zadanie tego typu, żeby ci pokazać zasadę postępowania:
Załóżmy, że układamy wieżę z klocków o wysokości . Klocków mamy dwa rodzaje: o wysokości i o wysokości . Pytanie jest o ilość możliwych sposobów ułożenia takiej wieży o wysokości .
, bo wystarczy tylko jeden klocek o wysokości . bo wieżę o wysokości można ułożyć albo za pomocą dwóch klocków o wysokości , albo jednego o wysokości . Analogicznie , ale już itd.
Teraz najważniejsza część, czyli wyznaczanie rekurencyjnej zależności: rozważmy wieżę o wysokości . Rozdzielmy to na dwa przypadki: kiedy ostatnim klockiem w wieży będzie klocek o wysokości , i kiedy będzie to klocek o wysokości . Jeżeli ostatni klocek będzie miał wysokość , to takich możliwych wież jest dokładnie (bo sprowadza się to do tego, że tworzymy dowolną wieżę o wysokości i dokładamy jeden klocek o wysokości ). Kiedy natomiast ostatni klocek ma wysokość , możliwych wież jest , dokładnie z tego samego powodu. Można wobec tego ułożyć taką zależność:
... razem z warunkami początkowymi i . A stąd można już w łatwy sposób dojść do postaci ogólnej ( jest to ciąg Fibonacciego ze zmienionymi wyrazami początkowymi ).
Teraz wracając do twojego zadania: chcemy go też podzielić na jakieś "podetapy". Mój pomysł był taki, żeby rozpatrzyć wyrazy o literach. Jeżeli -tą literą jest A, -tą literą mogą być A lub C. Dla B byłyby to B i C, a dla C - A, B lub C. Ale żeby wykorzystać tą zależność musielibyśmy wiedzieć, ile ciągów -literowych, gdzie A i B nie stoją obok siebie, kończy się odpowiednio na A, ile na B i ile na C. Wtedy można ułożyć analogiczną zależność rekurencyjną i po zadaniu
Rozumiesz już mniej więcej metodę postępowania?
Napisano 05.04.2014 - 13:06
Dzięki za ten opis. Tak rozumiem sens rekurencji.
Jeżeli n-tą literą jest A, n+1-tą literą mogą być A lub C. Dla B byłyby to B i C, a dla C - A, B lub C.
Pomyliłeś się - na odwrót z tą A i B.
Ale żeby wykorzystać tą zależność musielibyśmy wiedzieć, ile ciągów n-literowych, gdzie A i B nie stoją obok siebie, kończy się odpowiednio na A, ile na B i ile na C.
No właśnie, i na tym polega trudność w tym zadaniu.
Heh, już wiem na czym polega nieporozumienie!
Ja źle wyraziłem treść:
Ile jest takich ciągów, złożonych z A,B,C takich, że ani razu nie wystąpi litera A obok litery A, tzn nie może być podciągu AA - tak samo nie może być podciagu BB, ale może być CC
Tzn, poprawne jest np:
ABABACCACABACCCACCCBCCCBA
Napisano 05.04.2014 - 16:52
Ach, no widzisz Ale rozwiązanie będzie identyczne, nawet jak się zmieni treść zadania w ten sposób.
Najpierw policzmy, ile jest takich ciągów o długości , jeżeli ostatnią literą ma być C. Zauważ, że jeżeli weźmiemy dowolny ciąg spełniający warunki z zadania o długości mniejszej o jeden, czyli (a jest ich ), możemy do każdego z nich dopisać C i w ten sposób otrzymamy wszystkie możliwe ciągi o długości z literą C na końcu. Z tego więc wniosek, że wszystkich ciągów o długości z literą C na końcu jest .
Teraz litery A i B. Kluczem jest tutaj zauważenie, że one muszą być traktowane "na równi" i zachowują się niejako symetrycznie. Wyobraź sobie, że masz pod ręką wszystkie możliwe ciągi o długości z literą A na końcu. Jeżeli zamienisz w tych ciągach literę A na B i B na A, otrzymasz ... wszystkie możliwe ciągi o długości z literą B na końcu. Z tego więc wniosek, że tych ciągów jest tyle samo.
Wprowadźmy na szybko oznaczenia: - liczba możliwych ciągów o długości z literą A na końcu i analogicznie i . Zależność między nimi jest oczywista: jak dodamy wszystkie, otrzymujemy , czyli:
Wiemy już, że . Do tego . Otrzymujemy więc szybko z :
Teraz pozostaje już tylko formalność i ułożenie zależności rekurencyjnej
Napisano 05.04.2014 - 21:12
Okey, dzięki bardzo - jutro z pewnością napiszę tutaj dokończenie tego zadania.
Dziś natomiast jeszcze chciałbym dopytać.
Oczywiście ze wszystkim tutaj się zgadzam. Ale sam próbowałem i jestem w pewnym punkcie, z którego nie wiadomo jak wybrnąć.
Ja trochę wyszedłem od innej strony, ale chyba też prawidłowo, a mianowicie stosując Twoje oznaczenia:
oraz
Potem wyznaczyłem, że
I co Ty sądzisz o tym rozwiązaniu ?
Napisano 06.04.2014 - 21:56
Ja trochę wyszedłem od innej strony, ale chyba też prawidłowo, a mianowicie stosując Twoje oznaczenia:
oraz
Potem wyznaczyłem, że
I co Ty sądzisz o tym rozwiązaniu ?
Sposób ciekawy Zależności oczywiście poprawne (oprócz tej ostatniej, nie bardzo też wiem, skąd ją wziąłeś), ale to ... na razie tylko zależności. Trzeba by trochę popracować, żeby z samych zależności wyprowadzić rozwiązanie. Ja tam nie widzę prostego sposobu, strasznie brzydkie rachunki mi z tego wychodzą (ale być może można to rozwiązać szybko jak się coś zauważy, nie wiem). Z ostatniego rozwiązania mamy , ale to chyba tylko tyle.
Napisano 07.04.2014 - 10:40
Próbując dalej pracować z Twoimi zależnościami, żeby wyprowadzić wzór na musiałem skorzystać właśnie z tej pewnej zależności:
I teraz należy wziąć funkcję tworzącą - masa obliczeń. Ale tędy dojdziemy do wyniku, prawda ?
Napisano 07.04.2014 - 13:53
Jak już masz zależność rekurencyjną, jest mnóstwo metod szukania postaci ogólnej. Funkcje tworzące to rzeczywiście trochę skomplikowany i pracochłonny sposób, łatwiej moim zdaniem jest rozwiązać zadanie układając równanie charakterystyczne i iść dalej tą drogą.
Napisano 07.04.2014 - 15:54
A czy właściwie ułożyłem te zależności ?
Jeśli tak, to co to za metoda ? Ja znam tylko funkcje tworzące do takich rzeczy.
Napisano 07.04.2014 - 16:25
Zależność jest jak najbardziej prawidłowa. Tylko co oznacza u ciebie ? Mogę jedynie zgadywać, że chodziło ci o , a taka zależność jest nieprawdziwa (brakuje ci dwójki przy drugim składniku). No i jak z takiej postaci udało ci się ułożyć prawidłową zależność rekurencyjną?
A metoda równania charakterystycznego jest bardzo prosta: na samym początku zakładasz, że rozwiązanie jest postaci i podstawiasz to do swojej zależności rekurencyjnej, którą stworzyłeś:
Teraz rozwiązujesz normalne równanie kwadratowe. Wychodzą dwa rozwiązania:
Wobec tego rozwiązanie ogólne zależności rekurencyjnej jest postaci:
... gdzie i są jakimiś stałymi. Jeżeli ma się warunki początkowe, to właśnie z nich się wylicza te stałe i otrzymuje się wzór na ilość ciągów Skoro i to rozwiązuje się układ:
Jak chcesz więcej się dowiedzieć odnośnie tej metody, wystarczy że wyszukasz frazę "równanie charakterystyczyne rekurencja" lub coś podobnego Ale aż mnie zdziwiło, że nic o niej nie wiedziałeś.
Napisano 07.04.2014 - 17:06
No i jak z takiej postaci udało ci się ułożyć prawidłową zależność rekurencyjną?
Po prostu źle przepisałem tutaj z zeszytu pośrednie obliczenia, nic poza tym.