Złożoność obliczeniowa – co to takiego?
Wielu z Was na początku swojej drogi programisty pewnie miało kiedyś zagwozdkę – po co wszyscy się tak męczą, skoro można zaimplementować sortowanie bąbelkowe? Może jest to trochę dziwny przykład,…
Algorytmy
Minimalna liczba nawiasów przy przekształcaniu wyrażeń z „Odwrotnej Notacji Polskiej” (ONP)
„Odwrotna Notacja Polska” (ONP, ang. Reverse Polish Notation, RPN) to poprostu inny sposób zapisywania wyrażeń arytmetycznych czy też algorytmów. Polega ona w dużym skrócie na prostszym zapisie wyrażeń arytmetycznych bez nawiasów z…
Abstrakcyjne struktury danych: Stos
Tworząc oprogramowanie czasami zapisywanie poszczególnych danych do zwykłych zmiennych, tablicy bądź plików po prostu przestaje wystarczać bądź jest całkowicie nie efektywne. W takich przypadkach na pomoc programiście przychodzi programowanie zorientowane…
Przerabiamy algorytm QuickSort z wersji rekurencyjnej na nierekurencyjną
Algorytm szybkiego sortowania znany jako QuickSort to jeden z najciekawszych i zarazem doskonale znanych algorytmów sortowania danych. Charakteryzuje się on stosunkowo szybkim działaniem i prostą implementacją. Cała idea jego działania…
Wyszukiwanie binarne – Algorytm typu „dziel i zwyciężaj”
Wyszukiwanie binarne to jeden z najpopularniejszych algorytmów do wyszukiwania danych w tablicy posortowanych liczb. Algorytm ten został oparty o metodę „dziel i zwyciężaj” dzięki czemu potrafi w czasie logarytmicznym znaleźć…
Algorytm Kadane 2D – czyli problem maksymalnej dwuwymiarowej podtablicy
Algorytm Kadane w swojej pierwotnej wersji służy do wyszukiwania podciągu o maksymalnej sumie elementów. Biorąc na przykład zwykłą tablicę z jakimiś liczbami jak choćby: 3 -8 9 4 7 6,…
Błędny algorytm na maturze z informatyki…
Wczoraj został przeprowadzony egzamin maturalny z informatyki na poziomie podstawowym oraz rozszerzonym. Pierwsza część co prawda przebiegła bez większych wpadek, ale już na drugiej okazało się, że jedno z zadań…
Szyfr Cezara
Szyfr Cezara (szyfr przesuwający) jest jednym z najstarszych znanych szyfrów. Jest on zbudowany na zasadzie szyfru podstawieniowego gdzie każda litera, tekstu niezaszyfrowanego zastępowana jest oddaloną od niej o stałą liczbę…
Sortowanie bąbelkowe, algorytm klasy O(N2)
Algorytm sortowania "bąbelkowego" jest jednym z najprostszych algorytmów służących do sortowania liczb, o złożoności czasowej O(N2) i pamięciowej O(1). Jego nazwa wzięła się od "pęcherzyków powietrza", które ulatywały w górę tuby wypełnionej wodą….
