szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 6 lis 2015, o 20:08 
Użytkownik

Posty: 1019
Witam, mam do rozwiązania następujące zadanie

Niech h(k,n) będzie liczbą rozsadzeń w określonym porządku k pacjentów w taki sposób w poczekalni, w której jest n krzeseł w taki sposób, aby żaden pacjent nie siedział bezpośrednio obok drugiego. Znaleźć zależność rekurencyjną dla h(k,n). Jakieś wskazówki?
Góra
Mężczyzna Offline
PostNapisane: 6 lis 2015, o 23:22 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Dla jednego krzesła masz:

h(1,1)=1

Dla dwóch krzeseł masz tylko jednego pacjenta:

h(2,1)=2

Dla trzech krzeseł masz albo jednego albo dwóch pacjentów, którzy mogą permutować:

h(3,1)=3

h(3,2)= 1 \cdot 2!

Dla czterech krzeseł może być jeden lub dwa pacjenty:

h(4,1)=4

h(4,2)=3 \cdot 2!

itd...

Ogólnie teraz łatwo zauważyć, że:

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ć:

k=\left[  \frac{n}{2}  \right] +1

bo wtedy:

h(n,k)=0

Wyciągając wzór ogólny otrzymamy:

h(n+1,k)=h(n,k)+k \cdot h(n-1,k-1)

Wzór ogólny tak należy rozumieć:

Mamy k pacjentów i n+1 krzeseł najpierw wszystkich pacjentów rozsadzamy na n krzesłach, ostatnie puste, i tu jest h(n,k) możliwości, potem rozsadzamy k-1 pacjentów na n-1 krzesłach, przedostatnie jest puste, a ostatnie zajęte i mamy: 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 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??
Góra
Mężczyzna Offline
PostNapisane: 7 lis 2015, o 13:59 
Użytkownik

Posty: 1019
arek1357 napisał(a):
A swoją drogą czemu ci pacjenci nie mogą siedzieć koło siebie czy może są zadżumieni ? jakaś epidemia??

Może epidemia ;). Chociaż zwykle ludzie mają tendencje do siadania co drugie krzesło (póki można).
Góra
Mężczyzna Offline
PostNapisane: 8 lis 2015, o 20:20 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość sposobów rozsadzenia osób  fa1thly  1
 [Teoria grup] rozsadzenia wokół stołu  matinf  1
 Analiza grupy pacjentów  zatonski  3
 [C++] Baza Pacjentów  Leogict  2
 Weryfikacja hipotezy - czas snu pacjentów  El pytacz  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl