Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        STUDIA        

Wzór na ilość ciągów



  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
12 odpowiedzi w tym temacie

#1 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 02.04.2014 - 12:50

Witam,

Mamy wyprowadzić wzór na ilość ciągów. Wiemy, że ilość ciągów to a_n (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 ?


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

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 n 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 a_n, a_{n-1} itd. :)


Użytkownik Tomalla edytował ten post 02.04.2014 - 20:12

  • 1
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#3 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

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 a_n

Gdzie a_n 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.


  • 0

#4 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

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 n. Klocków mamy dwa rodzaje: o wysokości 1 i o wysokości 2. Pytanie jest o ilość możliwych sposobów ułożenia takiej wieży o wysokości n.

 

a_1=1, bo wystarczy tylko jeden klocek o wysokości 1. a_2=2 bo wieżę o wysokości 2 można ułożyć albo za pomocą dwóch klocków o wysokości 1, albo jednego o wysokości 2. Analogicznie a_3=3, ale już a_4=5 itd.

 

Teraz najważniejsza część, czyli wyznaczanie rekurencyjnej zależności: rozważmy wieżę o wysokości n. Rozdzielmy to na dwa przypadki: kiedy ostatnim klockiem w wieży będzie klocek o wysokości 1, i kiedy będzie to klocek o wysokości 2. Jeżeli ostatni klocek będzie miał wysokość 1, to takich możliwych wież jest dokładnie a_{n-1} (bo sprowadza się to do tego, że tworzymy dowolną wieżę o wysokości n-1 i dokładamy jeden klocek o wysokości 1 ). Kiedy natomiast ostatni klocek ma wysokość 2, możliwych wież jest a_{n-2}, dokładnie z tego samego powodu. Można wobec tego ułożyć taką zależność:

 

\fbox{a_n=a_{n-1}+a_{n-2}}

 

... razem z warunkami początkowymi a_1=1 i a_2=2. 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 n+1 literach. 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. 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. Wtedy można ułożyć analogiczną zależność rekurencyjną i po zadaniu :)

Rozumiesz już mniej więcej metodę postępowania?


  • 1
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#5 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

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


  • 0

#6 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

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 n, 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 n-1 (a jest ich a_{n-1}), możemy do każdego z nich dopisać C i w ten sposób otrzymamy wszystkie możliwe ciągi o długości n z literą C na końcu. Z tego więc wniosek, że wszystkich ciągów o długości n z literą C na końcu jest a_{n-1}.

 

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 n 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 n z literą B na końcu. Z tego więc wniosek, że tych ciągów jest tyle samo.

 

Wprowadźmy na szybko oznaczenia: S^A_n - liczba możliwych ciągów o długości n z literą A na końcu i analogicznie S^B_n i S^C_n. Zależność między nimi jest oczywista: jak dodamy wszystkie, otrzymujemy a_n, czyli:

 

S^A_n+S^B_n+S^C_n\quad=\quad a_n\qquad(*)

 

Wiemy już, że \fbox{S^C_n=a_{n-1}}. Do tego S^A_n=S^B_n. Otrzymujemy więc szybko z (*):

 

S^A_n+S^A_n+a_{n-1}=a_n\qquad\Leftrightarrow\qquad \fbox{S^A_n=S^B_n=\frac{a_n-a_{n-1}}{2}}

 

Teraz pozostaje już tylko formalność i ułożenie zależności rekurencyjnej :)


  • 1
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#7 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

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:
S_n^A=S_{n-1}^B+S_{n-1}^C

S_n^B=S_{n-1}^C+S_{n-1}^A

S_n^C=S_{n-1}^A+S_{n-1}^B+S_{n-1}^C

oraz

a_n=2S_{n-1}^A+2S_{n-1}^B+3_{n-1}^C

Potem wyznaczyłem, że

S_n^A=S_{n-3}^3A+S_{n-2}^A+S_{n-1}^A

 

I co Ty sądzisz o  tym rozwiązaniu ?


  • 0

#8 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 06.04.2014 - 21:56

Ja trochę wyszedłem od innej strony, ale chyba też prawidłowo, a mianowicie stosując Twoje oznaczenia:

S_n^A=S_{n-1}^B+S_{n-1}^C

S_n^B=S_{n-1}^C+S_{n-1}^A

S_n^C=S_{n-1}^A+S_{n-1}^B+S_{n-1}^C

oraz

a_n=2S_{n-1}^A+2S_{n-1}^B+3_{n-1}^C

Potem wyznaczyłem, że

S_n^A=S_{n-3}^3A+S_{n-2}^A+S_{n-1}^A

 

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 S_n^C\,=\,S_{n-1}^A+S_{n-1}^B+S_{n-1}^C\,=\,a_{n-1}, ale to chyba tylko tyle.


  • 1
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#9 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 07.04.2014 - 10:40

Próbując dalej pracować z Twoimi zależnościami, żeby wyprowadzić wzór na a_{n+1} musiałem skorzystać właśnie z tej pewnej zależności:
 

a_{n+1}= 2a_{n}+b_n + 3c_n = 2a_n + a_{n-1}

a_0=1;a_1=3

 

I teraz należy wziąć funkcję tworzącą - masa obliczeń. Ale tędy dojdziemy do wyniku, prawda ?


  • 0

#10 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

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ą.


  • 1
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#11 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

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.


  • 0

#12 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 07.04.2014 - 16:25

Zależność a_{n+1}=2a_n+a_{n-1} jest jak najbardziej prawidłowa. Tylko co oznacza u ciebie a_{n+1}= 2a_{n}+b_n + 3c_n ? Mogę jedynie zgadywać, że chodziło ci o a_{n+1}=2S^A_n+S^B_n+3S^C_n, 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 a_n=\lambda^n i podstawiasz to do swojej zależności rekurencyjnej, którą stworzyłeś:

 

a_{n+1}=2a_n+a_{n-1}\\\lambda^{n+1}=2\lambda^n+\lambda^{n-1}\\\lambda^2-2\lambda-1=0

 

Teraz rozwiązujesz normalne równanie kwadratowe. Wychodzą dwa rozwiązania:

 

\lambda=\frac{2\pm2\sqrt{2}}{2}=1\pm\sqrt{2}

 

Wobec tego rozwiązanie ogólne zależności rekurencyjnej jest postaci:

 

a_n\quad=\quad \alpha(1+\sqrt{2})^n+\beta(1-\sqrt{2})^n

 

... gdzie \alpha i \beta 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 a_0=1 i a_1=3 to rozwiązuje się układ:

 

\{\alpha+\beta=1\\\alpha(1+\sqrt{2})+\beta(1-\sqrt{2})=3

 

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ś.


  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#13 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

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.


  • 0