Delta mi!

Podobnie jak wyznaczanie liczb pierwszych, problem znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych ma klasyczne i zapewne wszystkim Czytelnikom znane rozwiązanie. Mowa oczywiście o algorytmie Euklidesa, jednym z najstarszych do dziś używanych algorytmów. Jest to rozwiązanie bardzo proste w implementacji, a w wersji z dzieleniem – efektywne: pozwala wyznaczyć NWD dwóch liczb nie większych niż  w czasie  W pewnych przypadkach istnieją jednak rozwiązania asymptotycznie szybsze.

Jeśli potrzebne nam są do czegoś liczby pierwsze z pewnego początkowego zakresu, zazwyczaj wyznaczamy je za pomocą sita Eratostenesa...

W tej edycji kącika omówimy zadanie pt. Podlewanie ogórków (naprawdę!) z rundy 2A konkursu TopCoder Open 2012.

Tym razem omówimy zadanie z pogranicza informatyki i muzykologii, które pojawiło się na Bałtyckiej Olimpiadzie Informatycznej w bieżącym roku.

Tym razem w kąciku lekko zmodyfikowana wersja zadania Listonosz z konkursu Wielka Przesmycka 2004.

W tej edycji kącika znowu cofniemy się w czasie do 2005 roku, do pierwszej edycji konkursu Potyczki Algorytmiczne, i omówimy zadanie z finału próbnego tego konkursu pt. Drogi (bardzo podobne zadanie pojawiło się zresztą w jeszcze bardziej zamierzchłej przeszłości, na Międzynarodowej Olimpiadzie Informatycznej w 1996 roku).

W tym miesiącu omówimy zadanie, które pojawiło się w pierwszej edycji konkursu Potyczki Algorytmiczne, w roku 2005.

Wyobraź sobie, Drogi Czytelniku, że jesteś kapitanem okrętu wojennego i w trakcie jednej z misji znalazłeś się na środku morza leżącego na terytorium wroga. Wiesz, że wróg rozmieścił w tej strefie pewną (skończoną) liczbę radarów. Każdy radar ma określony zasięg, być może różny w przypadku różnych radarów, i jest w stanie wykryć każdy podejrzany obiekt, który znajdzie się w jego zasięgu. Naszym siłom wywiadowczym udało się wykraść plan rozmieszczenia radarów. Na jego podstawie chcesz stwierdzić, czy możesz wydostać się z wrogich wód niezauważony przez radary.

Chyba wszyscy lubimy liczby pierwsze. Szczególne wrażenie robią te naprawdę duże, wydają się skrywać w sobie jakąś nadzwyczajną tajemnicę: dlaczego akurat one stały się swego rodzaju wybrańcami spośród innych liczb i mają tak niezwykłe właściwości?

Tym razem omówimy zadanie Robot sortujący (ang. Robotic Sort) z Mistrzostw Europy Środkowej w Programowaniu Zespołowym 2007 (CERC 2007).

Tym razem zajmiemy się zadaniem Nurkowanie z Obozu Naukowo-Treningowego im. Antoniego Kreczmara w 2007 roku.

Jednym z pierwszych zadań, z jakimi musi zmierzyć się każdy uczący się algorytmów lub programowania, jest znajdowanie minimum w tablicy (ciągu liczb). Oznaczmy taką tablicę przez

W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są Alicja i Bob, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.

W tym kąciku omówimy zadanie Jaskinia, które pojawiło się w zeszłym roku na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

Jedną z najlepiej znanych metod wyznaczania liczb pierwszych jest sito Eratostenesa. Opiera się ona na spostrzeżeniu, w zasadzie oczywistym, że jak wyrzucimy wszystkie liczby złożone, to zostaną same liczby pierwsze...

W tym artykule omówimy zadanie Prostokąt arytmetyczny z Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2011.

W tym miesiącu opiszemy zadanie Monety, które pojawiło się na Potyczkach Algorytmicznych w roku 2010.

W tym kąciku rozwiążemy zadanie Prostokąty (Rectangles), które pojawiło się w 2007 roku na konkursie organizowanym przez MIT w serwisie spoj.pl.

W tym miesiącu omówimy zadanie, które rozwiązywali uczestnicy Obozu Naukowo-Treningowego im. A. Kreczmara w 2009 r.

Któż z nas nie bawił się jako dziecko w chowanego? Zabawa ta sprawia dzieciom wiele radości, mimo że z algorytmicznego punktu widzenia jest bardzo prosta. Jeżeli bowiem wszyscy ukrywający się czekają uczciwie w swoich kryjówkach, to zawsze uda się ich znaleźć – wystarczy, jeżeli szukający przejrzy wszystkie miejsca.

W grafie nieskierowanym możemy obliczyć stopień każdego wierzchołka, czyli liczbę krawędzi incydentnych z tym wierzchołkiem. Przykładowo, dla grafu-koperty otrzymujemy w ten sposób ciąg stopni 4, 4, 3, 3, 2. Wykonanie takiego przekształcenia dla danego grafu jest naprawdę proste. Możemy jednak postawić pytanie odwrotne: czy mając dany ciąg liczb, możemy stwierdzić, czy odpowiada on stopniom wierzchołków jakiegoś grafu nieskierowanego, a jeśli tak, zrekonstruować ten graf?

Zadanie omawiane w tym kąciku pochodzi z obozu treningowego drużyn rosyjskich z 2008 roku (autor zadania: Andrew Stankevich).

Kilkanaście lat temu zgubiłem się w lesie. Nie na tyle, żeby sytuacja była beznadziejna...

Z artykułu Wojciecha Śmietanki wypływa ważny morał: przystosowanie algorytmu do działania na maszynie równoległej wymaga często zupełnie innego spojrzenia na dany problem. Okazuje się jednak, że nawet w przypadku architektury jednoprocesorowej optymalizacja algorytmu może wymagać od nas całkiem pomysłowych przeróbek. W tym artykule podamy dwa przykłady, w których kluczową okaże się kolejność, w jakiej wykonujemy operacje.

Napisanie programu, który generuje rysunek fraktala, idealnie nadaje się na zadanie dla początkującego programisty. Proste reguły prowadzące do powstania skomplikowanych wzorów powodują, że przy stosunkowo niewielkim wysiłku programistycznym można osiągnąć całkiem ambitne efekty wizualne. Ponadto samopodobieństwo fraktali pozwala ćwiczyć jedną z podstawowych koncepcji programistycznych – rekurencję.