Patrząc na tekst, jesteśmy wzrokowo w stanie powiedzieć, czy dwa słowa są do siebie podobne: czy to znaczeniowo, czy pod kątem różnic w liczbie liter, czy jakkolwiek tylko przyjdzie nam do głowy. Tylko jak taką metrykę zdefiniować formalnie, a następnie w jaki sposób ją zapisać algorytmicznie? Idąc dalej tymi pytaniami — skąd wyszukiwarka internetowa wie, że jeśli wpisałeś(-aś) „dwistak”, to tak naprawdę miałeś(-aś) na myśli „świstak”? Poznajmy odpowiedzi na te pytania.

Potęgowanie to dość podstawowa, a jednocześnie przydatna operacja w matematyce. Jednak wykonując je według definicji, możemy nie dać rady zrobić tego szybko, szczególnie gdy podnosimy liczby do wysokich potęg. Mimo to jest na to sposób, jak można potęgi obliczać szybko, i to na tyle prostym algorytmem, że jest zwykle jednym z pierwszych, które poznajemy przy nauce programowania. Opowiedzmy sobie o nim, przetestujmy, a także sprawdźmy, czy naprawdę jest taki szybki.

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.

Obliczanie największego wspólnego dzielnika dwóch liczb to prawdopodobnie jeden z pierwszych algorytmów, które poznajemy podczas swojej edukacji. Zarazem jest to też bardzo proste do zapamiętania. Omówmy sobie to klasyczne podejście, a także różne inne podejścia.

Wieże Hanoi to dla większości ludzi na świecie prosta, drewniana zabawka dla dzieci. Natomiast dla studentów informatyki to nie raz jedno z najgorszych wspomnień z pierwszych lat studiów i nauki programowania. Jak to możliwe? Co jest w nich takiego strasznego? Przekonajmy się na własną rękę.

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.

Z mojego poprzedniego artykułu wiemy już czym jest rekurencja, rekursja ogonowa oraz jak je stosujemy. Jednak temat rekurencji jest dość rozległy i warto opowiedzieć sobie o tym, jak rekurencji możemy się najzwyczajniej w świecie… pozbyć. Proces ten nazywamy derekursywacją i możemy podejść do tego na różne sposoby, których część tutaj opiszę.

Rekurencja — co to jest?

W poprzednich częściach serii opisywałem, w jaki sposób tworzyć algorytmy sortowania bazujące na tym, jak na co dzień sortujemy, oraz jak podejścia te można optymalizować. Jednak, jak mogłeś się przekonać, nie są to najszybsze rozwiązania, dlatego teraz przejdziemy do omawiania tych mniej oczywistych podejść do sortowania, które okazują się być wydajniejsze. Omówimy algorytmy, które bazują na metodzie „dziel i zwyciężaj”.