Witam, mam do rozwiązania następujące zadanie
Niech \(\displaystyle{ h(k,n)}\) będzie liczbą rozsadzeń w określonym porządku \(\displaystyle{ k}\) pacjentów w taki sposób w poczekalni, w której jest \(\displaystyle{ n}\) krzeseł w taki sposób, aby żaden pacjent nie siedział bezpośrednio obok drugiego. Znaleźć zależność rekurencyjną dla \(\displaystyle{ h(k,n)}\). Jakieś wskazówki?
Rozsadzenia pacjentów
-
squared
- Użytkownik
- Posty: 1017
- Rejestracja: 21 mar 2009, o 11:11
- Płeć: Mężczyzna
- Podziękował: 167 razy
- Pomógł: 152 razy
Rozsadzenia pacjentów
Ostatnio zmieniony 6 lis 2015, o 21:59 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
arek1357
- Użytkownik
- Posty: 5736
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Rozsadzenia pacjentów
Dla jednego krzesła masz:
\(\displaystyle{ h(1,1)=1}\)
Dla dwóch krzeseł masz tylko jednego pacjenta:
\(\displaystyle{ h(2,1)=2}\)
Dla trzech krzeseł masz albo jednego albo dwóch pacjentów, którzy mogą permutować:
\(\displaystyle{ h(3,1)=3}\)
\(\displaystyle{ h(3,2)= 1 \cdot 2!}\)
Dla czterech krzeseł może być jeden lub dwa pacjenty:
\(\displaystyle{ h(4,1)=4}\)
\(\displaystyle{ h(4,2)=3 \cdot 2!}\)
itd...
Ogólnie teraz łatwo zauważyć, że:
\(\displaystyle{ h(n,1)=n}\)
Pacjentów musi być mniej lub równo niż połowa krzeseł dla parzystych albo maksymalnie dla nieparzystych może być:
\(\displaystyle{ k=\left[ \frac{n}{2} \right] +1}\)
bo wtedy:
\(\displaystyle{ h(n,k)=0}\)
Wyciągając wzór ogólny otrzymamy:
\(\displaystyle{ h(n+1,k)=h(n,k)+k \cdot h(n-1,k-1)}\)
Wzór ogólny tak należy rozumieć:
Mamy \(\displaystyle{ k}\) pacjentów i \(\displaystyle{ n+1}\) krzeseł najpierw wszystkich pacjentów rozsadzamy na \(\displaystyle{ n}\) krzesłach, ostatnie puste, i tu jest \(\displaystyle{ h(n,k)}\) możliwości, potem rozsadzamy \(\displaystyle{ k-1}\) pacjentów na \(\displaystyle{ n-1}\) krzesłach, przedostatnie jest puste, a ostatnie zajęte i mamy: \(\displaystyle{ h(n-1,k-1)}\) możliwości.
Pamiętamy, że ostatnie krzesło zajęte, ale można na ostatnim krześle posadzić każdego z \(\displaystyle{ k}\) pacjentów,
więc dlatego mamy ten czynnik!
Raczej działa...
Teraz niech jakiś extramocny lub słabosilny zamieni go na wzór jawny!
A swoją drogą czemu ci pacjenci nie mogą siedzieć koło siebie czy może są zadżumieni ? jakaś epidemia??
\(\displaystyle{ h(1,1)=1}\)
Dla dwóch krzeseł masz tylko jednego pacjenta:
\(\displaystyle{ h(2,1)=2}\)
Dla trzech krzeseł masz albo jednego albo dwóch pacjentów, którzy mogą permutować:
\(\displaystyle{ h(3,1)=3}\)
\(\displaystyle{ h(3,2)= 1 \cdot 2!}\)
Dla czterech krzeseł może być jeden lub dwa pacjenty:
\(\displaystyle{ h(4,1)=4}\)
\(\displaystyle{ h(4,2)=3 \cdot 2!}\)
itd...
Ogólnie teraz łatwo zauważyć, że:
\(\displaystyle{ h(n,1)=n}\)
Pacjentów musi być mniej lub równo niż połowa krzeseł dla parzystych albo maksymalnie dla nieparzystych może być:
\(\displaystyle{ k=\left[ \frac{n}{2} \right] +1}\)
bo wtedy:
\(\displaystyle{ h(n,k)=0}\)
Wyciągając wzór ogólny otrzymamy:
\(\displaystyle{ h(n+1,k)=h(n,k)+k \cdot h(n-1,k-1)}\)
Wzór ogólny tak należy rozumieć:
Mamy \(\displaystyle{ k}\) pacjentów i \(\displaystyle{ n+1}\) krzeseł najpierw wszystkich pacjentów rozsadzamy na \(\displaystyle{ n}\) krzesłach, ostatnie puste, i tu jest \(\displaystyle{ h(n,k)}\) możliwości, potem rozsadzamy \(\displaystyle{ k-1}\) pacjentów na \(\displaystyle{ n-1}\) krzesłach, przedostatnie jest puste, a ostatnie zajęte i mamy: \(\displaystyle{ h(n-1,k-1)}\) możliwości.
Pamiętamy, że ostatnie krzesło zajęte, ale można na ostatnim krześle posadzić każdego z \(\displaystyle{ k}\) pacjentów,
więc dlatego mamy ten czynnik!
Raczej działa...
Teraz niech jakiś extramocny lub słabosilny zamieni go na wzór jawny!
A swoją drogą czemu ci pacjenci nie mogą siedzieć koło siebie czy może są zadżumieni ? jakaś epidemia??
-
squared
- Użytkownik
- Posty: 1017
- Rejestracja: 21 mar 2009, o 11:11
- Płeć: Mężczyzna
- Podziękował: 167 razy
- Pomógł: 152 razy
Rozsadzenia pacjentów
Może epidemia . Chociaż zwykle ludzie mają tendencje do siadania co drugie krzesło (póki można).arek1357 pisze:A swoją drogą czemu ci pacjenci nie mogą siedzieć koło siebie czy może są zadżumieni ? jakaś epidemia??
-
arek1357
- Użytkownik
- Posty: 5736
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Rozsadzenia pacjentów
W sumie masz rację gdziekolwiek się siada nikt nie chce siedzieć koło innej osoby i szuka miejsca dalej.
W takim układzie zadanie ma sens. Bo wynika to z naszej psychiki.
W takim układzie zadanie ma sens. Bo wynika to z naszej psychiki.