MYŚLENIE ALGORYTMICZNE JAK ROZWIĄZYWAĆ PROBLEMY ZA POMOCĄ ALGORYTMÓW

ISBN: 978-83-283-8335-7

453 stron
format: B5
oprawa: miękka
Rok wydania: 2022

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.

SPIS TREŚCI

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