problem zwrotnicy kolejowej

[Deadeye 0]

witam

mam do rozwiazania pewien problem, i nie jestem w stanie poniewaz nie mam zadnej wiedzy z kombinatoryki. moze pomozecie?

 

zadanie:

mamy 2 kolejki i stos:

kolejka1	   kolejka2
		s
		t
		o
		s

na poczatku w kolejce1 mamy dana ilosc rozroznialnych ( np ponumerowanych) obiektow. mozemy wykonac dwa dzialania - przeniesc z konca kolejki1 obiekt do stosu, lub (jesli stos nie jest pusty) przeniest ostatni dodany do stosu element do drugiej kolejki (przy okazji odslaniajac kolejny element na stosie - zgodnie z zasada dzialania stosu. czyli np gdy odlozymy 2 obiekty na stos, a pozniej przelozymy je do kolejki2 to beda w odwrotnej kolejnosci).

pytanie: ile jest kombinacji w jakich mozna ulozyc wszystkie elementy w kolejce2?

 

moj tok rozumowania:

jakakolwiek zmiana w kolejnosci przenoszenia obiektow powoduje inne ulozenie koncowe, wiec wystarczy zbadac ile lacznie mozliwosci przenoszenia jest. zeby to przeliczyc wystarczy brac pod uwage ilosc obiektow w kolejnce1 (na poczatku n) i na stosie (na poczatku 0). pierwsze dzialanie (przeniesienie na stos) jest mozliwe jesli kolejka1 > 0 i zmniejsza o 1, jednoczesnie zwiekszajac o 1 stos. drugie dzialanie jest mozliwe jesli stos >0 i zmniejsza stos o 1. proces sie zakancza gdy stos i kolejka1 sa puste. na poczatku mamy oczywiscie jedna mozliwosc - wyjecie z kolejki1 do stosu. w pozniejszych krokach mozliwe sa 3 sytuacje:

1) stos pusty - jedna mozliwosc wyboru, w nastepnym kroku 2 mozliwosci (bo stos juz bedzie wypelniony).

2) stos niepusty i kolejka1 niepusta - mamy 2 mozliwosci

3) kolejka1 pusta - do konca zostaje nam jedna mozliwosc - pobieranie ze stosu az bedzie pusty, wtedy koniec.

 

teraz tylko pytanie - jak obliczyc, ile razy nastapi ktora sytuacja, zeby moc obliczyc wzor na ogolny wzrost mozliwosci po kolejnych krokach? najwiekszym problemem jest 3cia sytucja - bo sprawia ze do konca bedzie juz tylko jedna mozliwosc.

 

 

moj tok rozumowania moze byc bardzo pokrecony, dlatego nie ma sensu na niego zwracac uwagi w zalaczniku wrzucam obrazek pokazujacy mozliwe rozwiazania dla n=3 - w kazdym punkcie pierwsza liczba to liczba obiektow w kolejce1, a druga to liczba obiektow na stosie. galezie prowadza do sytuacji, do jakiej moze dojsc w danym momencie. liczba galezii na samym dole to rozwiazanie zadania.

 

zrobic algorytm ktory rozwiazuje to zadanie jest banalnie, ale stworzyc wzor juz nie. czy ktos bylby w stanie mi pomoc? bylbym bardzo wdzieczny

wyniki dla pierwszej 12stki (policzone przez moj program, wiec moga byc bledne, choc wydaja sie byc poprawne - na pewno sa poprawne dla pierwszych 4)

1 - 1

2 - 2

3 - 5

4 - 14

5 - 42

6 - 132

7 - 429

8 - 1430

9 - 4862

10 - 16796

11 - 58786

12 - 208012

[Sławek 0]

A od czego masz encyklopedię ciągów?

http://www.research.att.com/~njas/sequence...language=polish

 

I wiki:

http://en.wikipedia.org/wiki/Catalan_number