Problem z algorytmem losującym

[bartman 0]

Witam proszę o pomoc z algorytmem

Mianowicie muszę napisać program który będzie losował rozmieszczenie zawodników przy stolikach w taki sposób że:

Mam grę w której bierze udział min 16 zawodników (liczba zawodników zwiększa się co cztery) i liczbę stołów = liczba graczy / 4.

Gra składa się z 5 rund. W pierwszej rundzie rozlosowujemy po 4 zawodników na każdy stół, w następnej rundzie dalej rozlosowujemy tych zawodników pomiędzy te stoły ale już w taki sposób aby nikt ze sobą nie grał dwa razy.

 

I tu pojawia się moje pytanie jak to zrobić??

Myślałem żeby stworzyć dwie tablice: jedna trójwymiarowa przechowująca rozlosowanych zawodników w danej rundzie czyli Tablica[ ilość_rund, ilość_stołów, zawodnik przy stole] no i drugą tablice w której była by przechowywana lista osób dla każdego gracza z którym może jeszcze grać. Niestety pogram się zawiesza gdyż zawsze dochodzi do takiego momentu (zwykle w 5 rundzie) że pozostaje do rozlosowania np jeszcze pięciu zawodników ale oni nie mogą już ze sobą grać gdyż w poprzednich rundach ze sobą grali no i nie ważne ile razy bym powtarzał losowanie zawsze dochodzi do tego momentu.

 

Z góry wielkie dzięki za pomoc

[Gość Clamoor]

Niezbyt mam czas długo mysleć ale zrobił bym to tak:

 

tablica Gracze N elementowa

 

x kolejni gracze az do N

 

tablica[x][0] zawierajaca true / false (1 / 0) oznaczajaca czy w danym losowaniu juz przydzielony

tablica[x][1] wskaźnik do listy graczy z którymi juz grał

 

czyli wygladało by to tak:

 

0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

 

nastepnie dla 1 gracza losowałbym 3 z którymi nie grał, i zaznaczał odpowiednio ze juz sa wylosowani

1  0  0  0  1  0  1  0  0  0   1   0  0  0  0  0  <= tablica[x][0]
1  2  3  4  5  6  7  8  9  10  11  12 13 14 15 16 <= tablica[x] 
5           1     1            1                  <= listy 
8           8     5            5
11          11    11           8

 

dla kolejnego sprawdzając czy dany juz nie był wylosowany

 

1  1  1  0  1  0  1  0  0  1   1   0  0  0  0  1  <= tablica[x][0]
1  2  3  4  5  6  7  8  9  10  11  12 13 14 15 16 <= tablica[x] 
5  16 2     1     1        2   1               2  <= listy
8  10 10    8     5        3   5               3
11 3  16    11    11       16  8               10

 

aż skończymy 1 losowanie do końca

 

1  1  1  1  1  1  1  1  1  1   1   1  1  1  1  1  <= tablica[x][0]
1  2  3  4  5  6  7  8  9  10  11  12 13 14 15 16 <= tablica[x] 
5  16 2  12 1  9  1  4  6  2   1   4  6  4  6  2  <= listy
8  10 10 8  8  13 5  12 13 3   5   8  9  12 9  3
11 3  16 14 11 15 11 14 15 16  8   14 15 8  13 10

 

nastepnie zerujemy tablica[x][0] celem rozpoczecia kolejnej rundy

sprawdzajac oczywiscie dla gracza x czy dany gracz juz nie został wylosowany oraz czy nie znajduje sie w liście juz rozegranych

1  1  0  0  0  0  0  0  0  0   0   1  0  0  0  1<= tablica[x][0]
1  2  3  4  5  6  7  8  9  10  11  12 13 14 15 16 <= tablica[x] 
5  16 2  12 1  9  1  4  6  2   1   4  6  4  6  2  <= listy
8  10 10 8  8  13 5  12 13 3   5   8  9  12 9  3
11 3  16 14 11 15 11 14 15 16  8   14 15 8  13 10
16 1                               1           1
12 12                              2           12
2  16                              16          2

 

itd... az do zapelnienia 5 rund

 

runda nr

dla n = 16

1: n-1 -0  = 15 graczy
2: n-1 -3  = 12
3: n-1 -6  = 9
4: n-1 -9  = 6
5: n-1 -12 = 3

 

dla 16 graczy jest mozliwe rozegraniu 5 rund wiec dla wiekszych n jest to tym bardziej mozliwe ...

mam nadzieje ze nigdzie sie nie pomysliłem i ze to jest w miare przejrzyste

 

P.S. pamięciowo to stoi + - n^2, obliczeniowo ... pesymistycznie dość fatalnie , optymistycznie nieźle, realnie ... mniej niz n^2 mysle ... ale jak mowie oceniam na szybko

Edytowane 19 Październik 2008 przez Clamoor

[bartman 0]

Wielkie dzięki za fatyge i pomoc ale mam jedno spostrzeżenie, które wydaje mi się, że w Twoim algorytmie też może mieć miejsce a mianowicie, może dojść (mi się tak dzieje przy zbliżonej implementacji) do momentu w którym mam jeszcze wolnych graczy ale one już grały z osobami przy danym stoliku lub z drugiej strony mam do wylosowania osoby z którymi "x" użytkownik jeszcze nie grał ale one już w tej rundzie grały. I jak się przed tym zabezpieczyć no bo przecież nie można zrobić żeby powtarzał losowanie bez końca ?

[Gość Clamoor]

hmmm faktycznie pominałem ze maja grac przy inych stolikach, ja jedynie czwórki graczy upewniałem sie zeby były inne ...

 

hmm musiałbys chyba poazac dokładna tresc wejscia i wyjscia (szczegolnie wyjscia) ... bo inaczej to nie wiem co jest najwazniejsze

 

edit:

w następnej rundzie dalej rozlosowujemy tych zawodników pomiędzy te stoły ale już w taki sposób aby nikt ze sobą nie grał dwa razy.

chociaz z tego wynika ze tylko gracze nie moga sie powtarzac ...

 

sprecyzuj dane

Edytowane 19 Październik 2008 przez Clamoor

[bartman 0]

Miałem na myśli to że przy zmianie rundy muszę się upewnić czy dany gracz x nie grał już w wszystkich poprzednich rundach z graczem y no i oczywiste jest żeby gracz x nie grał w danej rundzie przy dwóch stolikach. Mam nadzieje że teraz to już w miare precyzyjnie napisałem, załączam jeszcze "ręcznie" rozpisane rozstawienie zawodników

 

[Gość Clamoor]

a) jak bardzo sie to pali daj przykładowe dane wejsciowe i wyjściowe jak znajde chwile wiecej moze sie pobawie

[bartman 0]

Mi się nie spieszy z tym, mam jeszcze 2 tygodnie na to.

Dane wejściowe liczby od 1 do min 16 max 100 (z możliwością wyboru zakresu) - odzwierciedlające danych graczy .

Dane wyjściowe (najlepiej tablica trójwymiarowa) z rozlosowanymi liczbami w w/w sposób

 

Byłbym wdzięczny za pomoc gdyż mi już pomysły na to się wyczerpały

 

Pozdrawiam