Спортивное программирование [Стивен Халим] (pdf) читать постранично, страница - 2
Книга в формате pdf! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
- 1
- 2
- 3
- 4
- . . .
- последняя (9) »
3.3.1. Интересное использование двоичного поиска........................................146
3.4. «Жадные» алгоритмы ............................................................................................152
3.4.1. Примеры ............................................................................................................153
3.5. Динамическое программирование ....................................................................160
3.5.1. Примеры DP......................................................................................................161
3.5.2. Классические примеры ..................................................................................171
3.5.3. Неклассические примеры .............................................................................184
3.6. Решения упражнений, не помеченных звездочкой .......................................192
3.7. Примечания к главе 3 .............................................................................................195
Глава 4. Графы ...........................................................................................................197
4.1. Общий обзор и мотивация ...................................................................................197
4.2. Обход графа ..............................................................................................................198
4.2.1. Поиск в глубину (Depth First Search, DFS) ..................................................198
4.2.2. Поиск в ширину (Breadth First Search, BFS) ...............................................200
4.2.3. Поиск компонент связности (неориентированный граф) ....................202
4.2.4. Закрашивание – Маркировка/раскрашивание компонент
связности .....................................................................................................................203
4.2.5. Топологическая сортировка (направленный ациклический граф) ....204
4.2.6. Проверка двудольности графа .....................................................................206
4.2.7. Проверка свойств ребер графа через остовное дерево DFS ..................207
4.2.8. Нахождение точек сочленения и мостов (неориентированный
граф) ..............................................................................................................................209
4.2.9. Нахождение компонент сильной связности (ориентированный
граф) ..............................................................................................................................212
4.3. Минимальное остовное дерево ...........................................................................218
4.3.1. Обзор ..................................................................................................................218
4.3.2. Алгоритм Краскала .........................................................................................219
4.3.3. Алгоритм Прима ..............................................................................................221
4.3.4. Другие варианты применения .....................................................................222
4.4. Нахождение кратчайших путей из заданной вершины во все
остальные (Single – Source Shortest Paths, SSSP) .....................................................229
4.4.1. Обзор ..................................................................................................................229
4.4.2. SSSP на невзвешенном графе .......................................................................230
4.4.3. SSSP на взвешенном графе ...........................................................................232
4.4.4. SSSP на графе, имеющем цикл с отрицательным весом .......................237
4.5. Кратчайшие пути между всеми вершинами ....................................................242
4.5.1. Обзор ..................................................................................................................242
4.5.2. Объяснение алгоритма DP Флойда–Уоршелла.........................................243
4.5.3. Другие применения ........................................................................................246
Содержание 7
4.6. Поток ..........................................................................................................................253
4.6.1. Обзор ..................................................................................................................253
4.6.2. Метод Форда–Фалкерсона ............................................................................254
4.6.3. Алгоритм Эдмондса–Карпа ..........................................................................256
4.6.4. Моделирование графа потока – часть I......................................................257
4.6.5. Другие разновидности задач, использующих поток ..............................259
4.6.6. Моделирование графа потока – часть II ....................................................261
4.7. Специальные графы ...............................................................................................264
4.7.1. Направленный ациклический граф ............................................................265
4.7.2. Дерево .................................................................................................................274
4.7.3. Эйлеров граф ....................................................................................................276
4.7.4. Двудольный граф .................................................................................................277
4.8. Решения упражнений, не помеченных звездочкой .......................................287
4.9. Примечания к главе 4.............................................................................................291
Глаа 5. Математика .................................................................................................293
5.1. Общий обзор и мотивация ...................................................................................293
5.2. Задачи Ad Hoc и математика................................................................................294
5.3. Класс Java BigInteger ...............................................................................................303
5.3.1. Основные функции .........................................................................................303
5.3.2. Дополнительные функции ...........................................................................305
5.4. Комбинаторика........................................................................................................311
5.4.1. Числа Фибоначчи ............................................................................................311
5.4.2. Биномиальные коэффициенты ...................................................................312
5.4.3. Числа Каталана ................................................................................................313
5.5. Теория чисел.............................................................................................................319
5.5.1. Простые числа ..................................................................................................319
5.5.2. Наибольший общий
- 1
- 2
- 3
- 4
- . . .
- последняя (9) »
Последние комментарии
58 минут 30 секунд назад
2 часов 38 минут назад
1 день 8 часов назад
1 день 15 часов назад
1 день 15 часов назад
1 день 15 часов назад