Искусство поиска решения в нестандартной задаче

Москва, 2023

Потопахин В. В.

Искусство 
поиска решения 
в нестандартной 
задаче

2-е издание, электронное

УДК 004.421
ББК 32.973.26-018
П64

П64
Потопахин, Виталий Валерьевич.
Искусство поиска решения в нестандартной задаче / В. В. Потопахин. — 2-е изд., эл. — 1 файл pdf : 167 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; 
экран 10". — Текст : электронный.
ISBN 978-5-89818-565-7

Книга является заключительной в авторской трилогии книг после «Современное 
программирование с нуля» и «Искусство алгоритмизации».
Эта книга о том, что делать с задачей, если её решение нельзя вычитать в учебнике. 
Иначе говоря, — эта книга о творчестве в программировании. В тексте вы не найдете 
готовых рецептов, скорее, это описание того, как искать путь в интеллектуальной неизвестности, как выстроить свое мышление, так чтобы, не зная готовых формул и 
теорем, все же получить достаточно приличное решение за оптимальное время.
Издание предназначено для широкого круга начинающих программистов — 
школьников, студентов, а также всех думающих разработчиков программного обеспечения.

УДК 004.421 
ББК 32.973.26-018

Электронное издание на основе печатного издания: Искусство поиска решения в нестандартной задаче / В. В. Потопахин. — Москва : ДМК Пресс, 2016. — 166 с. — ISBN 978-5-97060-1983. — Текст : непосредственный.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было 
форме и какими бы то ни было средствами без  письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических 
ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность 
приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами 
защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-565-7
© Потопахин В. В., 2016 
© Оформление, издание, ДМК Пресс, 2016

ОГЛАВЛЕНИЕ

Введение ..........................................................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

Оглавление

Способ расчета выручки ...............................................................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

ВВЕДЕНИЕ

Книга, введение к которой вы сейчас читаете, третья в моем авторском курсе. Две первые – «Современное программирование с нуля» и 
«Искусство алгоритмизации» – посвящены вхождению в творчество 
и науку программирования. Книга «Поиск решения» должна познакомить вас с одним из возможных ответов на вопрос «Что делать с 
нетривиальной задачей, если её решение нельзя прочитать в хорошей 
книжке?».
Сразу обращаю ваше внимание на одно важное обстоятельство. 
Программирование можно понимать как технологию сборки решения 
из более мелких задач. Такой подход создал индустрию программирования. И программирование можно понимать как искусство поиска 
решения логически сложной задачи, сведение которой к более простым не решает проблемы, потому как она либо просто не разбивается 
на хорошие задачи, либо эти более простые все равно представляют 
собой систему, связанную сложной логикой. Технологическому подходу будет посвящена четвертая книга моего курса. А сейчас мы постараемся посмотреть на программирование как на интеллектуальное 
искусство.
Главная идея книги – показать процесс мыслительной деятельности таким, какой он есть на самом деле, с ошибками, тупиковыми 
вариантами, рождением красивой идеи. И что, пожалуй, главное – показать возможность такой организации мышления, при которой поиск решения становится системной и плановой работой. Конечно, по 
прочтении книги у вас не будет рецепта построения решения. Единственный метод борьбы с творческими проблемами – развитый мыслительный аппарат, поэтому все главы книги – это описание процесса 
поиска решения реальных задач. И поиск этот не бессистемный, путь 
к решению в каждой задаче лежит не только через интуитивные прорывы и даже не столько через них, сколько через анализ накопленной 
информации.
Основной метод, действие которого проявляется на каждом 
шагу, – это метод борьбы с неопределенностями. Решение каждой за

Введение

дачи представляется как последовательность вопросов «Что нам еще 
не ясно?» и «Как с этим бороться?». Возможно, некоторые из использованных задач искушенному «решателю» покажутся простыми, но 
цель максимально осложнить чтение не ставилась, поэтому задачи 
разноуровневые и поэтому книга может оказаться полезной для людей с самой различной степенью подготовки.
Базовый язык книги – Компонентный Паскаль, современная версия хорошо зарекомендовавшего себя языка, но некоторые решения 
записаны на псевдокоде. В принципе, базовый язык мог бы быть и 
другим, но все же Паскаль представляется наиболее удачным средством организации простого и в то же время достаточно строгого описания. Мой программисткий и главным образом преподавательский, 
учительский опыт говорит, что императивный стиль письма более соответствует природе программисткого мышления, чем функциональный или другие. Впрочем, даже если читатель не особенно 
приветствует императивные языки или язык Паскаль, то и такой читатель проблем с прочтением книги не испытает. Я уверен, что языковые особенности для большинства задач нашей предметной области 
не должны играть существенной роли. 

P.S.
Обратите внимание на правила, выведенные в процессе решения, 
их немного, и они не составляют какой-либо завершенной теории. 
Создать систему правил можно, но это опасное занятие. Завершенная 
теория, скорее всего, привела бы не столько к повышению эффективности мыслительного процесса, сколько к ограничению ваших творческих возможностей. Поэтому правила, сформулированные во всех 
последующих главах, не носят характера предписаний, это скорее небольшие советы, корректирующие направление мышления.

ГЛАВА 1. 

Как решается 
сложная задача

Существует один общий подход к поиску решения сложной задачи, 
независимо от того, из какой она области: математики, физики или 
программирования. Выражается он в трех простых предложениях:
1. Определим тип задачи.
2. Вспомним, какими методами нам или кому-нибудь другому 
доводилось решать задачи такого типа.
3. Попробуем применить эти методы к поставленной задаче.
Подход кажется логичным и разумным. Ведь большинство задач, с 
которыми мы сталкиваемся, кем-то уже решены, кто-то уже знает, как 
ответить на заинтересовавший вопрос, ответ уже есть в совокупной 
базе знаний человечества. Но накопленное общечеловеческое знание – это достаточно сложная штука. Оно не так доступно, как хотелось бы в силу своей огромности. Существуют и другие причины, по 
которым конкретный человек, сталкиваясь с реальной задачей, может 
не найти готового решения. Поэтому, несмотря на то что человечество в целом знает и умеет довольно много, отдельный человек часто 
встречается с ситуацией неопределенной и, следовательно, творческой. А в такой ситуации наш алгоритм из трех предложений уже не 
работает. 
Кроме того, если взять действительно интересную задачу, то окажется, что определить, к какому типу она относится, довольно сложно. И часто задача будет относиться не к одному типу, а к нескольким. Например, это может быть задача комбинаторного характера с 
применением графов, или это может быть задача моделирования физических процессов с использованием графики и методов численной 
математики и т. д.

Если бы была возможна исчерпывающая классификация задач, с конечным количеством классов, четко отделимых друг от друга, то это бы 

Глава 1. Как решается сложная задача

означало ограниченность программисткой науки. Программирование, 
как наука закончилось бы в момент написания последнего алгоритма на 
последний неразрешенный класс задач.

Вроде бы нет ничего страшного, просто в таких задачах мы имеем 
дело со сложными типами, и все равно можно действовать по той же 
схеме, то есть последовательно выполнять действия 1, 2, 3.
К сожалению, не получается. Во-первых, сложных типов можно 
сконструировать огромное количество, а чем типизация обширнее, 
тем сложнее выполнять пункт первый. Во-вторых, чем больше типов, тем сложнее в них ориентироваться, а в-третьих, тем сложнее 
отличить, где заканчивается один и начинается другой. Например, 
задача графического моделирования физического процесса, – это 
задача численной математики, физики или это графическая задача? 
В общем, при попытке составить какую-то классификацию мы столкнемся с таким количеством проблем, что невольно придет мысль поискать другой подход.
Попробуем подойти к сложным задачам с другой стороны. Начнем 
с небольшого, но очень важного замечания. Что бы мы не изобретали, 
все упирается в рождение идеи. А идея всегда рождается интуитивно, 
причем независимо от степени её гениальности и значимости. Происходит это так: вы некоторое время сосредоточенно размышляете на 
заданную тему, и вдруг приходит решение, причем не совсем понятно, 
откуда. Это называется интуицией. Существуют различные теории, 
объясняющие интуицию, откуда она берется, что она такое сама по 
себе, но для нас эти теории ровным счетом ничего не значат, так как 
не дают метода мышления.
Все серьезные идеи рождаются интуитивно, что огорчает, так как 
совершенно не ясно, как интуицией управлять, но, с другой стороны, 
совершенно не подготовленный человек вряд ли сможет сформулировать красивую идею, что вселяет надежду. Ведь если для рождения эффективной идеи нужна подготовка, то, значит, интуиция где-то в своей 
основе содержит систему, какой-то метод, а методу можно научиться.
Что такой метод может из себя представлять? Можно ли описать 
его точно? Конечно, нельзя ожидать, что общий метод решения творческих задач будет иметь алгоритмическую ясность. Невозможно 
себе представить, что такой метод будет описанием последовательности действий. Хотя, конечно, многие люди, когда речь идет о методе, представляют некую последовательность инструкций, выполнив 
которые, можно получить верный результат. Но это глубокая, принципиальная ошибка.

Пошаговое уточнение неопределенностей

Поэтому мы сразу и навсегда откажемся от идеи разработать такой 
всеобъемлющий алгоритм. Кроме того, мы решительно откажемся от 
попыток до конца понять тайну творчества. Это слишком невероятно, чтобы интуиция, творческий инсайт подлежал исчерпывающему 
логическому анализу. Это то, чего мы не будем делать. А попробуем  
разработать подход, помогающий удержать направление исследования и превращающий хаос творчества в осмысленный процесс.
Итак, мы ищем не методы решения задач, а методы организации 
мыслительной деятельности. Такова наша цель. И, чтобы её достичь, 
не будем строить теорию, а получим умения из практики. Решая задачи и отмечая то, что помогло получить решение, как-то обобщать свои 
наблюдения и, если получится, выводить общие правила.

Общие правила не должны иметь форму запретов, но надо четко понимать, что неограниченное творчество – это, по сути, хаос, из которого не 
появляется ничего продуктивного. Творчество творчеством, а любому исследователю необходимо получить приемлемое решение за ограниченное время. Поэтому дисциплина мышления должна ставить перед собой 
задачу, не создавая жестких запретов, тем не менее упорядочивать мыслительный процесс, нацеливая его на результат.

В этой книге большая часть глав посвящена конкретным проблемам, но есть несколько текстов общего значения, как, например, 
данная глава. А ниже мы рассмотрим подход, который, возможно, отражает самую общую идею поиска программисткого решения и учитывает именно программисткую специфику такой работы.  

Пошаговое уточнение 
неопределенностей

Рассмотрим пример несложной задачи. Пусть требуется разработать 
алгоритм расчета всех простых чисел, не превосходящих заданное 
число N. Если для решения не требуется особой эффективности, например верхняя граница не слишком велика, то можно воспользоваться самой очевидной идеей: алгоритм решения – это цикл, в теле 
которого для каждого очередного числа выясняется, простое оно или 
нет, и если простое, то число печатается как результат.
Для того чтобы принять решение относительно простоты очередного числа, необходимо проверить все числа, могущие быть его делителями, и если хотя бы один делитель есть, то проверяемое очередное 
не простое, иначе все-таки простое.

Глава 1. Как решается сложная задача

Идея вполне понятна, но все же вчитаемся в текст более внимательно, все ли здесь действительно хорошо. Один неясный пункт 
есть, это фраза, требующая проверить все числа, могущие быть делителями. Я из своего личного преподавательского опыта знаю, что ученики, недостаточно искушенные в задачах математической природы, 
о такие вещи спотыкаются довольно часто. «Как проверить?» – это и 
есть уточняющий вопрос, ответив на который, мы сможем записать 
решение в завершенной форме.

Заметим, что любое исследование начинается с искусства вопроса. Правильно заданный вопрос – это, образно говоря, половина ответа.

Рассмотрим более сложный пример. Есть группа людей со вполне определенными симпатиями и антипатиями друг к другу. Необходимо расставить их по рабочим позициям так, чтобы коллектив 
оказался психологически наиболее устойчивым. Возможно, психология дает какие-то методы решения подобных задач, но мы психологической наукой не владеем. А из соображений здравого смысла 
ясно, что необходимо организовать перебор всех возможных вариантов и выбрать из них вариант с наибольшим значением критерия 
устойчивости. 
Это своего рода макроидея, или решение в первом приближении. 
Здесь сразу видны следующие неопределенности. Во-первых, что 
значит перебирать варианты? Ясно, что с людьми этого делать не 
получится, ни в одном языке программирования нет такого термина – «люди». Эту неопределенность мы устраняем легко, пронумеровав группу. Тогда перебор вариантов расстановки людей сводится 
к перебору всех возможных перестановок их номеров. Кстати, появившийся термин «перестановка» наводит на мысль поискать какойнибудь уже известный алгоритм построения всех перестановок. Но 
здесь  возникает новая неопределенность. Совершенно не факт, что 
наше понимание термина перестановка совпадает с математическим 
пониманием. В этом надо убедиться.
Следующая неопределенность сложнее. Это критерий устойчивости. Ясно, что для каждой полученной перестановки необходимо 
что-то считать, и это что-то должно характеризовать устойчивость построенного коллектива. Мы должны определиться с математической 
формой этого критерия.    

Как известно, математика – это язык для точной записи знания, поэтому 
выше не зря появилось упоминание о математической форме записи кри