 |
Coders' city
Nasza pasja to programowanie!
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Kayne
Dołączył: 25 Sie 2005
Posty: 236
|
 Wysłany: Pon Lis 07, 2011 3:16 pm Temat postu: Magiczny kwadrat - jak go stworzyć? |
  |
|
Witam,
Zastanawiałem się dłuższy czas, czy zakładać temat w tym dziale, czy w C i C++, ale ostatecznie stwierdziłem, że bardziej potrzebuję teoretycznej wiedzy, czy naprowadzenia na rozwiązanie. Póki co, nie mam problemów w kodzie, bo go nie mam ;)
Do rzeczy: W jaki sposób wygenerować magiczny kwadrat? Nie mogłem w sieci znaleźć żadnych ciekawych, mądrych sposobów ani algorytmów na to. Jedyne co mi przychodzi na myśl, to generowanie kwadratów z losowymi liczbami i sprawdzanie, czy są to magiczne kwadraty, ale... Jest to strasznie nie wydajne rozwiązanie i musi istnieć coś lepszego.
Ktoś ma może jakieś pomysły?
|
|
| Powrót do góry |
|
 |
|
|
marcin_an
Site Admin
Dołączył: 26 Maj 2005
Posty: 17278
Skąd: z drugiej strony Kabla
|
|
| Powrót do góry |
|
|
hurgadion
Dołączył: 06 Kwi 2011
Posty: 143
Skąd: Kraków
|
| Wysłany: Pon Lis 07, 2011 6:25 pm Temat postu: |
|
|
Witam,
może losowe sposoby nie są zbyt wydajne, ale przy tworzeniu kwadratu magicznego 3x3 losowy sposób działa dość szybko, o ile zastosujemy pomocniczą funkcję losującą unikalne liczby z zakresu 1-9 (funkcja RndInt na podstawie Walkenbacha). Moje rozwiązanie jest w VBA, ale pewnie mozna go spokojnie przenieść na inny język programowania. Kod ma postać:
| Kod: |  
 Sub MagicalSquare()
 Dim tbl(), a&, b&, c&, d&, e&, f&, g&, h&
 ReDim tbl(1 To 9)
 Randomize
 For i = 1 To 100000
 tbl = RndInt
a = tbl(1) + tbl(2) + tbl(3)
b = tbl(4) + tbl(5) + tbl(6)
c = tbl(7) + tbl(8) + tbl(9)
d = tbl(1) + tbl(4) + tbl(7)
e = tbl(2) + tbl(5) + tbl(8)
f = tbl(3) + tbl(6) + tbl(9)
g = tbl(1) + tbl(5) + tbl(9)
h = tbl(3) + tbl(5) + tbl(7)
If a = 15 And b = 15 And c = 15 And d = 15 And e = 15 And f = 15 And g = 15 And h = 15 Then
Cells(1, 1).Value = tbl(1)
Cells(1, 2).Value = tbl(2)
Cells(1, 3).Value = tbl(3)
Cells(2, 1).Value = tbl(4)
Cells(2, 2).Value = tbl(5)
Cells(2, 3).Value = tbl(6)
Cells(3, 1).Value = tbl(7)
Cells(3, 2).Value = tbl(8)
Cells(3, 3).Value = tbl(9)
Exit Sub
End If
Next i
End Sub
Function RndInt()
Dim V() As Variant, Val As Variant
Dim i&, j&, r&, c&, a&
Dim t1 As Variant, t2 As Variant
Randomize
a = 9
ReDim V(1 To a)
ReDim Val(1 To 2, 1 To a)
For i = 1 To a
Val(1, i) = Rnd
Val(2, i) = i
Next i
For i = 1 To a
For j = i + 1 To a
If Val(1, i) > Val(1, j) Then
t1 = Val(1, j)
t2 = Val(2, j)
Val(1, j) = Val(1, i)
Val(2, j) = Val(2, i)
Val(1, i) = t1
Val(2, i) = t2
End If
Next j
Next i
i = 0
For r = 1 To a
i = i + 1
V(i) = Val(2, i)
Next r
RndInt = V
End Function
|
Funkcja RndInt jest pomocnicza, natomiast główne makro nie jest optymalne, pozdrawiam.
| Opis: |
|
Pobierz |
| Nazwa pliku: |
MagicalSquare.rar |
| Wielkość pliku: |
10.16 KB |
| Pobierano: |
26 raz(y) |
Ostatnio zmieniony przez hurgadion dnia Pon Lis 07, 2011 9:23 pm, w całości zmieniany 1 raz |
|
| Powrót do góry |
|
|
Hashedone
Dołączył: 23 Sie 2008
Posty: 853
|
| Wysłany: Pon Lis 07, 2011 7:36 pm Temat postu: |
|
|
3x3 to przypadek niemalże trywialny, wygeneruj 4x4. W swi-prologu z clpfd (technologia więzów dla skończonych zbiorów naturalnych) generowało się kilka sekund (na dwurdzeniowym P6000 bodajże), a z doświadczenia wiem, że trudno stworzyć samemu coś bardziej wydajnego dla tego typu problemów (co nie znaczy że się nie da). 5x5 mi się wygenerować w ogóle nie udało (jak będę miał chwilę to spróbuję w jakimś szybszym prologu bo to faktycznie nie jest najwydajniejsza implementacja). Życzę powodzenia, ale nie wiem czy są na to wydajne i w miarę proste algorytmy;)
_________________
PWr, WPPT, Informatyka
"Two or more? - use a for", Dijkstra |
|
| Powrót do góry |
|
|
Kayne
Dołączył: 25 Sie 2005
Posty: 236
|
| Wysłany: Pon Lis 07, 2011 8:42 pm Temat postu: |
|
|
hurgadion, dzięki, ale z 3x3 kwadratem bym sobie szybko poradził (świetny sposób Yang Hui). Problem w tym, że musi się sprawdzać dla każdych ;)
Hashedone, tutaj bardziej chodzi o sam zapis kodu, jakiś algorytm niż fakt, czy jest super wydajny (no, może po za tą pełną losowością... ;) ).
marcin_an, szukałem na angielskiej wiki, ale nie znalazłem zbytnio niczego, co by mi pomogło - albo umiałbym zakodować. Właśnie przejrzałem drugi wynik z google... I też zbytnio mi nie pomógł. Po prostu nie widzę, jak miałbym to w C napisać.
Dlatego szukam dalej rozwiązań, które sprawdzają się dla dowolnego n.
|
|
| Powrót do góry |
|
|
hurgadion
Dołączył: 06 Kwi 2011
Posty: 143
Skąd: Kraków
|
| Wysłany: Pon Lis 07, 2011 9:56 pm Temat postu: |
|
|
W sieci PL nie za wiele jest na temat algorytmizacji tego problemu, znalazłem coś takiego: http://math.uni.lodz.pl/~radmat/sztuczna/Projekt3.pdf więc chyba się da dla n > 4, chyba że prowadzący rzucił otwarty problem studentom :)
Hashedone: Odpaliłem losową metodę dla kwadratu 4x4, po kilkunastu minutach bez rezultatu, jutro jak będę miał humor, to odpalę kompa może na nieco dłużej... :)
|
|
| Powrót do góry |
|
|
Mgr.Dobrowolski
Dołączył: 18 Cze 2006
Posty: 475
|
| Wysłany: Pon Lis 07, 2011 11:22 pm Temat postu: |
|
|
| prawiem pewny, że widziałem na IOCCC, a tam programy są raczej zwięzłe.
|
|
| Powrót do góry |
|
|
Hashedone
Dołączył: 23 Sie 2008
Posty: 853
|
| Wysłany: Wto Lis 08, 2011 11:13 am Temat postu: |
|
|
@hugarion - źle się wyraziłem. Da się to zrobić i to całkiem szybko, jest o tym na drugim wyniku spod linku marcin_ana. Problem jest inny - dla mnie "algorytm generowania X" jest fajny dopiero wtedy, kiedy mogę za pomocą tego algorytmu wygenerować wszystkie X. Okazuje się że można to zrobić całkiem nieźle tą metodą której używałem przy użyciu lepszego prologa - w GNU Prologu na kwadrat 16x16 czekałem niecałe 26s. Podejżewam że yap byłby jeszcze szybszy, ale nie chce mi się ogarniać jego bibliteki do clpfd.
Co do algorytmu to jest w sumie prosty. Niech Square będzie tablicą nxn zbiorów liczb naturalnych (te zbiory będziemy nazywali dziedzinami). Początkowo każdy element Square zawiera wszystkie liczby z przedziału [1; n*n]. Weźmy sobie funkcję:
| Kod: |
function magic_matrix(Square)
1. Zawęź wszystkie dziedziny ze Square
2. Jeśli któraś dziedzina jest pusta, zwróć FAIL
3. Jeśli wszystkie dziedziny są jednoelementowe, zwróć Square
4. D = najmniejsza nie-jednoelementowa dziedzina Square
5. X = losowy element z D
6. NextSquare = Square, z zamienioną dziedziną D na {X}
7. Result = magic_matrix(NextSquare)
8. Jeśli Result != FAIL, zwróć Result
9. Usuń X z D
10. Idź do (2)
|
Jeśli można wywołać tę funkcję tak, aby zaczęła się dokładnie od miejsca gdzie ostatnio zwróciła wartość (wraz z kompletnym zachowaniem stosu), zwróci nam w końcu wszystkie możliwe kwadraty. W tym wszystkim najważniejszy jest punkt (1). Na czym to polega? Powiedzmy sobie że szukamy trzech liczb A, B, C, każda z przedziału [1;10] takich, że A + B + C = 20. Początkowo dziedziny A, B, C = [1; 10]. Jednak jeśli założymy że dziedziną A = {1}, to dziedziny B, C = [9; 10], bo jeśli pod którąkolwiek z tych zmiennych będzie coś < 9, to nie da rady dobrać drugiej liczby żeby warunek był spełniony. Dla magicznych kwadratów będziesz miał bardzo podobnie - dla każdego pola trzeba określić liczby, które jeszcze się mogą tam znaleźć. To taki uproszczony opis technologii więzów, polecam poczytać. Z góry uprzedzę że nie wiem czy to jest najlepsza metoda - wiem że działa i to całkiem nieźle i uważam ją za najlepsze podejście do problemu (przede wszystkim dla tego że algorytm jest bardzo ogólny i nie trzeba go całego pisać, tylko wystarczy wziąść do ręki odpowiednie narzędzie).
Jeszcze takie uwagi co do dwóch punktów:
(4) - nie zawsze bierze się najmniejszą dziedzinę. Można brać największą, najbardziej związaną (czyli taką, na której jest nawięcej warunków, można je brać w z góry ustalonej kolejności, lub nawet losowo. Jednak w moich próbach najlepsze rezultaty dało branie najmniejszej dziedziny (generalnie dla większości problemów jest to najmniejsza heurystyka, czasem przegrywa z braniem najbardziej związanej dziedziny)
(5) - znowu, nie zawsze losowy. Można brać najmniejszy, największy, środkowy, średni... Znowu metodą sprawdzania różnych heurystyk doszedłem do tego, że ta daje najlepsze rezultaty (i znowu - jest to typowe dla problemów, gdzie wyniki wyglądają na chaotyczne).
Oczywiście przedstawiony algorytm daje bardzo duże pole do optymalizacji. Można pozbyć się rekursji, można przede wszystkim na masę sposobów zrealizować punkt (1), jednak ten post i tak jest już za długi:D Polecam doczytać o technologii więzów i programowaniu w logice;)
_________________
PWr, WPPT, Informatyka
"Two or more? - use a for", Dijkstra |
|
| Powrót do góry |
|
|
hurgadion
Dołączył: 06 Kwi 2011
Posty: 143
Skąd: Kraków
|
| Wysłany: Czw Lis 10, 2011 7:08 pm Temat postu: |
|
|
Podszedłem do tematu hobbystycznie i napisałem programik wyszukujący kwadrat magiczny 4 x 4, działa nie za szybko, ale wyszukuje skutecznie (na dziesięć prób wyszukuje średnio 5,5 minuty). Kod jest nieco inny jak wyżej (plus funkcja RndInt()), może kogoś zainteresuje ten sposób:
| Kod: |
Sub Kwadrat4()
Dim z&, tab16(), tbl12(), tbl8(), a1&, a2&, a3&, a4, a5&, a6&, tbl(), i&, m&
Dim tbl1(), tbl2(), tbl3(), tbl4(), t(), t1(), t2(), t3(), t4(), w As Single, s As Single
Randomize
dalej:
z = 1
Do While z <> 0
tab16 = RndInt(16)
a1 = tab16(1) + tab16(2) + tab16(3) + tab16(4)
If a1 = 34 Then z = 0
Loop
ReDim tbl1(1 To 4)
For i = 1 To 4
tbl1(i) = tab16(i)
Next i
ReDim tbl12(1 To 12)
For i = 1 To 12
tbl12(i) = tab16(i + 4)
Next i
ReDim tablica(1 To 12)
z = 1
Do While z <> 0
tbl = RndInt(12)
tablica = tbl12
For i = 1 To 12
tbl12(i) = tablica(tbl(i))
Next i
a1 = tbl12(1) + tbl12(2) + tbl12(3) + tbl12(4)
If a1 = 34 Then z = 0
Loop
ReDim tbl2(1 To 4)
For i = 1 To 4
tbl2(i) = tbl12(i)
Next i
ReDim tbl8(1 To 8)
For i = 1 To 8
tbl12(i) = tbl12(i + 4)
Next i
ReDim tablica(1 To 8)
z = 1
Do While z <> 0
tbl = RndInt(8)
tablica = tbl12
For i = 1 To 8
tbl8(i) = tablica(tbl(i))
Next i
a1 = tbl8(1) + tbl8(2) + tbl8(3) + tbl8(4)
If a1 = 34 Then z = 0
Loop
ReDim tbl3(1 To 4)
ReDim tbl4(1 To 4)
For i = 1 To 4
tbl3(i) = tbl8(i)
tbl4(i) = tbl8(i + 4)
Next i
z = 1
m = 0
Do While z <> 0
t1 = RndInt(4)
t2 = RndInt(4)
t3 = RndInt(4)
t4 = RndInt(4)
t = tbl1
For i = 1 To 4
tbl1(i) = t(t1(i))
Next i
t = tbl2
For i = 1 To 4
tbl2(i) = t(t2(i))
Next i
t = tbl3
For i = 1 To 4
tbl3(i) = t(t3(i))
Next i
t = tbl4
For i = 1 To 4
tbl4(i) = t(t4(i))
Next i
a1 = tbl1(1) + tbl2(1) + tbl3(1) + tbl4(1)
a2 = tbl1(2) + tbl2(2) + tbl3(2) + tbl4(2)
a3 = tbl1(3) + tbl2(3) + tbl3(3) + tbl4(3)
a4 = tbl1(4) + tbl2(4) + tbl3(4) + tbl4(4)
a5 = tbl1(1) + tbl2(2) + tbl3(3) + tbl4(4)
a6 = tbl1(4) + tbl2(3) + tbl3(2) + tbl4(1)
If Application.Min(a1, a2, a3, a4, a5, a6) = 34 And Application.Max(a1, a2, a3, a4, a5, a6) = 34 Then z = 0
m = m + 1
If m > 200000 Then GoTo dalej:
Loop
Cells(1, 1).Resize(, 4) = tbl1
Cells(2, 1).Resize(, 4) = tbl2
Cells(3, 1).Resize(, 4) = tbl3
Cells(4, 1).Resize(, 4) = tbl4
End Sub
|
PS. Kupiłem sobie Hashedone książkę o Prologu, czekam na przesyłkę :)
| Opis: |
|
Pobierz |
| Nazwa pliku: |
Kwadrat.mag.4x4.rar |
| Wielkość pliku: |
12.92 KB |
| Pobierano: |
13 raz(y) |
|
|
| Powrót do góry |
|
|
|
|
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum
|
Debug: strone wygenerowano w 0.09393 sekund, zapytan = 9
|
Pomoc
Szukaj
Użytkownicy
Grupy
Rejestracja
Profil
Zaloguj się, by sprawdzić wiadomości
