Искусство поиска решения в нестандартной задаче (1500,00 руб.)

Стр.3

Стр.4

Стр.5

УДК 004.421 ББК 32.973.26-018 П64 П64 Потопахин В. В. Искусство поиска решения в нестандартной задаче. – М.: ДМК Пресс, 2016. – 166 с.: ил. ISBN 978-5-97060-198-3 Книга является заключительной в авторской трилогии книг после «Современное программирование с нуля» и «Искусство алгоритмизации». Эта книга о том, что делать с задачей, если её решение нельзя вычитать в учебнике. Иначе говоря, – эта книга о творчестве в программировании. В тексте вы не найдете готовых рецептов, скорее, это описание того, как искать путь в интеллектуальной неизвестности, как выстроить свое мышление, так чтобы, не зная готовых формул и теорем, все же получить достаточно приличное решение за оптимальное время. Издание предназначено для широкого круга начинающих программистов – школьников, студентов, а также всех думающих разработчиков программного обеспечения. УДК 004.421 ББК 32.973.26-018 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. © Потопахин В. В., 2016 ISBN 978-5-97060-198-3 © Оформление, издание, ДМК Пресс, 2016

Стр.3

ОГЛАВЛЕНИЕ Введение ..........................................................5 ГЛАВА 1. Как решается сложная задача ..................7 Пошаговое уточнение неопределенностей ................................ 9 Формализация задачи ............................................................. 13 Решение как построение цикла Дейкстры ............................... 17 Цикл Дейкстры .............................................................................17 Алгоритмически конечная задача .................................................18 Интересный пример ................................................................ 19 Еще одно важное обстоятельство – запись алгоритма ............. 24 В заключение .......................................................................... 27 ГЛАВА 2. Полный перебор и его оптимизация ........ 28 Задачи, сводимые к перебору ................................................. 29 Проблема комбинаторного взрыва .......................................... 30 Главная мораль ........................................................................ 47 ГЛАВА 3. Как свести решение к задаче существования ................................................ 49 Главная идея ............................................................................ 49 Задача поиска квадратного корня ................................................50 Поиск отсутствующего числа ........................................................52 Решение уравнения Диофанта .....................................................58 ГЛАВА 4. Тождественные преобразования условий .......................................................... 64 Прежде всего необходимо убрать мусор из текста условия ..... 64 Что делать после генеральной уборки ..................................... 67 Задача о рекурсивной процедуре ............................................ 67 Задача о бесконечном слове ................................................... 69 Неопределенные уравнения .................................................... 71 Расчет оптимального плана производства ............................... 73 Математическая модель задачи ...................................................74

Стр.4

4 Оглавление Способ расчета выручки ...............................................................74 Итак, где здесь геометрия? ..........................................................75 Задача. Раскладывание колечек по штырькам ......................... 77 ГЛАВА 5. Моделирование физических процессов .... 86 Модель движения системы тел в гравитационном поле ........... 86 Задача о сложении прямого и отраженного колебаний ............ 93 Задача о колебательном движении пружины ........................... 97 ГЛАВА 6. Несколько интересных задач ............... 100 Задача Дейкстры ................................................................... 101 Задача о поиске пути с наибольшим весом ............................ 108 Задача о минимальном количестве заправок ........................ 113 Задача. Постфиксная и префиксная записи арифметического выражения ................................................ 120 Прямая задача............................................................................120 Обратная задача ........................................................................123 Задача. Самый длинный путь рубки ....................................... 125 Задача. Одинокий путник с плохой памятью .......................... 131 Задача. Закраска односвязного контура ................................ 141 Обсудим некоторые алгоритмические идеи ...............................142 Задача. Живая группа Го ........................................................ 152 Задача о черных пятнах на белой шкуре ................................ 156 В заключение ........................................................................ 157 ГЛАВА 7. Практикум ........................................ 158

Стр.5