Zależność rekurencyjna
ABC: Niech sn oznacza liczbę ciągów ternarnych (składających się z cyfr 0, 1 i 2) o długości n,
n ≥ 1, w których na każdych dwóch sąsiednich pozycjach występują dwie różne cyfry. Wyznacz
rekurencyjną zależność dla sn
Czy mógłby ktoś pomóc bo nie mam żadnego pomysłu jak ta zależność miałaby wyglądać. Dodam dla
jasności że 0 może znaleźć się na początku ciągu
1 lut 13:04
kerajs:
Sn+1=2Sn ∧ S1=3
PS
Sn+1=3*2n
1 lut 13:53
ABC: Czyli tak jak podejrzewałem ale wydawało mi się zbyt proste dzięki
1 lut 13:57
1 lut 13:59
ABC: A mógłbyś mi jeszcze pomóc w trudniejszym przykładzie ? Muszę znaleźć jeszcze taką zależność:
"Niech an oznacza liczbę takich n−cyfrowych liczb naturalnych (n≥1), w których każda cyfra
należy do
zbioru {2, 3, 4, 5}, a ponadto liczby wystąpień cyfr 2 oraz 5 są parzyste, a cyfr 3 i 4
nieparzyste. "
1 lut 14:04
kerajs:
Treść zadania można interpretować dwojako:
1) wśród n cyfr liczba cyfr 2 lub 5 jest parzysta, a cyfr 3 lub 4 jest nieparzysta (np: 333252)
2) cyfry 2 lub 5 występują wyłącznie w seriach o długości parzystej, a 3 i 4 w seriach o
długości nieparzystej (np: 333223)
Określ która wersja jest właściwą.
2 lut 07:14
kerajs:
Errata: ciąg dla wersji 1 miał mieć postać: 333242
2 lut 07:17
wredulus_pospolitus:
@kerajs, raczej mamy tutaj:
wśród n cyfr liczba cyfr 2 i 5 jest parzysta, a cyfr 3 i 4 jest nieparzysta (np:
333242)
2 lut 07:26
wredulus_pospolitus:
a wtedy mamy:
a1 = 0
a2 = 2
a2n+2 = 4a2n
a2n+1 = 0
2 lut 07:29
wredulus_pospolitus:
chociaż co ja napisałem ... jest ich o wiele więcej.
2 lut 07:29
kerajs:
Problem w tym, że język potoczny nie jest tak precyzyjny jakby chcieli autorzy zadań.
Przez ''wśród n cyfr liczba cyfr 2 lub 5 jest parzysta'' rozumiem:
Jeśli w ciągu występuje cyfra 2, to parzystą ilość razy; jeśli w ciągu występuje cyfra 5, to
parzystą ilość razy; a jeśli w ciągu występuje zarówno cyfra 2 i 5, to każda parzystą ilość
razy.
Odpowiedź dla wersji b) : an=an−1+3an−2+2an−3−2an−4
2 lut 10:27
Mariusz:
Swoją drogą powodzenia dla tego kto chciałby wyznaczyć wzór jawny tej rekurencji
Takie równania to tylko Vaxowi chciało się rozwiązywać
(oczywiście tylko wtedy gdy się uczył je rozwiązywać)
Jeśli ktoś chce spróbować znaleźć wzór jawny to proponuję poczytać
http://matwbn.icm.edu.pl/ksiazki/mon/mon11/mon1110.pdf
3 lut 13:06
kerajs:
Przywaliłeś Sierpińskim, a tu ani wzorem jawnym, ani rekurencyjnym nikt nie jest
zainteresowany.
3 lut 20:03