Rysuj
| form pen ile i |
form := Display.
pen := Pen newOnForm: form.
pen up.
form fillWhite.
ile := lab size.
i := 1.
[i <= ile] whileTrue:
[
pen goto: (lab at: i).
pen down.
pen goto: (lab at: (i+1)).
pen up.
i := i + 2.
]
pen goto: 0@0.
pen down.
pen goto: (10*xsize)@0.
pen goto: (10*xsize)@(10*(ysize // 2)).
pen goto: 0@(10*(ysize // 2)).
pen goto: 0@0.
pen up.
pen goto: 0@(10*((ysize // 2) +1)).
pen down.
pen goto: (10*xsize)@(10*((ysize // 2) +1)).
pen goto: (10*xsize)@(10*ysize).
pen goto: 0@(10*ysize).
pen goto: 0@(10*((ysize // 2) +1)).
pen up.
pen goto: 0@(10*((ysize // 2) +1) + 1).
pen down.
pen goto: (10*xsize)@(10*((ysize // 2) +1) + 1).
pen up.
pen goto: 0@(10*((ysize // 2)) - 1).
pen down.
pen goto: (10*xsize)@(10*((ysize // 2)) - 1).
pen up.
[Sensor keyboardPressed] whileFalse: [].
Display restore.
Stworz: x y: y
| r v |
xsize := x.
ysize := y.
r := Random new.
lab := OrderedCollection new.
0 to: (x-1) do:
[:x1 |
0 to: (y-1) do:
[:y1 |
(y1 = (y // 2)) ifFalse:
[
v := r nextInt: 5.
(v > 2) ifTrue:
[ lab addLast: (10*x1)@(10*y1)
lab addLast: (10*(x1+1))@(10*y1) ].
(v < 4) ifTrue:
[ lab addLast: (10*x1)@(10*y1)
lab addLast: (10*x1)@(10*(y1+1)) ].
].
].
].
28 czerwiec 2009
Labirynt cz II
Normalnie bym nie pisał - bo sesja, ale udało mi się odratować kod źródłowy słynnego już labiryntu. Oto i on:
27 maj 2009
Labirynt
Zadanie brzmiało:
Zaprogramuj klasę generującą i rysującą labirynt o rozmiarze zadanym podczas tworzenia obiektu. Przyjmij że w labiryncie są tylko dwa wejścia oraz że istnieje droga łącząca te dwa wejścia.
Zadanie rozwiązałem po najmniejszej linii oporu. Labirynty generowane przez mój algorytm wyglądały mniej więcej tak:
Prowadzący chciał mnie za to poćwiartkować.. Ale przyznał, że mój algorytm spełnia specyfikację zadania (jest to labirynt z dwoma wejściami taki, że istnieje ścieżka między nimi) i skończyło się na zaliczeniu programu na maksymalną ilość punktów.
Jako feature dodałem wysoce specjalistyczny algorytm sztucznej inteligencji znajdujący rozwiązania tego typu labiryntów 8)
Zaprogramuj klasę generującą i rysującą labirynt o rozmiarze zadanym podczas tworzenia obiektu. Przyjmij że w labiryncie są tylko dwa wejścia oraz że istnieje droga łącząca te dwa wejścia.
Zadanie rozwiązałem po najmniejszej linii oporu. Labirynty generowane przez mój algorytm wyglądały mniej więcej tak:
Prowadzący chciał mnie za to poćwiartkować.. Ale przyznał, że mój algorytm spełnia specyfikację zadania (jest to labirynt z dwoma wejściami taki, że istnieje ścieżka między nimi) i skończyło się na zaliczeniu programu na maksymalną ilość punktów.Jako feature dodałem wysoce specjalistyczny algorytm sztucznej inteligencji znajdujący rozwiązania tego typu labiryntów 8)
Etykiety:
pogadanka
21 maj 2009
Cykl Eulera cz II.
Cyklem Eulera w grafie nazywamy następujące obejście grafu:
- zaczynamy w wybranym przez nas wierzchołku
- obchodzimy graf w ten sposób, że każdą krawędź przechodzimy dokładnie raz
- kończymy na wierzchołku w którym zaczęliśmy.
Jakie warunki musi spełniać graf aby istniał w nim cykl Eulera? Graf przede wszystkim musi być spójny. Jeśli by nie był mogłaby istnieć krawędź do której nie możemy dojść. Ponadto za każdym razem gdy wchodzimy do jakiegoś wierzchołka musimy umieć z niego wyjść. Zatem stopień każdego wierzchołka musi być wielokrotnością dwójki.
Okazuje się, że jeśli graf spełnia te dwa warunki to istnieje w nim cykl Eulera (dowód przez podanie algorytmu Fleury'ego będzie przedstawiony w którejś z kolejnych notek).
Zadanie z winniczkiem wydaje się teraz banalne. Spójność grafu mamy dane w treści zadania. Ponadto każdą krawędź w tym grafie musimy przejść dwukrotnie (ścieżki są dwa razy szersze od kosiarki) - zatem spełniony jest również drugi warunek. Zatem w grafie istnieje cykl Eulera. Ponieważ w zadaniu nie proszą nas o znalezienie tego cyklu, a jedynie o podanie w jakim czasie Winicjusz jest w stanie przejść ten graf, więc odpowiadamy: suma wag na krawędziach przemnożona przez dwa.
- zaczynamy w wybranym przez nas wierzchołku
- obchodzimy graf w ten sposób, że każdą krawędź przechodzimy dokładnie raz
- kończymy na wierzchołku w którym zaczęliśmy.
Jakie warunki musi spełniać graf aby istniał w nim cykl Eulera? Graf przede wszystkim musi być spójny. Jeśli by nie był mogłaby istnieć krawędź do której nie możemy dojść. Ponadto za każdym razem gdy wchodzimy do jakiegoś wierzchołka musimy umieć z niego wyjść. Zatem stopień każdego wierzchołka musi być wielokrotnością dwójki.
Okazuje się, że jeśli graf spełnia te dwa warunki to istnieje w nim cykl Eulera (dowód przez podanie algorytmu Fleury'ego będzie przedstawiony w którejś z kolejnych notek).
Zadanie z winniczkiem wydaje się teraz banalne. Spójność grafu mamy dane w treści zadania. Ponadto każdą krawędź w tym grafie musimy przejść dwukrotnie (ścieżki są dwa razy szersze od kosiarki) - zatem spełniony jest również drugi warunek. Zatem w grafie istnieje cykl Eulera. Ponieważ w zadaniu nie proszą nas o znalezienie tego cyklu, a jedynie o podanie w jakim czasie Winicjusz jest w stanie przejść ten graf, więc odpowiadamy: suma wag na krawędziach przemnożona przez dwa.
Etykiety:
teoria grafów,
Zadania
Subskrybuj:
Posty (Atom)
