Zaprzyjaźnij się z algorytmami
Przewodnik dla początkujących i średniozaawansowanych
Zaprzyjaźnij się z algorytmami. Przewodnik dla początkujących i
średniozaawansowanych zawiera opis podstawowych i najważniejszych technik
algorytmicznych i struktur danych, które zostały uporządkowane w osiemnastu
rozdziałach.
Do każdego tematu wyselekcjonowano zadania o zróżnicowanym poziomie trudności
odpowiednie zarówno dla początkujących, jak i bardziej zaawansowanych uczniów.
Książka jest również doskonałym materiałem dydaktycznym dla nauczycieli szkół
gimnazjalnych i ponadgimnazjalnych.
Wprowadzenie XI
Od autora XIII
1. Złożonosć czasowa 1
Porównanie różnych złożonosci czasowych 2
Limit czasu 3
Złożonosć pamięciowa 4
Ćwiczenie 4
Zadania treningowe 5
Żabka 5
Chodnik 6
Tasma 7
Rozwiązania 8
2. Zliczanie elementów 9
Ćwiczenie 10
Zadania treningowe11
Permutacja 11
Ropucha 12
Przyciski 13
Rozwiązania 14
3. Sumy prefiksowe 16
Ćwiczenie 17
Zadania treningowe18
Długa tasma 18
Samochody 19
Chomiki 20
Rozwiązania 21
4. Sortowanie 22
Sposób1:sortowanie przez wybieranie 22
Sposób2:sortowanie przez zliczanie.23
Sposób3:sortowanie przez scalanie 24
Funkcje sortujące.24
Ćwiczenie 25
Zadania treningowe 25
Iloczyn 25
Gwozdzie 26
Tory kolejowe 27
Rozwiązania 28
5. Stos i kolejka 30
Stos 30
Kolejka. 31
Ćwiczenie 32
Zadania treningowe 32
Nawiasy 32
Ryby 33
Cukiernia 34
Rozwiązania 35
6. Wyszukiwanie lidera 37
Sprawdzenie kandydata 37
Rozwiązanie o złożonosci O(n2) 38
Rozwiązanie o złożonosci O(n log n) 38
Rozwiązanie o złożonosci O(n) 39
Ćwiczenie 40
Zadania treningowe 41
Dwie częsci 41
Bajtocka flaga 42
Lider prefiksowy 43
Rozwiązania 44
7. Spójny podciąg o maksymalnej sumie 45
Rozwiązanie o złożonosci O(n3) 45
Rozwiązanie o złożonosci O(n2) 46
Rozwiązanie o złożonosci O(n) 46
Ćwiczenie 47
Zadania treningowe 49
Odchudzanie 49
Bilet 49
Praca domowa 51
Rozwiązania 51
8. Liczby pierwsze i złożone 53
Liczenie dzielników 53
Testpierwszosciwczasie O(n) 54
Ćwiczenie 54
Zadania treningowe56
Obwód 56
Szczyty 56
Flagi 57
Rozwiązania 58
9. Sito Eratostenesa 61
Faktoryzacja 62
Ćwiczenie 63
Zadania treningowe 64
Tablica liczb 64
Liczby półpierwsze 64
Liczby doskonałe 65
Rozwiązania 66
10. Algorytm Euklidesa 68
Najmniejsza wspólna wielokrotnosć 69
Ćwiczenie 69
Zadania treningowe 69
Mandarynki 69
Wesołamałpka 70
Zbiór pierwszych 71
Rozwiązania 72
11. Ciąg Fibonacciego 73
Ćwiczenie 74
Zadania treningowe74
Zajączek 74
Drabina 75
Spotkanie 76
Rozwiązania 77
12.Wyszukiwanie binarne 79
Intuicja 79
Implementacja 80
Wyszukiwanie binarne po wyniku 81
Ćwiczenie 81
Zadania treningowe 82
Promień 82
Deski 82
Tort 83
Rozwiązania 85
13. Gąsienica 87
Przykład użycia 87
Ćwiczenie 88
Zadania treningowe89
Smakołyki 89
Wycinek 90
Temperatura 90
Rozwiązania 92
14. Programowanie zachłanne 94
Problem wydawania reszty 94
Dowodzenie poprawnosci 95
Ćwiczenie 95
Zadania treningowe96
Sznurki . 96
Bracia .97
Szklanki 98
Rozwiązania 99
15. Programowanie dynamiczne 101
Problem wydawania reszty 101
Ćwiczenie 103
Zadania treningowe 104
Pionek 104
Wybrzeże 105
Ładnyciąg 106
Rozwiązania 107
16. Drzewabinarne 110
Pełnedrzewobinarne 111
Reprezentacjadrzewbinarnych 111
Binarne drzewa wyszukiwania (BST) 112
Zadania treningowe 113
Drzewkobinarne 113
Nieskończonedrzewko 114
Drzewko 115
Rozwiązania 116
17.Kolejka priorytetowa 119
Kopiec binarny.119
Wstawienie elementu dokopca O(log n) 120
Usunięcie elementu maksymalnego O(log n) 121
Tworzenie nowego kopca z listy elementów O(n) 122
Ćwiczenie 123
Zadania treningowe124
Emeryci 124
Bilety 124
Tamy 125
Rozwiązania 127
18. Algorytmy grafow eBFSiDFS 128
Rodzaje grafów 129
Reprezentacja grafu 130
DFS, czyliprzeszukiwanie grafu w głąb 132
BFS, czyli przeszukiwanie grafu w szerz 133
Ćwiczenie 134
Zadania treningowe 134
Lista kontaktów 134
Las .135
Wyprawa króla 136
Rozwiązania 137
A. Kolejne tematy 139
Algorytm Dijkstry 139
Srednica drzewa 139
Zbiory rozłączne 139
Algorytm Primai Kruskala 139
Sortowanie topologiczne 140
Drzewo licznikowe 140
Szybkie potęgowanie 140
Koszt zamortyzowany 140
Najdłuższy rosnący podciąg 140
Teoria gier 140
Algorytm Knutha–Morrisa–Pratta 141
Haszowanie tekstów 141
Algorytm Karpa–Millera–Rosenberga 141
Szukanie palindromów i algorytm Manachera 141
Najdłuższy wspólny podciąg 141
Programowanie dynamiczne na drzewach 141
Podstawy geometrii obliczeniowej 142
Sortowanie kątowe 142
Otoczka wypukła 142
Para najmniej i najbardziej oddalonych punktów 142
Maski bitowe142
Najniższy wspólny przodek 142
Silnie spójne składowe 143
Mosty i punkty artykulacji 143
Cykl Eulera.143
Przepływy iskojarzenia 143
B. STL 144
Para elementów 144
Wektor 145
Kolejka 148
Kolejka priorytetowa 149
Minimum, maksimum i zamiana. 150
Sortowanie 150
Permutacje 151
Mieszanie 152
Wskazniki w C++ 152
Iteratory 153
Wyszukiwanie binarne 154
Lista 154
Zbiór i multizbiór 155
Mapa 156
Bibliografia 157
Skorowidz 158
Opinie i komentarze 161
164 strony, Format: 16.5x23.5cm, oprawa miękka
