Kółko i Krzy?żyk :: 4programmers.net

0

Szukam pomysłu na algorytm f, który każde ułożenie U kółek i krzyżyków na planszy o wymiarach 25x25 przekształca symetrycznie do f(U) takiego, że jeżeli U1 symetryczne do U2 to f(U1)==f(U2).

Dostępne przekształcenia (z przykładami):

Zacznę od dowolnejego, ale ustalonego ułożenia początkowego U0:
|_0|_1|_2|_3|_4|_5|_6|_7|_8|_9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|
_0||||||||||||||||||||||||||
_1||||||||||||||||||||||||||
_2||||||||||||||||||||||||||
_3||||||||XX||||||||||||||||||
_4|||||||XX|OO|XX|OO||||||||||||||||
_5||||||||OO||||||||||||||||||
_6||||||||XX||||||||||||||||||
_7||||||||||||||||||||||||||
_8||||||||||||||||||||||||||
_9||||||||||||||||||||||||||
10||||||||||||||||||||||||||
11||||||||||||||||||||||||||
12||||||||||||||||||||||||||
13||||||||||||||||||||||||||
14||||||||||||||||||||||||||
15||||||||||||||||||||||||||
16||||||||||||||||||||||||||
17||||||||||||||||||||||||||
18||||||||||||||||||||||||||
19||||||||||||||||||||||||||
20||||||||||||||||||||||||||
21||||||||||||||||||||||||||
22||||||||||||||||||||||||||
23||||||||||||||||||||||||||
24|||||||||||||||||||||||||__|

-- Przesunięcie o wektor v
np:
v=(5,8)
U1=mov(U0,v):
|_0|_1|_2|_3|_4|_5|_6|_7|_8|_9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|
_0||||||||||||||||||||||||||
_1||||||||||||||||||||||||||
_2||||||||||||||||||||||||||
_3||||||||||||||||||||||||||
_4||||||||||||||||||||||||||
_5||||||||||||||||||||||||||
_6||||||||||||||||||||||||||
_7||||||||||||||||||||||||||
_8||||||||||||||||||||||||||
_9||||||||||||||||||||||||||
10||||||||||||||||||||||||||
11|||||||||||||XX|||||||||||||
12||||||||||||XX|OO|XX|OO|||||||||||
13|||||||||||||OO|||||||||||||
14|||||||||||||XX|||||||||||||
15||||||||||||||||||||||||||
16||||||||||||||||||||||||||
17||||||||||||||||||||||||||
18||||||||||||||||||||||||||
19||||||||||||||||||||||||||
20||||||||||||||||||||||||||
21||||||||||||||||||||||||||
22||||||||||||||||||||||||||
23||||||||||||||||||||||||||
24|||||||||||||||||||||||||__|

-- Odbicia względem
--- osi OX
np:
U2=sOX(U1):
|_0|_1|_2|_3|_4|_5|_6|_7|_8|_9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|
_0||||||||||||||||||||||||||
_1||||||||||||||||||||||||||
_2||||||||||||||||||||||||||
_3||||||||||||||||||||||||||
_4||||||||||||||||||||||||||
_5||||||||||||||||||||||||||
_6||||||||||||||||||||||||||
_7||||||||||||||||||||||||||
_8||||||||||||||||||||||||||
_9||||||||||||||||||||||||||
10||||||||||||||||||||||||||
11|||||||||||||XX|||||||||||||
12|||||||||||||OO|||||||||||||
13||||||||||||XX|OO|XX|OO|||||||||||
14|||||||||||||XX|||||||||||||
15||||||||||||||||||||||||||
16||||||||||||||||||||||||||
17||||||||||||||||||||||||||
18||||||||||||||||||||||||||
19||||||||||||||||||||||||||
20||||||||||||||||||||||||||
21||||||||||||||||||||||||||
22||||||||||||||||||||||||||
23||||||||||||||||||||||||||
24|||||||||||||||||||||||||__|

--- osi OY
np:
U3=sOY(U2):
|_0|_1|_2|_3|_4|_5|_6|_7|_8|_9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|
_0||||||||||||||||||||||||||
_1||||||||||||||||||||||||||
_2||||||||||||||||||||||||||
_3||||||||||||||||||||||||||
_4||||||||||||||||||||||||||
_5||||||||||||||||||||||||||
_6||||||||||||||||||||||||||
_7||||||||||||||||||||||||||
_8||||||||||||||||||||||||||
_9||||||||||||||||||||||||||
10||||||||||||||||||||||||||
11||||||||||||||XX||||||||||||
12||||||||||||||OO||||||||||||
13||||||||||||OO|XX|OO|XX|||||||||||
14||||||||||||||XX||||||||||||
15||||||||||||||||||||||||||
16||||||||||||||||||||||||||
17||||||||||||||||||||||||||
18||||||||||||||||||||||||||
19||||||||||||||||||||||||||
20||||||||||||||||||||||||||
21||||||||||||||||||||||||||
22||||||||||||||||||||||||||
23||||||||||||||||||||||||||
24|||||||||||||||||||||||||__|

--- prostej y==x
np:
U4=sYX(U3):
|_0|_1|_2|_3|_4|_5|_6|_7|_8|_9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|
_0||||||||||||||||||||||||||
_1||||||||||||||||||||||||||
_2||||||||||||||||||||||||||
_3||||||||||||||||||||||||||
_4||||||||||||||||||||||||||
_5||||||||||||||||||||||||||
_6||||||||||||||||||||||||||
_7||||||||||||||||||||||||||
_8||||||||||||||||||||||||||
_9||||||||||||||||||||||||||
10||||||||||||||||||||||||||
11||||||||||||||OO||||||||||||
12||||||||||||||XX||||||||||||
13||||||||||||XX|OO|OO|XX|||||||||||
14||||||||||||||XX||||||||||||
15||||||||||||||||||||||||||
16||||||||||||||||||||||||||
17||||||||||||||||||||||||||
18||||||||||||||||||||||||||
19||||||||||||||||||||||||||
20||||||||||||||||||||||||||
21||||||||||||||||||||||||||
22||||||||||||||||||||||||||
23||||||||||||||||||||||||||
24|||||||||||||||||||||||||__|

-- Zamiana Kółek na Krzyżyki (a Krzyżyków na Kółka)
np:
U5=zam(U4):
|_0|_1|_2|_3|_4|_5|_6|_7|_8|_9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|
_0||||||||||||||||||||||||||
_1||||||||||||||||||||||||||
_2||||||||||||||||||||||||||
_3||||||||||||||||||||||||||
_4||||||||||||||||||||||||||
_5||||||||||||||||||||||||||
_6||||||||||||||||||||||||||
_7||||||||||||||||||||||||||
_8||||||||||||||||||||||||||
_9||||||||||||||||||||||||||
10||||||||||||||||||||||||||
11||||||||||||||XX||||||||||||
12||||||||||||||OO||||||||||||
13||||||||||||OO|XX|XX|OO|||||||||||
14||||||||||||||OO||||||||||||
15||||||||||||||||||||||||||
16||||||||||||||||||||||||||
17||||||||||||||||||||||||||
18||||||||||||||||||||||||||
19||||||||||||||||||||||||||
20||||||||||||||||||||||||||
21||||||||||||||||||||||||||
22||||||||||||||||||||||||||
23||||||||||||||||||||||||||
24|||||||||||||||||||||||||__|

Plansza jest nieskończona, ale okresowa (powtaża się co 25 pól), więc możliwe są także przesunięcia "poza planszę".
np:
v=(-13,-13);
U6=mov(U5,v):
|_0|_1|_2|_3|_4|_5|_6|_7|_8|_9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|
_0|XX|OO||||||||||||||||||||||OO|XX|
_1|OO|||||||||||||||||||||||||
_2||||||||||||||||||||||||||
_3||||||||||||||||||||||||||
_4||||||||||||||||||||||||||
_5||||||||||||||||||||||||||
_6||||||||||||||||||||||||||
_7||||||||||||||||||||||||||
_8||||||||||||||||||||||||||
_9||||||||||||||||||||||||||
10||||||||||||||||||||||||||
11||||||||||||||||||||||||||
12||||||||||||||||||||||||||
13||||||||||||||||||||||||||
14||||||||||||||||||||||||||
15||||||||||||||||||||||||||
16||||||||||||||||||||||||||
17||||||||||||||||||||||||||
18||||||||||||||||||||||||||
19||||||||||||||||||||||||||
20||||||||||||||||||||||||||
21||||||||||||||||||||||||||
22||||||||||||||||||||||||||
23|XX|||||||||||||||||||||||||
24|OO||||||||||||||||||||||||__|

Wszystkie przedstawione ułożenia U0, U1, U2, U3, U4, U5, U6 są do siebie symetryczne.

0

Jestem co najmniej zdziwiony, że potrafiłeś te działania opisać wzorami, a nie potrafisz wymyślić tak prostych algorytmów....

Przecież są to tylko podstawowe operacje na tablicy i to w dodatku statycznej, a tylko wielokrotnie powtarzanej...

Przesunięcie o wektor jest tylko przesunięciem wszystkich (lub określonych) pól o jakiś index (jeśli nowy index elementu będzie większy od 25 to jest on równy nowy_index-25 (da nam to przesunięcie poza tablicę)).
Symetria i inne przekształcenia są tylko przepisanie tablicy od dołu do góry (i/lub) z prawej do lewej...
Zamiana X->O O->X jest jeszcze prostsza, bo jest to tylko ‘przelecenie’ wszystkich pozycji tablicy i zamienianie każdego X na O i vice versa.

PS> Najlepeij by była to tablica bool`i (lub chociaż char) gdzie np. 0 to O, a 1 to X
PS2> Chyba, że czegoś nie zrozumiałem...
PS3> [code]Na przyszłość używaj znacznika [ code ] [ /code ][/code]

0

Chyba minie nie zrozumiałeś [stuk]

Mam jusz zaprogramowane funkcje mov(U,r), sOX(U), sOY(U), sYX(U), zam(U). Jest to zrobione obiektowo i najbardziej optymalnie :-) jak tylko potrafię, ale nie o to mi chodziło... :-/

Chodzi mi o to by przy pomocy tych funkcji zrobić funkcję, która sprawdzałaby czy podane ułożenia są symetryczne (ale to jeszcze nie wszystko [glowa] ).

Nie ma to być funkcja typu:

bool CzySymetryczne(U1,U2);

ale taka f(U), że (jak jusz napisałem)
f(U1)==f(U2) <==> U1 symetryczne do U2

//to znaczy, że z U1 da się w skończonej liczbie kroków przy pomocy fynkcji mov(U,r), sOX(U), sOY(U), sYX(U), zam(U) uzyskać U2

Potrzebna mi taka funkcja, ponieważ mam zamiar używać jej do zapisu danych dla symetrycznych ułożeń w pliku. Tzn chcĘ zapisywać ile razy podobne ułożenie doprowadziło do zwycięstwa, ile do remisu, a ile do przegranej :-)

Gdybym miał taką funkcję f(U), mógłbym dla każdego Un zapisywać tylko f(Un) i DANE dla n-tego ułożenia. Jak chciałbym znaleźć DANE dla ułożeń symetrycznych np do U6 to wystarczyłoby obliczyć f(U6)... nie musiałbym nic więcej sprawdzać. :d

Przesunięcie o wektor jest tylko przesunięciem wszystkich [...] pól o jakiś index (jeśli nowy index elementu będzie większy od 25 to jest on równy nowy_index-25 (da nam to przesunięcie poza tablicę)).

No nie zupełnie ;-)

index=nowy_index%25;//używając twoich oznaczeń

//a u mnie
struct Tpt{
 short x,y
}

Tpt pt(short _x,short _y){
 Tpt p;
 p.x=_x;
 p.y=_y;
 return p;
}

Tpt operator%(Tpt a,Tpt b){
 while(a.x<0)a.x+=b.x; // to ze wzglendu na nieprawidłowe działanie 
 while(a.y<0)a.y+=b.y; // operatora % na liczbach (short<0) ujemnych
 a.x%=b.x;
 a.y%=b.y;
 return a;
}

 //i teraz
Tpt wspolzedne=nowe_wspolzedne%pt(25,25);

Odp(PS)>
Ja w używam tablicy char'ów (najłatwiej ją wypisać na ekran - muszę używać cout :-P ), lub dwóch tablic zawierających współżędne odpowiednio kółek i krzyżyków (te z kolei zajmóją najmniej pamięci - szczególnie w plikach)

0

index=nowy_index%25;//używając twoich oznaczeń

Skąd ci to do głowy przyszło?? Dzielenie z resztą? Raczej coś takiego:

char delta = index+przesuniecie;
index = ((delta)<0)?(25+(delta)):(((delta)>25)?((delta)-25):(delta));

[Ale mogłem gdzieś zrobić błąd, a nie chce mi sie sprawdzać)

Nie rozumiem... Policz ile jest różnych kombinacji jednego ułożenia, możliwych do zrobienia przy pomocy wymienionych przez ciebie funkcji. Teraz jeśli wiesz jakie są kombinacje, to wycinasz z planszy fragment, którego bokami będą skrajne punkty i obracasz przy pomocy tych funkjci na ileś tam sposobów. Jeśli w kótrymś razie porównywane obrazy pokryją się (OzX, lub XzX a OzO), to wiesz że ten obraz jest symetryczny do danego.

0

1.
Bo jak do mojego wpiszę

nowy_index=10028;

to mi wyjdzie

index=10028%25; // =3

a jak do twojego

delta=10028;

to

index = (10028<0)?(25+10028):((10028>25)?(10028-25):10028);

to jest

index = (false)?10053:((true)?10003:10028);

to jest

index = (true)?10003:10028; // =10003 - nie mieści się na planszy

:-(

2.
Moim zdaniem funkcja f(U) mogłabybyć postaci:

U f(U);

I zwracałaby szczególne ułożenie U0=f(Un) takie, że U0 symetryczne do Un. Problem leży w tym, że nie wiem w jaki napisać algorytm, który wybiera te szczegulne (przydałoby się wymyślić kryteria, które ma ono spełniać [stuk] ) ułożenie U0 ze zbioru ułożeń symetrycznych do Un.

Możnaby również w jakiś sposób "ponumerować" zbiory ułożeń symetrycznych i napisać funkcję postaci

int f(U);

Zwracałaby ona nr i=f(Un) zbioru ułożeń symetrycznych, do którego należy ułożenie Un. Tu problem leży w tym, że nie wiem jak obliczyć ile jest możliwychułożeń niesymetrycznych (nie zakładam że liczba kółek musi być równa liczbie krzyżyków z dokładnością do 2; ) >> nie wiem czy starczy miejsca w int :-/ . Ale nawet jakbym wiedział to nie wiem jak je "ponumerować" [glowa]

ps: nie chciałem tego Od razu pisać, bo może to zasugerować konkretny tok rozumowania (ale nie koniecznie jedyny słuszny); Ktoś może przecież mieć inny pomysł na funkcję zwracającą ten sam wynik dla wszystkich ułożeń symetrycznych, a różny dla dowolnych niesymetrycznych (nie determinuje tu jakiego typu ma być wynik funkcji f(U))

Kółko i Krzy?żyk

1 użytkowników online, w tym zalogowanych: 0, gości: 1

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami