Czy to jest rekurencja? nicck: Mam takie zadanie ze studiów nad którym się już trochę głowię i nie bardzo wiem jak mogę się za nie zabrać. Jego treść brzmi: "Pracujesz w firmie kryptograficznej. Odczytujesz zaszyfrowane wiadomości złożone jedynie z cyfr0,1,2. Z pewnego punktu widzenia interesujące są te wiadomości, w których nie występują konfiguracje 00 oraz 01. Takie wiadomości należą do klasy X. Odpowiedz na pytanie, ile jest różnych wiadomości klasy X złożonych z czterdziestu znaków? Odpowiedź uzasadnij, przedstawiając stosowne obliczenia." Jak do tego podejść. Czy jest to rekurencja czy może da się to rozwiązać w jakiś inny sposób?

wredulus_pospolitus: tak ... to będzie ciąg rekurencyjny

wredulus_pospolitus: to wyznaczeniu ciągu rekurencyjnego ... możesz wyznaczyć jego jawną postać

nicck: a jak można się domyślić czy trzeba rozwiązać to rekurencją, a nie w żaden inny sposób? Jak do tego dojść? Co wskazuje na to że tu trzeba użyć rekurencji? Dzięki

nicck: chciałbym zaoytać o warunki początkowe.Pisze w treści tego zadania że "odczytuje zaszyfrowane wiadomości złożone jedynie z cyfr 0,1,2" Czy i jakie tu będą warunki początkowe. Czy warunki początkowe to w tym przypadku a₀ = 0 a₁ = 1 a₂ = 2 czy raczej idąc w dalszą treść tego zadania "Z pewnego punktu widzenia interesujące są te wiadomości, w których nie występują konfiguracje 00 oraz 01. Takie wiadomości należą do klasy X." a₀ = 00 a₁ = 01 Które są poprawne i dlaczego?

kerajs: Wyciągasz błędne wnioski, gdyż to zadanie wcale nie musi być rozwiązywane z pomocą rekurencji. Możesz wygenerować 3⁴⁰ ciągów, skreślić zawierające 00 i 01 i zliczyć pozostałe. To też rozwiązanie, choć ciut czasochłonne. Inne, bez rekurencji: Oznaczenia: i − liczba znaków ''0'' j − liczba znaków ''2'' Szukana liczba ciągów klasy X to:

	40−i j	j+1 i
240+∑i=120 ( ∑j=i−1 40−i			)

Wredulus wybrał rekurencję najprawdopodobniej kierując się doświadczeniem. X_n=2X_n−1+X_n−2 Dla warunków początkowych: W₁=3 i W₂=7 dostaje się:

	1		1
Xn=		(1+√2)n+1+		(1−√2)n+1
	2		2

Wystarczy teraz policzyć X₄₀

kerajs: Sorki, miało być: Dla warunków początkowych: X₁=3 i X₂=7 dostaje się: .......

nicck: Podziękował

nicck: Przepraszam. Jeszcze tylko chciałbym dopytać o te warunki początkowe x1=3 i x2=7. Jak to policzyłeś?

nicck: Wolałbym to rekurencją rozwiązać. Uczę się tego pod egzamin z dyskretnej i gość powiedział że takie zadania do rozwiązania tylko rekurencją(jednorodną lub niejednorodną).

nicck: Te warunki początkowe x1=3 to są ciągi, które zawierają w sobie 0 i jest ich 3, a tych bez 0 jest 7?

. : x₁ − − − ciągi długości '1' i są to: 0, 1, 2, x₂ − − − ciągi długości '2' i spełniające warunki to: 02, 10, 11, 12, 20, 21, 22 Ojjjj... długa droga Ciebie czeka aby kampania wrześniowa nie zakończyła się klęską.

kerajs: Obawiam się, że nie zrozumiałeś co napisałem. Przez X_n rozumiem liczbę n−elementowych ciągów klasy X . X₁ to ciągi jednoelementowe klasy X. To: 0, 1 i 2 , a stąd X₁=3 X₂ to ciągi dwuelementowe klasy X. To: 02, 10, 11, 12, 20, 21 i 22 , a stąd X₂=7 . Zamiast wypisywać można było odjąć od 3² możliwych dwuelementowych ciągów te zabronione, czyli 00 i 01.

nicck: @kerajs Ok dzięki. Rozumiem, że to co tutaj podałeś :X_n=2X_n−1+X_n−2 to jest wzór rekurencyjny do tego zadania? @ . : Tobie również dziękuje za pomoc. Dziękuje również za dobrą rade:"Ojjjj... długa droga Ciebie czeka aby kampania wrześniowa nie zakończyła się klęską."

wredulus_pospolitus: tak ... to jest wzór rekurencyjny do tego zadania ... pytanie brzmi −−− czy jesteś w stanie zrozumieć w jaki sposób do tego wzoru można dojść

nicck: @wredulus_pospolitus: No właśnie tu jest pies pogrzebany. Jak do tego dojść? Nie jak rozwiązać? Tylko dojść? Jak ustalić że tutaj pierwszy warunek początkowy wygląda tak x₁ = 0, 1, 2,, a nie inaczej?

wredulus_pospolitus: Jaki kierunek studiujesz? a jak 'inaczej' może być? Jakie inne ciągi długości '1' mogłyby być

nicck : @wredulus_pospolitus: Informatykę. Raczej myślałem że powinny tam być ciągi o dł.2. Bo skoro pisze w zadaniu że interesują nas wiadomości , w których nie występują konfiguracje 00 i 01 to założyłem raczej że to powinny być ciągi 2−elementowe.

wredulus_pospolitus: to błędnie założyłeś ... no to jako student informatyki niestety musisz dogłębnie pojąć sposób myślenia (kombinowania) w tego typu zadaniach. Dlatego polecam Ci, abyś przy tym zadaniu 'pokombinował' w jaki sposób stworzyć wzór rekurencyjny. Jeżeli chcesz ... możesz tutaj przedstawić swój tok myślenia (tworzenia) tegoż wzoru.

wredulus_pospolitus: dodatkowo treść zadania mówi o tym, że NIE INTERESUJĄ nas wiadomości zawierające 00, 01.

jc: Do rachunków dokładnych chyba najlepszy jest zacytowany wzór rekurencyjny. nicck, zachęcam do samodzielnego uzasadnienia wspomnianego wzoru. wynik = 1466015503703

jc: ... = 2222142093424997

nicck: Takie pytanie jeszcze odnośnie tych wyrazów początkowych. Pierwszy wyraz to X₁ = 3 i składa się z cyfr 0, 1, 2. Natomiast drugi wyraz X₂ = 7 i składa sie z 02, 10, 20, 11, 22, 12, 21. Po co w takim bądź razie jest nam potrzebny wyraz początkowy X₁, skoro on zawiera cyfry 0,1,2, a nie zostajemy tylko przy wyrazie X₂, który już zawiera jakieś kombinacje cyfr podanych w zadaniu(0,1,2).

jc: wzór masz taki: x_n+1= 2x_n +x_n−1. aby znaleźć x₃, potrzebujesz x₁ i x₂. x₃ = 2*7+3 = 17 Można też przyjąć: x₀=1, x₁=3 (mamy tylko jeden ciąg o długości 0 − pusty napis). Wtedy x₂=2*3+1 = 7. Pomyśl, jak uzyskać wzór rekurencyjny. Przy okazji zauważyłem, że znów coś źle wpisałem (tym razem x₁) x₄₀=2470433131948081

jc: Wzór rekurencyjny można pewnie uzyskać na różne sposoby. Ja rozpatrzyłem 3 rodzaje napisów: kończące się zerem, jedynką, dwójką.

nicck: Jeżeli miałbym odwoływać się do tego wzoru, który został podany a_n = 2a_n−1+a_n−2 to dlaczego tak? Dlatego że to rekurencja, a więc odwołujemy się do ostatniej "kopii" czyli w tym przypadku do wyrazu a₂ = 7, a potem do przedostatniej czyli a₁ = 3. Napis 2a_n−1 sugeruje że w tym wypadku odwołujemy się do wyrazu a₂, czyli do ciągu 2−elementowego o długości 7. I zostaje nam jeszcze pierwszy wyraz czyli a₁ = 3. To jest ciąg o długości 3 ale składający się z pojedynczych elementów dlatego jest a_n−2. Reasumując ten zapisz 2a_n−1 odwołuje się do wyrazu a₂, który jest ciągiem 2−elementowym o dł.7, natomiast to a_n−2 odwołuje się do wyrazu a₁, który jest ciągiem 1−elementowym o dł. 3.

jc: Twój ciąg rekurencyjny to ciąg liczb mówiących ile mamy pewnych napisów. x₀ = 1, mamy jeden pusty napis x₁ = 3, mamy 3 napisy o długości 1: 0, 1, 2 x₂ = 7, mamy 7 dopuszczalnych napisów o długości 2: 01, 02, 11, 12, 20, 21, 22 wzór rekurencyjny : x₀ = 1, x₁=3, x_n+1=2x_n+x_n−1 oczywiście można by podać rekurencję, która by mówiła, jak przejść od jednego zbioru napisów do kolejnego (jeśli napis kończy się na 0 dopisz 2, jeśli napis kończy się na 1 lub 2, dopisz 0, 1 lub 2) { } → {0, 1, 2} →{02, 10, 11, 12, 20, 21, 22} → {020, 021, 022, 102, 110, 111, 112, 120, 121, 122, 202, 210, ..., 222}

nicck: ok. dzięki za pomoc. Teraz spróbuje samodzielnie sobie to wszystko w głowie ułożyć. Dziękuje.