Содержание.
Глава 1. Стратегии решения задач 16
Классические головоломки 18
Лисица, гусь и кукуруза 18
Задача: как пересечь реку? 18
Вынесенные уроки 22
Головоломки со скользящими плитками 22
Задача: скользящая восьмерка 22
Задача: скользящая пятерка 24
Вынесенные уроки 26
Судоку 27
Задача: заполнить квадрат «Судоку» 27
Вынесенные уроки 28
Замок Кварраси 29
Задача: открыть инопланетный замок 29
Вынесенные уроки 32
Обшие подходы к решению задач 32
Планируйте решения 32
Переформулируйте задачи 34
Делите задачи 35
Начните с того, что знаете 36
Упрощайте задачи 36
Ищите аналогии 38
Экспериментируйте 39
Не расстраивайтесь 39
Упражнения 41
Глава 2. Истинные головоломки 42
Обзор языка С++, используемого в этой главе 43
Шаблоны вывода 43
Задача: половина квадрата 43
Задача: квадрат (упрощение задачи с половиной квадрата) 44
Задача: линия (еще большее упрощение задачи с половиной квадрата) 44
Задача: посчитать на уменьшение, считая на увеличение 45
Задача: равнобедренный треугольник 46
Обработка ввода 49
Задача: проверка контрольной суммы Луна 50
Разбиение проблемы на части 51
Задача: преобразовать символ цифры в целое число 53
Задача: проверка контрольной суммы Луна, фиксированная длина 54
Задача: проверка простой контрольной суммы, фиксированная длина 55
Задача: положительное или отрицательное 57
Соберем все детали вместе 58
Отслеживание состояния 60
Задача:.декодирование сообщения 60
Задача: чтение трех- или четырехзначного числа 64
Задача: чтение трех- или четырехзначного числа, дальнейшее упрощение 65
Заключение 73
Упражнения 73
Глава 3. Решение задач с массивами 76
Обзор основных свойств массивов 77
Сохранение 78
Копирование 78
Извлечение и поиск 79
Поиск определенного значения 79
Поиск по критерию 80
Сортировка 81
Быстрая и простая сортировка с помощью функции qsort 81
Легко модифицируемый алгоритм сортировки — сортировка вставками 82
Вычисление статистических показателей 84
Решение задач с помощью массивов 84
Задача: нахождение моды 84
Рефакторинг 88
Массивы фиксированных данных 91
Нескалярные массивы 93
Многомерные массивы 95
В каких случаях использовать массивы 99
Упражнения 103
Глава 4. Решение задач с указателями и динамической памятью 105
Обзор основных свойств указателей 106
Преимущества использования указателей 107
Структуры данных, размер которых определяется во время выполнения программы 107
Динамические структуры 108
Разделение памяти 108
В каких случаях использовать указатели 109
Вопросы памяти 110
Стек и куча 110
Объем памяти 113
Время существования переменной 115
Решение задач с указателями 115
Строка переменной длины 116
Задача: операции со строками переменной длины 116
Проверка на специальные случаи 122
Копирование созданной динамически строки 123
Связные списки 126
Задача: отслеживание неизвестного количества студенческих карточек 126
Построение списка узлов 127
Добавление узлов в список 130
Обход списка 132
Заключение и дальнейшие шаги 135
Упражнения 135
Глава 5. Решение задач с классами 138
Обзор основных свойств классов 139
Цели использования классов 141
Инкапсуляция 141
Повторное использование кода 142
Разделение задачи 142
Сокрытие 143
Читабельность 145
Выразительность 146
Создание простого класса 146
Задача: список класса 146
Базовый фреймворк класса 147
Служебные методы 151
Классы с динамическими данными 154
Задача: отслеживание неизвестного количества записей студентов 155
Добавление узла 157
Перегруппировка списка 159
Деструктор 163
Глубокое копирование 164
Общий обзор классов с динамической памятью 168
Ошибки, которых следует избегать 169
Фальшивый класс 169
Однозадачники 170
Упражнения 171
Глава 6. Решение задач с помощью рекурсии 173
Обзор основ рекурсии 174
Головная и хвостовая рекурсия 174
Задача: подсчет количества попугаев 174
Подход 1 175
Подход 2 176
Задача: выявление лучшего клиента 178
Подход 1 179
Подход 2 181
Большая рекурсивная идея 183
Задача: вычисление суммы элементов целочисленного массива 184
Распространенные ошибки 186
Слишком много параметров 187
Глобальные переменные 188
Применение рекурсии к динамическим структурам данных 189
Рекурсия и связные списки 190
Задача: подсчет отрицательных чисел в односвязном списке 191
Рекурсия и двоичные деревья 192
Задача: нахождение наибольшего значения в двоичном дереве 194
Функции-обертки 195
Задача: нахождение количества листьев в двоичном дереве 195
В каких случаях использовать рекурсию 198
Аргументы против рекурсии 198
Задача: отображение элементов связного списка в прямом порядке 200
Задача: отображение элементов связного списка в обратном порядке 201
Упражнения 202
Глава 7. Решение задач с помощью повторного использования кода 204
Хорошее и плохое повторное использование кода 205
Основы работы с компонентами 206
Кодовый блок 206
Алгоритмы 207
Шаблоны 207
Абстрактные типы данных 208
Библиотеки 209
Изучение компонентов 210
Исследовательское обучение 210
Применение полученных знаний на практике 211
Задача: староста 211
Анализ решения задачи выбора старосты 214
Обучение по мере необходимости 215
Задача: эффективный обход 215
Когда следует искать компонент 216
Нахождение компонента 217
Применение компонента 218
Анализ эффективного решения задачи с обходом 222
Выбор типа компонента 223
Процесс выбора компонента 225
Задача: выборочная сортировка 225
Сравнение результатов 229
Упражнения 230
Глава 8. Думайте как программист 232
Разработка собственного мастер-плана 233
Использование своих сильных и слабых сторон 233
Планирование с учетом недостатков кодирования 234
Планирование с учетом недостатков дизайна 236
Планирование с учетом ваших сильных сторон 238
Составление мастер-плана 240
Решение любой задачи 242
Задача: жульничество при игре в «Виселицу» 243
Нахождение возможности для жульничества 244
Необходимые операции для обмана в игре «Виселица» 246
Исходный дизайн 248
Первичное кодирование 249
Анализ первоначальных результатов 257
Искусство решения задач 258
Изучение новых навыков программирования 259
Новые языки 260
Выделите время на учебу 260
Начните с того, что вы знаете 261
Изучите отличия 261
Изучайте хорошо написанный код 262
Новые навыки для языка, который вы уже знаете 263
Новые библиотеки 263
Выберите курс 264
Заключение 265
Упражнения 266
Предметный указатель 268
