MENU
Nasze ceny
-
promocja
Myślenie algorytmiczne. Jak rozwiązywać problemy za pomocą algorytmów - ebook
Myślenie algorytmiczne. Jak rozwiązywać problemy za pomocą algorytmów - ebook
Warunkiem poprawnego działania algorytmu i pomyślnego rozwiązania problemu programistycznego jest trafny wybór struktury danych i zastosowanie odpowiedniego algorytmu. A to oznacza, że nawet świetna znajomość ulubionego języka programowania nie wystarcza, aby pisać rzeczywiście dobry kod. Nie masz wyjścia: musisz nabrać biegłości w posługiwaniu się algorytmami i strukturami danych.
Dzięki tej książce nauczysz się rozwiązywania ambitnych problemów algorytmicznych i projektowania własnych algorytmów. 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 wybierać odpowiednie algorytmy. Sprawdzisz także, w jaki sposób dobór odpowiedniej struktury danych może wpłynąć na czas wykonywania algorytmów. Nauczysz się też używać takich metod jak rekurencja czy wyszukiwanie binarne. Próbując swoich sił w samodzielnej modyfikacji poszczególnych algorytmów, jeszcze lepiej je zrozumiesz i podniesiesz umiejętności programistyczne na wyższy poziom! To wydanie zostało rozszerzone o rozdziały poświęcone programowaniu dynamicznemu i algorytmom probabilistycznym. Znajdziesz w nim również nowe przykłady i bardziej rozbudowane wyjaśnienia trudniejszych zagadnień.
W książce między innymi:
- algorytm przeszukiwania wszerz
- algorytm Dijkstry
- struktura zbiorów rozłącznych, kopce, tablice mieszające
- programowanie dynamiczne
- algorytmy probabilistyczne
Twórz algorytmy, które sprostają każdemu wyzwaniu.
Spis treści
Przedmowa
Podziękowania
Wprowadzenie
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.: Chaos w hasłach
- Problem
- Rozwiązanie 1.: Sprawdzanie wszystkich haseł
- Rozwiązanie 2.: Użycie tablicy mieszającej
- 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
- Podsumowanie
- Uwagi
4. Zaawansowana memoizacja i programowanie dynamiczne
- Problem 1.: Skoczek
- Problem
- Analiza przykładu
- Rozwiązanie 1.: Analiza wstecz
- Rozwiązanie 2.: Analiza w przód
- Problem 2.: Sposoby budowy
- Problem
- Analiza przykładu
- Rozwiązanie 1.: Stosowanie "dokładnych" podproblemów
- Rozwiązanie 2.: Dodawanie kolejnych podproblemów
- Podsumowanie
- Uwagi
5. 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
- Grafy a programowanie dynamiczne
- Problem 2.: Wspinaczka po linie
- Problem
- Rozwiązanie 1.: Poszukiwanie ruchów
- Rozwiązanie 2.: Nowy model
- Problem 3.: Tłumaczenie książek
- Problem
- Wczytywanie nazw języków
- Budowanie grafu
- Implementacja algorytmu BFS
- Koszt całkowity
- Podsumowanie
- Uwagi
6. Najkrótsze ścieżki na grafach ważonych
- Problem 1.: Myszy w labiryncie
- Problem
- Zostawiamy algorytm BFS
- Znajdowanie najkrótszej ś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
- Analiza przypadku testowego dziwacznych ścieżek
- Zadanie 1.: Najkrótsze ścieżki
- Zadanie 2.: Liczba najkrótszych ścieżek
- Podsumowanie
- Uwagi
7. 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
8. 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
9. 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: Struktura zbiorów rozłącznych
- 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
10. Randomizacja
- Problem 1.: Yokan
- Problem
- Losowy wybór kawałka
- Generowanie liczb losowych
- Określanie liczby kawałków
- Odgadywanie smaków
- Ilu prób potrzebujemy?
- Wypełnianie tablic smaków
- Funkcja main
- Randomizacja
- Algorytmy typu Monte Carlo
- Algorytmy typu Las Vegas
- Algorytmy deterministyczne a probabilistyczne
- Problem 2.: Kapsle i butelki
- Problem
- Rozwiązywanie podzadania
- Rozwiązanie 1.: Rekurencja
- Rozwiązanie 2.: Dodanie randomizacji
- Sortowanie szybkie
- Implementacja algorytmu sortowania szybkiego
- Efektywność najgorszego przypadku i oczekiwana
- 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
- Kapsle i butelki: sortowanie w miejscu
C. Z podziękowaniem za problemy
| Kategoria: | Programowanie |
| Zabezpieczenie: |
Watermark
|
| ISBN: | 978-83-289-2064-4 |
| Rozmiar pliku: | 7,4 MB |
