Witam, mam za zadanie wyznaczyć ilość możliwych kombinacji zbioru 2=elementowego dla ciągu o długości n, tak by jeden z tych dwóch elementów (obojętnie który) nigdy nie występował jeden obok drugiego.
Przykłady:
Zbiór = 0 i 1
Ciąg o długości = 2
Element, który nie ma występować obok siebie = 1
Możliwe kombinacje = 00 01 10
Wynik: 3
Zbiór = 0 i 1
Ciąg o długości = 3
Element, który nie ma występować obok siebie = 1
Możliwe kombinacje = 000 001 010 100 101
Wynik: 5
Zbiór = 0 i 1
Ciąg o długości = 4
Element, który nie ma występować obok siebie = 1
Możliwe kombinacje = 0000 0001 0010 0100 1000 1010 0101 1001
Wynik: 8
Czy jestem w stanie wyznaczyć to jakimś wzorem albo sposobem?
Przez pewien czas uważałem, iż wzór n+2^(n-2), gdzie n to długość ciągu, jest poprawny, jednak wszystko wskazuje na to, że dla większych długości ciągu jest on błędny.
Kombinacje 2-elementowego zbioru
Kombinacje 2-elementowego zbioru
Chodzi mi o to, aby język giętki / Powiedział wszystko, co pomysli głowa. Juliusz Słowacki (1809 - 1849)
- Konikov
- Użytkownik
- Posty: 497
- Rejestracja: 13 mar 2008, o 18:56
- Płeć: Mężczyzna
- Lokalizacja: z całki tego świata
- Podziękował: 66 razy
- Pomógł: 44 razy
Kombinacje 2-elementowego zbioru
\(\displaystyle{ A_n}\) - ilość kombinacji dla ciągu o długości \(\displaystyle{ n}\)
\(\displaystyle{ A_1 = 2\\
A_2 = 3\\
A_n = A_{n-1} + A_{n-2}}\)
Teraz - dlaczego? Powiedzmy, że sytuacja jest taka sama jak w Twoich przykładach, czyli jest \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\), a \(\displaystyle{ 1}\) nie mogą być obok siebie (symetryczna sytuacja jest z obliczeniowego punktu widzenia identyczna). Wtedy na początku możesz postawić:
\(\displaystyle{ 0...}\)
lub
\(\displaystyle{ 10...}\) (wiadomo, że za jedynką musi stać zero)
Tak więc w pierwszym przypadku pozostaje do wypełnienia \(\displaystyle{ n-1}\) miejsc, w drugim \(\displaystyle{ n-2}\).
\(\displaystyle{ A_1 = 2\\
A_2 = 3\\
A_n = A_{n-1} + A_{n-2}}\)
Teraz - dlaczego? Powiedzmy, że sytuacja jest taka sama jak w Twoich przykładach, czyli jest \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\), a \(\displaystyle{ 1}\) nie mogą być obok siebie (symetryczna sytuacja jest z obliczeniowego punktu widzenia identyczna). Wtedy na początku możesz postawić:
\(\displaystyle{ 0...}\)
lub
\(\displaystyle{ 10...}\) (wiadomo, że za jedynką musi stać zero)
Tak więc w pierwszym przypadku pozostaje do wypełnienia \(\displaystyle{ n-1}\) miejsc, w drugim \(\displaystyle{ n-2}\).
Kombinacje 2-elementowego zbioru
Aż sam jestem na siebie teraz zły. Bo taką zależność zauważyłem już wcześniej, jednak testując ją błędnie wyznaczyłem kombinacje dla 6 (wynik wychodził mi 22, przez co, ta zależność się nie sprawdzała) i na siłę szukałem kolejnego rozwiązania.
Dziękuję bardzo za pomoc
Dziękuję bardzo za pomoc