Proszę o pomoc w rozwiązaniu 3 zadanek:
1) Ile podzbiorów zbioru {1,2,3,...} wliczając zbiór pusty nie zawiera sąsiednich liczb?
2) Na ile sposobów można wypełnić prostokąt o wymiarach 2 x n kostkami domino w wymiarach 2 x 1?
3) Ile jest słów długości n złożonych z liter a,b,c, w których nie ma dwóch kolejnych liter a?
Bardzo proszę o jakiś komentarz do zadań i w miarę możliwości o wzór rekurencyjny:)
Pozdrawiam
rekurencje - 3 zadania
-
mol_ksiazkowy
- Użytkownik
- Posty: 11373
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
-
Czesio
- Użytkownik
- Posty: 103
- Rejestracja: 30 wrz 2005, o 18:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 3 razy
- Pomógł: 6 razy
rekurencje - 3 zadania
Ad.2 Nie jestem dobry w te klocki, więc jeśli się mylę, to poprawcie mnie.
Możemy postawić klocek pionowo, i wtedy pozostanie nam \(\displaystyle{ n-1}\) "miejsc" lub postawić dwa klocki poziomo i pozostanie nam \(\displaystyle{ n-2}\) miejsc. Zatem:
\(\displaystyle{ F_{n}=F_{n-1}+F_{n-2}}\) , czyli Fibonacci.
Możemy postawić klocek pionowo, i wtedy pozostanie nam \(\displaystyle{ n-1}\) "miejsc" lub postawić dwa klocki poziomo i pozostanie nam \(\displaystyle{ n-2}\) miejsc. Zatem:
\(\displaystyle{ F_{n}=F_{n-1}+F_{n-2}}\) , czyli Fibonacci.
-
Hefajstos1
- Użytkownik
- Posty: 6
- Rejestracja: 28 sie 2012, o 19:42
- Płeć: Mężczyzna
- Lokalizacja: Wawa
rekurencje - 3 zadania
3.
Alfabet zawiera dwie litery \(\displaystyle{ \Sigma ={a,b}}\)
\(\displaystyle{ S_[n]}\) - liczba słów długości słów n, gdzie nie występuje "aa".
1) a,b,c...\(\displaystyle{ \infty}\) - \(\displaystyle{ S_{n-2}}\)
2) b,c...\(\displaystyle{ \infty}\) -\(\displaystyle{ S_{n-1}}\)
\(\displaystyle{ \begin{cases}
S_{n}= S_{n-2}+S_{n-1}; n \ge 2 \\
S_{0}= 1 \\
S_{1}= 2 \\
\end{cases}}\)
Alfabet zawiera dwie litery \(\displaystyle{ \Sigma ={a,b}}\)
\(\displaystyle{ S_[n]}\) - liczba słów długości słów n, gdzie nie występuje "aa".
1) a,b,c...\(\displaystyle{ \infty}\) - \(\displaystyle{ S_{n-2}}\)
2) b,c...\(\displaystyle{ \infty}\) -\(\displaystyle{ S_{n-1}}\)
\(\displaystyle{ \begin{cases}
S_{n}= S_{n-2}+S_{n-1}; n \ge 2 \\
S_{0}= 1 \\
S_{1}= 2 \\
\end{cases}}\)
Ostatnio zmieniony 29 sie 2012, o 18:12 przez Frey, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
rekurencje - 3 zadania
@Hefajstos1
1. Mocny wykop, nie ma co
2. Dlaczego \(\displaystyle{ S_{1}}\) to 2? Nie mamy 3 słów 1-literowych (a; b; c)? Trochę też nie rozumiem Twojego zapisu z nieskończonościami. Ja bym do tego podszedł trochę inaczej (tzn. zdefiniował \(\displaystyle{ A_{n}, B_{n}, C_{n}}\) jako n-literowe ciągi kończące się na odpowiednio a, b, c, a później zapisał \(\displaystyle{ S_{n}}\) jako odpowiednią sumę tychże ciągów tzn.:
\(\displaystyle{ \begin{cases}
S_{n} = 2A_{n-1} + 3B_{n-1} + 3C_{n-1}\\
A_{n}= B_{n-1} + C_{n-1}\\
B_{n}= A_{n-1} + B_{n-1} + C_{n-1}\\
C_{n}= A_{n-1} + B_{n-1} + C_{n-1}\\
\end{cases}}\),
ale w ten sposób zadanie robi się podejrzanie trudniejsze od 2 poprzednich (co prawda nie aż tak trudne, zwłaszcza jeśli zauważyć, że \(\displaystyle{ B_{n}=C_{n}}\), no ale i tak trudniejsze), co powoduje, że zaczynam się zastanawiać czy nie ma jakiegoś prostszego sposobu.
Pierwsze chyba z Fibonacciego. Jeśli \(\displaystyle{ S_{n}}\) to liczba takich podzbiorów to mamy 2 sytuacje - ostatni element nie został wybrany (wtedy pozostaje \(\displaystyle{ S_{n-1}}\) sposobów (dlaczego?)) albo został (co daje \(\displaystyle{ S_{n-2}}\) sposobów (dlaczego?)). Zatem \(\displaystyle{ S_{n} = S_{n-1} + S_{n-2}}\). Jeszcze pozostaje określić \(\displaystyle{ S_{0}}\) i \(\displaystyle{ S_{1}}\).
1. Mocny wykop, nie ma co
2. Dlaczego \(\displaystyle{ S_{1}}\) to 2? Nie mamy 3 słów 1-literowych (a; b; c)? Trochę też nie rozumiem Twojego zapisu z nieskończonościami. Ja bym do tego podszedł trochę inaczej (tzn. zdefiniował \(\displaystyle{ A_{n}, B_{n}, C_{n}}\) jako n-literowe ciągi kończące się na odpowiednio a, b, c, a później zapisał \(\displaystyle{ S_{n}}\) jako odpowiednią sumę tychże ciągów tzn.:
\(\displaystyle{ \begin{cases}
S_{n} = 2A_{n-1} + 3B_{n-1} + 3C_{n-1}\\
A_{n}= B_{n-1} + C_{n-1}\\
B_{n}= A_{n-1} + B_{n-1} + C_{n-1}\\
C_{n}= A_{n-1} + B_{n-1} + C_{n-1}\\
\end{cases}}\),
ale w ten sposób zadanie robi się podejrzanie trudniejsze od 2 poprzednich (co prawda nie aż tak trudne, zwłaszcza jeśli zauważyć, że \(\displaystyle{ B_{n}=C_{n}}\), no ale i tak trudniejsze), co powoduje, że zaczynam się zastanawiać czy nie ma jakiegoś prostszego sposobu.
Pierwsze chyba z Fibonacciego. Jeśli \(\displaystyle{ S_{n}}\) to liczba takich podzbiorów to mamy 2 sytuacje - ostatni element nie został wybrany (wtedy pozostaje \(\displaystyle{ S_{n-1}}\) sposobów (dlaczego?)) albo został (co daje \(\displaystyle{ S_{n-2}}\) sposobów (dlaczego?)). Zatem \(\displaystyle{ S_{n} = S_{n-1} + S_{n-2}}\). Jeszcze pozostaje określić \(\displaystyle{ S_{0}}\) i \(\displaystyle{ S_{1}}\).