W ostatnim artykule przedstawiłem odwrotną notację polską (ONP) i jak obliczać wyrażenia matematyczne zapisane za jej pomocą. Jednak powiedzmy sobie szczerze — pisząc aplikację obliczającą wyrażenia, nie możemy zmuszać użytkowników do stosowania małopopularnej notacji tylko dlatego, że wygodnie się ją programuje. Dlatego też w tym artykule opiszę, w jaki sposób wiedzę na temat ONP zastosować do obliczania wyrażeń matematycznych zapisanych w tradycyjny, infiksowy sposób.

Kolejność wykonywania działań to, jak można zauważyć w Internecie, jeden z największych problemów, jakie przeciętne osoby mają z matematyką. Regularnie od wielu lat pojawia się w mediach społecznościowych jakiś wariant zagadki „oblicz 6/2(2+1)”, gdzie ludzie się kłócą, czyja odpowiedź jest prawidłowa. W idealnym świecie takich problemów nie powinno być. Dlatego powstały alternatywne sposoby zapisu działań matematycznych pozbywające się nawiasów, takie jak np. odwrotna notacja polska. Nasz świat idealnym jednak nie jest, więc męczymy się z nawiasami, ale poznajmy tę notację, bo akurat w świecie informatyki ma ona duże znaczenie.

Podczas nauki programowania jedną z pierwszych koncepcji z zakresu projektowania algorytmów, którą poznajemy, jest „dziel i zwyciężaj”. Poznaje się ją w kontekście wyszukiwania binarnego, a niektórzy nauczyciele przypominają, że strategia ta jest też wykorzystywana w najszybszych algorytmach sortowania. Jednak wiesz, że to podejście ma jeszcze więcej zastosowań? W artykule chciałem pokazać moim zdaniem jedno z ciekawszych — algorytm Karacuby, czyli algorytm szybkiego mnożenia oparty na „dziel i zwyciężaj”.

W grach dwuwymiarowych z widokiem z góry dość podstawowym elementem jest obracanie postaci gracza w kierunku kursora myszki. Ewentualnie możesz chcieć, żeby inne postacie w grze obracały się w kierunku gracza. Zastosowania są różne, ale stoi za tym jedna, bardzo prosta funkcja. Pokażę ją tutaj, a następnie wytłumaczę matematycznie, dlaczego to działa.

Na moim blogu rysowaliśmy już wiele rzeczy. Linie, okręgi, rośliny, zegar. Porysujmy znowu! Tym razem na tapet weźmy kolejną rzecz powiązaną z kołami — spirale. Po raz kolejny zobaczysz, jak w praktyce wykorzystać matematykę, geometrię i trygonometrię, aby zmusić komputer (z użyciem JavaScriptu) do narysowania czegokolwiek.

Do tej pory na blogu przedstawiałem przede wszystkim gotowe i znane rozwiązania algorytmiczne, ale rzadko pokazywałem, jak od podstaw coś zrobić, czego nie znajdziemy w podręcznikach do algorytmiki. Za to możemy znaleźć w podręcznikach do informatyki. Pokażę w tym wpisie, w jaki sposób, wykorzystując prostą matematykę, zrobić coś, co działa i wyświetla więcej niż ciągi liczb. A dokładniej — stworzymy prosty, animowany zegar analogowy.

Ostatnio zapoznaliśmy się ze względnie prostą operacją potęgowania. Prostą, bo w końcu to tylko powtarzanie jednego z najbardziej podstawowych działań aż do uzyskania wyniku. Zainteresujmy się teraz, jak algorytmicznie podejść do operacji odwrotnej do potęgowania, która już do tak prostych nie należy. Porozmawiajmy o pierwiastkowaniu.

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.