Myślenie algorytmiczne. Jak rozwiązywać problemy za pomocą algorytmów - ebook

Jak już wiesz, struktura danych jest sposobem zorganizowania danych w pamięci komputera, co ma umożliwić szybkie wykonywanie zamierzonych operacji. Pamiętasz też, że algorytm jest sekwencją działań pozwalających na rozwiązanie problemu. Często warunkiem poprawnego działania algorytmu i pomyślnego rozwiązania problemu programistycznego jest trafny wybór struktury danych. To bardzo ważne zagadnienie. Nawet jeśli dobrze znasz wybrany język programowania, to aby pisać dobry kod, musisz nabrać biegłości w posługiwaniu się algorytmami i strukturami danych.

Dzięki tej książce nauczysz się rozwiązywać ambitne problemy algorytmiczne i projektować własne algorytmy. Materiałem do ćwiczeń są tu przykłady zaczerpnięte z konkursów programistycznych o światowej renomie. Dowiesz się, jak klasyfikować problemy, czym się kierować podczas wybierania struktury danych i jak dobierać odpowiednie algorytmy. Sprawdzisz także, w jaki sposób wybór struktury danych może wpłynąć na czas wykonywania algorytmów. Nauczysz się też używać takich metod jak rekurencja, programowanie dynamiczne czy wyszukiwanie binarne. Swoich sił spróbujesz w ramach samodzielnej pracy nad modyfikacją poszczególnych algorytmów. Zamieszczone tu szczegółowe analizy kodu pomogą Ci w zrozumieniu praktycznych aspektów stosowania algorytmów i struktur danych.

W książce między innymi:

• algorytm przeszukiwania wszerz
• algorytm Dijkstry
• struktura zbiorów rozłącznych
• kopce
• tablice mieszające

Algorytmy: zmierzysz się z naprawdę trudnymi problemami!

Przedmowa

Podziękowania

Wprowadzenie

• Zasoby internetowe
• Dla kogo jest przeznaczona ta książka
• Język programowania
  • Dlaczego wybrałem język C?
  • Słowo kluczowe static
  • Pliki nagłówkowe
  • Zwalnianie pamięci
• Zagadnienia
• Witryny oceniające
• Anatomia opisu problemu
• Problem: Kolejki po jedzenie
  • Problem
  • Rozwiązanie problemu
• Uwagi

1. Tablice mieszające

• Problem 1. Płatki śniegu
  • Problem
  • Uproszczenie problemu
  • Rozwiązywanie podstawowego problemu
  • Rozwiązanie 1. Porównywanie parami
  • Rozwiązanie 2. Zmniejszenie liczby wykonywanych operacji
• Tablice mieszające
  • Projekt tablicy mieszającej
  • Dlaczego warto używać tablic mieszających?
• Problem 2. Słowa złożone
  • Problem
  • Wskazywanie słów złożonych
  • Rozwiązanie
• Problem 3. Sprawdzanie pisowni - usuwanie litery
  • Problem
  • Rozważania o zastosowaniu tablic mieszających
  • Rozwiązanie doraźne
• Podsumowanie
• Uwagi

2. Drzewa i rekurencja

• Problem 1. Halloweenowy łup
  • Problem
  • Drzewa binarne
  • Rozwiązywanie problemu dla przykładowego drzewa
  • Reprezentacja drzew binarnych
  • Zbieranie wszystkich cukierków
  • Zupełnie inne rozwiązanie
  • Przechodzenie minimalnej liczby ulic
  • Odczyt danych wejściowych
• Dlaczego korzystać z rekurencji?
• Problem 2. Odległość pomiędzy potomkami
  • Problem
  • Odczyt danych wejściowych
  • Liczba potomków w odległości d od wierzchołka
  • Liczba potomków dla wszystkich wierzchołków
  • Sortowanie wierzchołków
  • Wyświetlanie wyników
  • Funkcja main
• Podsumowanie
• Uwagi

3. Memoizacja i programowanie dynamiczne

• Problem 1. Burgerowa gorączka
  • Problem
  • Określenie planu rozwiązania problemu
  • Określanie optymalnego rozwiązania
  • Rozwiązanie 1. Zastosowanie rekurencji
  • Rozwiązanie 2. Memoizacja
  • Rozwiązanie 3. Programowanie dynamiczne
• Memoizacja i programowanie dynamiczne
  • Krok 1. Struktura optymalnego rozwiązania
  • Krok 2. Rozwiązanie rekurencyjne
  • Krok 3. Memoizacja
  • Krok 4. Programowanie dynamiczne
• Problem 2. Skąpcy
  • Problem
  • Określanie optymalnego rozwiązania
  • Rozwiązanie 1. Rekurencja
  • Funkcja main
  • Rozwiązanie 2. Memoizacja
• Problem 3. Rywalizacja hokejowa
  • Problem
  • Rozważania dotyczące rywalizacji
  • Określenie optymalnego rozwiązania
  • Rozwiązanie 1. Rekurencja
  • Rozwiązanie 2. Memoizacja
  • Rozwiązanie 3. Programowanie dynamiczne
  • Optymalizacja zużycia pamięci
• Problem 4. Sposoby zaliczenia
  • Problem
  • Rozwiązanie: memoizacja
• Podsumowanie
• Uwagi

4. Grafy i przeszukiwanie wszerz

• Problem 1. Pogoń skoczka
  • Problem
  • Optymalne ruchy skoczka
  • Najlepszy wynik skoczka
  • Przesunięcie i powrót skoczka
  • Optymalizacja czasu działania
• Grafy i przeszukiwanie wszerz
  • Czym są grafy?
  • Grafy a drzewa
  • Algorytm BFS na grafach
• Problem 2. Wspinaczka po linie
  • Problem
  • Rozwiązanie 1. Poszukiwanie ruchów
  • Rozwiązanie 2. Nowy model
• Problem 3. Tłumaczenie książek
  • Problem
  • Budowanie grafu
  • Implementacja algorytmu BFS
  • Koszt całkowity
• Podsumowanie
• Uwagi

5. Najkrótsze ścieżki na grafach ważonych

• Problem 1. Myszy w labiryncie
  • Problem
  • Zostawiamy algorytm BFS
  • Najkrótsze ścieżki na grafach ważonych
  • Tworzenie grafu
  • Implementacja algorytmu Dijkstry
  • Dwie optymalizacje
• Algorytm Dijkstry
  • Efektywność działania algorytmu Dijkstry
  • Krawędzie o wagach ujemnych
• Problem 2. Planowanie odwiedzin u babci
  • Problem
  • Macierz sąsiedztwa
  • Konstruowanie grafu
  • Dziwaczne ścieżki
  • Zadanie 1. Najkrótsze ścieżki
  • Zadanie 2. Liczba najkrótszych ścieżek
• Podsumowanie
• Uwagi

6. Wyszukiwanie binarne

• Problem 1. Karmienie mrówek
  • Problem
  • Nowy rodzaj problemów z drzewami
  • Wczytywanie danych wejściowych
  • Sprawdzanie wykonalności
  • Poszukiwanie rozwiązania
• Wyszukiwanie binarne
  • Wydajność działania algorytmu wyszukiwania binarnego
  • Określanie wykonalności
  • Przeszukiwanie tablicy posortowanej
• Problem 2. Skok przez rzekę
  • Problem
  • Koncepcja zachłanności
  • Testowanie wykonalności
  • Poszukiwanie rozwiązania
  • Wczytywanie danych wejściowych
• Problem 3. Jakość życia
  • Problem
  • Sortowanie wszystkich prostokątów
  • Wyszukiwanie binarne
  • Sprawdzanie wykonalności
  • Szybsze sprawdzanie wykonalności
• Problem 4. Drzwi w jaskini
  • Problem
  • Rozwiązywanie podzadań
  • Zastosowanie wyszukiwania liniowego
  • Stosowanie wyszukiwania binarnego
• Podsumowanie
• Uwagi

7. Kopce i drzewa segmentów

• Problem 1. Promocja w supermarkecie
  • Problem
  • Rozwiązanie 1. Wartość maksymalna i minimalna w tablicy
  • Kopce maksymalne
  • Kopce minimalne
  • Rozwiązanie 2. Kopce
• Kopce
  • Inne zastosowania
  • Wybór struktury danych
• Problem 2. Budowanie drzewców
  • Problem
  • Rekurencyjne wyświetlanie drzewców
  • Sortowanie na podstawie etykiet
  • Rozwiązanie 1. Rekurencja
  • Pytania o sumę zakresu
  • Drzewa segmentów
  • Rozwiązanie 2. Drzewa segmentów
• Drzewa segmentów
• Problem 3. Suma dwóch
  • Problem
  • Wypełnianie drzewa segmentów
  • Znajdowanie odpowiedzi z użyciem drzewa segmentów
  • Aktualizacja drzewa segmentów
  • Funkcja main
• Podsumowanie
• Uwagi

8. Struktura zbiorów rozłącznych

• Problem 1. Sieć społecznościowa
  • Problem
  • Modelowanie danych w formie grafu
  • Rozwiązanie 1. BFS
  • Struktura zbiorów rozłącznych
  • Rozwiązanie 2. Struktura zbiorów rozłącznych
  • Optymalizacja 1. Łączenie na podstawie wielkości
  • Optymalizacja 2. Skracanie ścieżek
• Struktura zbiorów rozłącznych
  • Relacje: Trzy wymagania
  • Wybieranie struktury zbiorów rozłącznych
  • Optymalizacje
• Problem 2. Przyjaciele i wrogowie
  • Problem
  • Rozszerzenie: wrogowie
  • Funkcja main
  • Operacje find i union
  • Operacje UstawJakoPrzyjaciół i UstawJakoWrogów
  • Operacje CzySąPrzyjaciółmi i CzySąWrogami
• Problem 3. Kłopot z szufladami
  • Problem
  • Równoważne szuflady
  • Funkcja main
  • Implementacja operacji find i union
• Podsumowanie
• Uwagi

Podsumowanie

A. Efektywność algorytmów

• Kwestia czasu. i nie tylko
• Notacja dużego O
  • Czas liniowy
  • Czas stały
  • Inny przykład
  • Czas kwadratowy
  • Notacja dużego O w tej książce

B. Ponieważ nie mogłem się powstrzymać

• Płatki śniegu: niejawne listy połączone
• Burgerowa gorączka: rekonstrukcja rozwiązania
• Pogoń skoczka: kodowanie ruchów
• Algorytm Dijkstry: stosowanie kopca
  • Myszy w labiryncie: śledzenie z użyciem kopców
  • Myszy w labiryncie: implementacja z użyciem kopca
• Skracanie skracania ścieżek
  • Krok 1. Żadnych więcej operatorów trójargumentowych
  • Krok 2. Bardziej czytelne operatory przypisania
  • Krok 3. Wyjaśnienie rekurencji

C. Z podziękowaniem za problemy