Strona używa cookies (ciasteczek). Dowiedz się więcej o celu ich używania i zmianach ustawień. Korzystając ze strony wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.    X

O algorytmach w życiu codziennym.

Jak wszystkim zaznajomionym w temacie programowania wiadomo, najważniejsze są algorytmy. To dzięki algorytmice posiadamy coraz to lepsze rozwiązania problemów w programowaniu.

Na studiach nauczyłem się już wiele rzeczy. Długo by wymieniać. Mianowicie podczas ostatnich moich zabaw programistycznych napotkałem ciekawy problem. Mianowicie robiąc sobie "grę" postanowiłem, że moja postać będzie musiała się obracać aby spełniać inne czynności. Wszystko ładnie pięknie. Do pewnego momentu oczywiście, a co gdy chcę się obrócić w danym kierunku więcej niż raz? Wygląda to np tak.

turn left - aby obrócić się w lewo raz
turn left 9 - aby zrobić to 9 razy.

Oczywiście wynik działania byłby taki sam, jednak skoro można to napisać to czemu nie spróbować?

Nie wspomniałem wcześniej, że moja postać może się obracać tylko w 4 kierunkach oznaczonych kolejno zgodnie z kierunkiem wskazówek zegara 0,1,2 i 3 zaczynając od północy. A więc każdą cyfrę po komendzie turn left muszę potraktować działaniem modulo 4 (%4) aby wynik był poprawny. Idąc dalej tym tokiem myślenia rozpisałem sobie obracanie na kartce. Wynikiem rozpiski były permutacje (załączam dwie trudniejsze).

Jak każdy widzi problem nie taki łatwy na jaki wygląda. Pierwsza myśl była aby napisać x=koniec.komendy%4 switch(x) {case 0:{zmien.kierunek(3); break;} case 1:{zmien.kierunek(0); break;} case 2:{zmien.kierunek(1); break;} case 3:{zmien.kierunek(2); break;} }

Można to zastąpić instrukcjami if else. Jednak ja nie lubię tracić miejsca, a takich permutacji miałem 8. Jedne prostsze inne trudne jak te powyżej. Tutaj w grę weszły wszelkie umiejętności z algebry liniowej jakie nabyłem w trakcie studiowania a także trochę logiki. Postanowiłem więc poświęcić trochę czasu i znaleźć wzory na te permutacje. Faktem jest, że zajęło mi wszystko razem parę ładnych godzin jednak efekt jest porażający. Całego powyższego switcha udało się zastąpić jednym wzorem co na pewno przyśpiesza program, chociaż na pierwszy rzut oka czytelność kodu spada. Rozwiązaniem dla powyższych permutacji są kolejno wzory 1. ((4+(-3-x)%4)%4) 2. ((4+(-((2+x)%4)))%4)

Na pewno wzory te nie należą do najłatwiejszych ale rozwiązują wiele problemów. Między innymi zamiast pisać 8 funkcji switch napisałem 8 wzorów równie trudne jak te powyżej lub/i łatwiejszych.

Oczywiście gdybym przyjął 8 kierunków wzory byłyby dużo bardziej trudniejsze. Jeśli postać miałaby się obracać tak jak w realnym świecie na pewno ten sposób byłby do niczego, jednak dla 4 kierunków wydawał mi się on jak najbardziej najlepszy.

Z każdym krokiem w moim kursie programowania dowiaduje się, że kolejne działy matematyki, które uważałem za mało użyteczne pojawiają się coraz częściej.

Osobiście jestem ciekaw kiedy sięgnę po wykorzystanie całek aby rozwiązywać problemy.

Pozdrawiam. 

Komentarze

0 nowych
Jaahquubel_   12 #1 29.07.2011 02:06

Tak namieszałeś z tymi obrotami, że ciężko pojąć o co chodzi.

Permutacja Delta obraca postać patrzącą na północ tak, aby patrzyła na wschód (obrót w prawo), a patrzącą na wschód odwraca w lewo, na północ. Południe i zachód analogicznie. Ja to nie widzę żeby to była permutacja opisująca obrót w lewo.

Permutacja Pi zamienia północ na południe i odwrotnie, a reszty kierunków nie rusza. Znów, ja tu obrotu nie widzę.
Czy ja to źle rozumiem?

Czy chodzi Ci o coś w stylu:
kierunek_postaci=(kierunek_postaci-krotnosc_obrotu)%4,
przy założeniu, że % daje zawsze liczbę nieujemną?

Sam pomysł zamiany switcha na wzorek bardzo ciekawy. Czy jednak jesteś pewien, że to działa szybciej? Ja tam widzę po 5 działań na permutację, a w wersji ze switchem masz jedno działanie (modulo) i do czterech porównań, czyli w najgorszym razie 5 operacji. Dobrze rozumuję? Czy zysk w tym miejscu może zależeć od języka programowania?

Draqun   9 #2 30.07.2011 00:41

Permutacje te są dziwne. Permutacja Delta jest o obrocie w lewo z punktu 2 o X razy, gdzie X to ilość obrotów modulo 4. Wzór ten pozawala szybko znaleźć kierunek w jakim się nam postać znajdzie, co wyjdzie na dobre na pewno kodowi wynikowemu.

Analogicznie permutacja Pi. Wzory nie należą do najprostszych (niektóre z nich były banalne) jednak jak się wgryźć w to głębiej oszczędność pracy kodowania była przyjemna a w dodatku znalazłem zastosowanie dla permutacji, które może gdzieś w przyszłości wykorzystam :)

@AJaahquubel_
Czy zysk w tym miejscu może zależeć od języka programowania?

Możliwe. Znam C, C++ i coś tam pamiętam z PHP. Może się okazać, że w innym języku szukanie takich wzorów okaże się zbędne. Osobiście jednak od dwóch dni zastanawiam się jak ogromne byłyby wzory np. dla położenia postaci w jednej z 360 pozycji okręgu? Jest moim zdaniem ich wystarczająco dużo aby w każdej grze (chyba poza FPS-ami) ustawić postać w dowolnej pozycji :)

Saskatchewan   7 #3 30.07.2011 10:26

A ja dalej nie rozumiem.

Draqun napisał:
> Permutacja Delta jest o obrocie w lewo z punktu 2
> o X razy, gdzie X to ilość obrotów modulo 4.

Mi to bardziej wygląda na Pi, a nie na Deltę:
- stoję na 2, robię X obrotów w lewo, gdzie X%4==0 i jestem na 2;
- stoję na 2, robię X obrotów w lewo, gdzie X%4==1 i jestem na 1;
- itd..

Jaahquubel_ napisał:
> Czy chodzi Ci o coś w stylu:
> kierunek_postaci=(kierunek_postaci-krotnosc_obrotu)%4,
> przy założeniu, że % daje zawsze liczbę nieujemną?

No właśnie, i wtedy, gdy stoję na 2 i obracam się w lewo:
- 0 obrotów -> (2-0) % 4 == 2 % 4 == 2
(bo 2 == 4*0 + 2, tzn. 1 % 4 == 0 i 2 reszty);
- 1 obrót -> (2-1) % 4 == 1 % 4 == 1
(bo 1 == 4*0 + 1);
- ...
- 3 obroty -> (2-3) % 4 == -1 % 4 == 3
(bo -1 == 4*(-1) + 3, tzn -1 % 4 == -1 i 3 reszty);
- 17 obrotów -> (2-17) % 4 == -15 % 4 == 1
(bo -15 == 4*(-4) + 1)
- itd..

Ja to widzę w ten sposób.

Draqun   9 #4 30.07.2011 19:23

Mea culpa źla się wyraziłem, ale działa to tak jak Saskatchewan zauważuł. Permutacja Delta mówi o obracaniu się z miejsca numer 1 (mój 2 kierunek wschód ;)) a Pi z miejsca numer 2 (czyli mój 3 kierunek południe :))

Czyli:
- jestem zwrócony na wschód
- komenda: turn left 9
- x=9%4 czyli 1
- do wzoru wprowadzane jest 1
- W wyniku wykorzystania wzoru otrzymamy 0 czyli postać obrócona na wschód teraz jest zwrócona na północ czyli mój kierunek 0.

Teraz rozpatrzmy drugą permutację(Pi) i wzór.
- stoję obrucony na południe
- turn left 3
- x=3%4 czyli x=3
- stosujemy wzór numer dwa
2+3=5
5%4=1
4-1=3
3%4=3
Zwróć uwagę na drugą permutację. Dla trójki wynikiem jest trójka czyli tak jak w moich obliczeniach.

Wiem, że może to wydawać się trochę niejasne. Nie do końca jest łatwo mi przekazać tak skomplikowane moje wymysły.

Zauważcie również, że pierwszy rząd permutacji to nie jest miejsce, z którego obraca się postać. Jest to liczba obrotów jakie musi wykonać aby znaleźć się w miejscu jakie jest w drugim rzędzie. A wzór jest opisany dla obracania się z danego miejsca.

Saskatchewan   7 #5 31.07.2011 13:18

No to popatrz na własnych przykładach:
- wschód (1), turn left 9 --> (1-9)%4 = (-8)%4 = 0;
- południe (2), turn left 3 --> (2-3)%4 = (-1)%4 = 3.
Wyniki wyszły poprawne, a nie korzystałem z twoich wzorów, tylko tego co napisał Jaahquubel_.

A teraz wzory:
1. ((4+(-3-x)%4)%4)
Do ((-3-x)%4) dodajesz czwórkę i bierzesz modulo 4 z sumy, czyli i tak wyjdzie ci to samo co z ((-3-x)%4). Tej -3 też nie wytrzasnąłeś z kosmosu, bo przecież (-3) == 1-4, a skoro operujesz na Z_4, to -3 przecież jest jedynką.

Analogicznie drugi wzór.

  #6 31.07.2011 15:36

Faktycznie macie rację. Byłem pewien, że znajdą sie lepsze sposoby na te wzory :).

Dzięki wielkie.

Pozdrawiam.

Saskatchewan   7 #7 31.07.2011 17:02

Każdy czasem coś przekombinuje ;).

Pozdrawiam

Jaahquubel_   12 #8 02.08.2011 15:33

"Zauważcie również, że pierwszy rząd permutacji to nie jest miejsce, z którego obraca się postać."
I tym mnie zmyliłeś, bo w tej notacji permutacje działają tak: górny rząd przeprowadzają na dolny rząd.

"położenia postaci w jednej z 360 pozycji okręgu"
A tu działa coś, co już wcześniej podałem (dla obrotu w lewo):
kierunek_postaci=(kierunek_postaci-krotnosc_obrotu)%n, gdzie podstawiasz n=360 dla tej konkretnej sytuacji, przy założeniu, że Twój język programowania i kompilator zwraca modulo zawsze dodatnie (podkreślam to, bo kiedyś czytałem jakiś artykuł o tym, że to zależy od OS-u, języka i kompilatora, i że podobno jedni podają w książkach definicję taką, że np. -9%4=-1, a inni -9%4=3).

Kombinujesz dobrze, takie kombinowanie Cię rozwija, więc się nie poddawaj. A to, że przekombinowałeś, to po prostu życie. No i na Twój wpis trafiło dwóch matematyków. :)

Pozdrawiam!