świstak.codes

O programowaniu, informatyce i matematyce przystępnym językiem

Programowanie

Iteracja — co to jest?

21 grudnia 2022

Iteracja to według słownika PWN-u metoda polegająca na wielokrotnym stosowaniu tej samej procedury. Nawet nieskończenie, niczym Syzyf wtaczający głaz na szczyt góry (jak na okładce). W zasadzie na tym mógłbym zamknąć ten artykuł, bo właśnie odpowiedziałem na pytanie z tytułu. Jednak mimo to wejdźmy w temat głębiej: jakie mamy rodzaje iteracji, do czego się ostatecznie sprowadzają, co mają wspólnego z rekurencją, a także czym są iteratory.

Czytaj więcej

Problem skoczka szachowego

26 października 2022

Problem skoczka szachowego to jeden z popularniejszych problemów algorytmicznych. Często możemy go spotkać pośród zadań z algorytmiki dla adeptów programowania. Zobaczmy, na czym ten problem polega oraz jak go rozwiązać, i przede wszystkim... co ma to wspólnego z szeroko opisywanym przeze mnie ostatnio tematem grafów.

Czytaj więcej

Szybkie wyszukiwanie ścieżek

28 września 2022

Klasyką algorytmiki jest wykorzystywanie takich algorytmów, jak BFS, algorytm Dijkstry czy Bellmana-Forda do wyszukiwania najkrótszych ścieżek. Jednak algorytmy te wykonują bardzo dużo operacji i przy rozbudowanych przypadkach, takich jak znajdowanie tras na mapie albo nawet ścieżki, po której ma przejść postać w grze komputerowej, mogą być zbyt wolne czy też zająć zbyt dużo pamięci. Na szczęście są również inne podejścia do tego problemu, dużo wydajniejsze, jeśli posiadamy nieco więcej informacji o grafie. Czas najwyższy poznać jedno z nich — algorytm A*.

Czytaj więcej

Praktyczne zastosowania przechodzenia po grafie

31 sierpnia 2022

W artykule „Przechodzenie po grafie” przedstawiłem algorytmy służące do przechodzenia po węzłach grafu — DFS (przechodzenie w głąb) oraz BFS (przechodzenie wszerz). Jednak samo odwiedzanie węzłów może wydawać się na pierwszy rzut oka mało przydatne, dlatego przedstawię trzy sposoby, jak można wykorzystać te algorytmy do celów praktycznych. Użyjemy też wszystkie trzy pokazane tam sposoby przechodzenia grafu: rekurencyjny DFS, iteracyjny DFS oraz BFS.

Czytaj więcej

Dziwny przypadek reszty z dzielenia

1 września 2021

Gdy we wczesnych latach podstawówki uczyliśmy się dzielenia (szczególnie „pod kreską”), w pewnym momencie dowiadywaliśmy się, że nie da się liczb idealnie podzielić. Czasami zostaje reszta. W końcu gdy dzielimy 6 na 4, to w szóstce zmieścimy tylko jedną czwórkę, ale to nie oznacza, że 6 dzielone przez 4 to po prostu 1. Mamy jeszcze 2 reszty, ewentualnie co dokładniejsi podaliby wynik 1,5. Jak się okazuje, obliczenie reszty z dzielenia, mimo że wydaje się czymś prostym i oczywistym... no cóż, zawsze coś musi się komplikować. Dlatego też przeanalizujmy tę operację: rozłóżmy ją na czynniki pierwsze i zobaczmy, co może tutaj pójść inaczej, i dlaczego, mimo różnych wyników, wciąż wszystko jest poprawnie.

Czytaj więcej

Algorytmika gier — saper

14 kwietnia 2021

Gry komputerowe nie raz skrywają w sobie wiele ciekawej algorytmiki, która albo jest zaskakująca, albo nietypowa, albo na tyle ciekawa, że warto się z nią zapoznać. Są też takie, które mają pod sobą wręcz bardzo „szkolne” algorytmy, ale nie oznacza to, że nie są ciekawe. Jedną z takich gier jest klasyczny saper, którego wielu zapewne kojarzy z gier wbudowanych w system Windows. Stoją za nim bardzo proste, lecz ciekawe w implementacji algorytmy. Napiszmy razem prosty klon tej gry.

Czytaj więcej