perelki-programowania.-wydanie-ii full.pdf

(20885 KB) Pobierz
887610973.001.png
Spis treci
Wstęp ............................................................................................................................... 7
I Preliminaria ..................................................................................................... 11
1. Rozłupywanie ostrygi ...................................................................................................... 13
1.1. Przyjacielska rozmowa ......................................................................................................................................... 13
1.2. Dokładne określenie problemu........................................................................................................................... 14
1.3. Projekt programu ................................................................................................................................................. 14
1.4. Szkic implementacji ............................................................................................................................................. 16
1.5. Reguły .................................................................................................................................................................... 17
1.6. Problemy ............................................................................................................................................................... 18
1.7. Lektury uzupełniające ......................................................................................................................................... 19
2. Aha! Algorytmy ............................................................................................................... 21
2.1. Trzy problemy ...................................................................................................................................................... 21
2.2. Wszędobylskie szukanie binarne ....................................................................................................................... 22
2.3. Potęga typów podstawowych ............................................................................................................................. 23
2.4. Składanie razem: sortowanie .............................................................................................................................. 25
2.5. Reguły .................................................................................................................................................................... 26
2.6. Problemy ............................................................................................................................................................... 27
2.7. Lektury uzupełniające ......................................................................................................................................... 28
2.8. Implementacja programu anagramowego (kolumna boczna) ..................................................................... 29
3. Dane strukturyzują programy ........................................................................................ 31
3.1. Program kwestionariuszowy .............................................................................................................................. 31
3.2. Programowanie listów seryjnych ....................................................................................................................... 33
3.3. Tablica przykładów .............................................................................................................................................. 35
3.4. Strukturyzacja danych ......................................................................................................................................... 37
3.5. Wydajne narzędzie dla wyspecjalizowanych danych ..................................................................................... 37
3.6. Reguły .................................................................................................................................................................... 39
3.7. Problemy ............................................................................................................................................................... 40
3.8. Lektury uzupełniające ......................................................................................................................................... 42
887610973.002.png
 
4
SPIS TRECI
4. Pisanie poprawnych programów .................................................................................... 43
4.1. Wyzwanie szukania binarnego .......................................................................................................................... 43
4.2. Pisanie programu ................................................................................................................................................. 44
4.3. Zrozumieć program ............................................................................................................................................. 46
4.4. Reguły .................................................................................................................................................................... 49
4.5. Zadania weryfikacji oprogramowania .............................................................................................................. 50
4.6. Problemy ............................................................................................................................................................... 51
4.7. Lektury uzupełniające ......................................................................................................................................... 53
5. Drobna kwestia zaprogramowania ................................................................................. 55
5.1. Od pseudokodu do C ........................................................................................................................................... 55
5.2. Zaprzęg testowy .................................................................................................................................................... 57
5.3. Sztuka asercji ......................................................................................................................................................... 59
5.4. Testowanie zautomatyzowane ........................................................................................................................... 60
5.5. Pomiary prędkości ............................................................................................................................................... 61
5.6. Gotowy program .................................................................................................................................................. 63
5.7. Reguły .................................................................................................................................................................... 63
5.8. Problemy ............................................................................................................................................................... 64
5.9. Lektury uzupełniające ......................................................................................................................................... 65
5.10. Debugowanie (kolumna boczna) .................................................................................................................... 66
II Wydajność ....................................................................................................... 69
6. Spojrzenie na wydajność ................................................................................................. 71
6.1. Studium przypadku ............................................................................................................................................. 71
6.2. Poziomy projektowania ...................................................................................................................................... 73
6.3. Reguły .................................................................................................................................................................... 75
6.4. Problemy ............................................................................................................................................................... 75
6.5. Lektury uzupełniające ......................................................................................................................................... 76
7. Obliczenia pobieżne ........................................................................................................ 77
7.1. Podstawowe umiejętności ................................................................................................................................... 78
7.2. Szacowanie wydajności ....................................................................................................................................... 80
7.3. Czynniki bezpieczeństwa .................................................................................................................................... 82
7.4. Prawo Little’a ........................................................................................................................................................ 83
7.5. Reguły .................................................................................................................................................................... 84
7.6. Problemy ............................................................................................................................................................... 84
7.7. Lektury uzupełniające ......................................................................................................................................... 85
7.8. Obliczenia pobieżne w życiu codziennym ....................................................................................................... 86
8. Techniki projektowania algorytmów .............................................................................. 87
8.1. Problem i prosty algorytm .................................................................................................................................. 87
8.2. Dwa algorytmy kwadratowe ............................................................................................................................... 88
8.3. Algorytm dziel i zwyciężaj .................................................................................................................................. 89
8.4. Algorytm skanujący ............................................................................................................................................. 91
8.5. Jakie to ma znaczenie? ......................................................................................................................................... 92
8.6. Reguły .................................................................................................................................................................... 93
8.7. Problemy ............................................................................................................................................................... 94
8.8. Lektury uzupełniające ......................................................................................................................................... 96
5
SPIS TRECI
9. Optymalizacja kodu ......................................................................................................... 97
9.1. Typowa historia .................................................................................................................................................... 97
9.2. Zestaw pierwszej pomocy ................................................................................................................................... 98
9.3. Poważna operacja — szukanie binarne .......................................................................................................... 102
9.4. Reguły .................................................................................................................................................................. 105
9.5. Problemy ............................................................................................................................................................. 107
9.6. Lektury uzupełniające ....................................................................................................................................... 108
10. Oszczędzanie miejsca .................................................................................................... 109
10.1. Kluczem jest prostota ...................................................................................................................................... 109
10.2. Problem poglądowy ......................................................................................................................................... 110
10.3. Techniki zmniejszające wielkość danych ..................................................................................................... 113
10.4. Techniki zmniejszające wielkość kodu ......................................................................................................... 116
10.5. Reguły ................................................................................................................................................................ 118
10.6. Problemy ........................................................................................................................................................... 119
10.7. Lektury uzupełniające ..................................................................................................................................... 120
10.8. Duża oszczędność (kolumna boczna) ........................................................................................................... 120
III Produkt
....................................................................................................... 123
11. Sortowanie .................................................................................................................... 125
11.1. Sortowanie przez wstawianie ......................................................................................................................... 125
11.2. Proste sortowanie szybkie ............................................................................................................................... 127
11.3. Lepsze szybkie sortowania .............................................................................................................................. 130
11.4. Reguły ................................................................................................................................................................ 132
11.5. Problemy ........................................................................................................................................................... 133
11.6. Lektury uzupełniające ..................................................................................................................................... 134
12. Problem próby .............................................................................................................. 137
12.1. Problem ............................................................................................................................................................. 137
12.2. Jedno rozwiązanie ............................................................................................................................................ 138
12.3. Przestrzeń projektowania ............................................................................................................................... 139
12.4. Reguły ................................................................................................................................................................ 142
12.5. Problemy ........................................................................................................................................................... 143
12.6. Lektury uzupełniające ..................................................................................................................................... 144
13. Szukanie ........................................................................................................................ 145
13.1. Interfejs .............................................................................................................................................................. 145
13.2. Struktury liniowe ............................................................................................................................................. 147
13.3. Binarne drzewa poszukiwań ........................................................................................................................... 150
13.4. Struktury dla liczb całkowitych ..................................................................................................................... 153
13.5. Reguły ................................................................................................................................................................ 155
13.6. Problemy ........................................................................................................................................................... 156
13.7. Lektury uzupełniające ..................................................................................................................................... 156
13.8. Rzeczywisty problem szukania (kolumna boczna) ..................................................................................... 157
14. Kopce ............................................................................................................................. 161
14.1. Struktura danych .............................................................................................................................................. 161
14.2. Dwie krytyczne funkcje ................................................................................................................................... 163
6
SPIS TRECI
14.3. Kolejki priorytetowe ........................................................................................................................................ 166
14.4. Algorytm sortujący .......................................................................................................................................... 169
14.5. Reguły ................................................................................................................................................................ 171
14.6. Problemy ........................................................................................................................................................... 171
14.7. Lektury uzupełniające ..................................................................................................................................... 173
15. Sznury pereł .................................................................................................................. 175
15.1. Słowa .................................................................................................................................................................. 175
15.2. Frazy ................................................................................................................................................................... 178
15.3. Generowanie tekstu ......................................................................................................................................... 181
15.4. Reguły ................................................................................................................................................................ 185
15.5. Problemy ........................................................................................................................................................... 186
15.6. Lektury uzupełniające ..................................................................................................................................... 187
Zakończenie do wydania pierwszego ........................................................................... 189
Zakończenie do wydania drugiego ............................................................................... 191
A. Katalog algorytmów ..................................................................................................... 193
B. Quiz estymacyjny .......................................................................................................... 199
C. Modele kosztowe czasu i pamięci ................................................................................. 201
D. Reguły optymalizacji kodu ........................................................................................... 207
E. Klasy języka C++ służące do szukania ......................................................................... 213
Wskazówki do wybranych problemów ........................................................................ 217
Rozwiązania wybranych problemów ........................................................................... 223
Skorowidz ...................................................................................................................... 251

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin