Первый шаг в решении задачи

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

До участия в гонках А, В. С и D сделали следующие прогнозы:

А сказал, что выиграет В.

В сказал, что D будет последним.

С сказал, что А будет третьим.

D сказал, что предсказание А правильно.

Только одно из этих предсказаний сбылось, и оно было сделано победителем. В какой последовательности А, В, С и D пришли к финишу?

После внимательного прочтения условия задачи и анализа данных не составит труда понять, что поскольку предсказания А и D совпадают, то они неправильны. Следовательно, ни А, ни D не являются победителями. Таким образом, мы сделали первый шаг в решении задачи, и для того чтобы получить окончательное решение, нужно просто расширить наши знания. Если предсказание А было ложно, значит, В также не является победителем. Остается один участник С, следовательно, он и выиграл гонки, и его предсказание является верным. Значит, А пришел к финишу третьим. То есть порядок, в котором финишировали участники, либо CBAD, либо CDAB. Первая последовательность исключается, так как предсказание В неверно. Следовательно, участники прибыли к финишу в таком порядке — CDAB.

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

Другой метод решения задачи — найти связанную с ней задачу, которую легче решить или решение которой уже найдено, а затем попытаться применить это решение к текущей. Этот метод важен при разработке программ. Часто основная трудность в написании программы состоит не в решении частного случая задачи, а в нахождении общего алгоритма, который можно использовать для решения всех задач определенного типа. Если говорить более точно, столкнувшись с задачей создания программы для сортировки списка имен по алфавиту, мы должны не создать программу, сортирующую какой-то один список, а найти общий алгоритм, который можно использовать для сортировки любого списка имен. Следовательно, хотя команды

Поменять местами имена Дэвид и Алиса. Поместить имя Кэрол между Алиса и Дэвид. Поместить имя Боб между Алиса и Кэрол.

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

Еще один способ решения задачи — применить пошаговую детализацию (step-wise refinement), не пытаясь решить всю задачу со множеством деталей сразу. При пошаговой детализации задача разбивается на несколько подзадач. Главная идея этого метода состоит в том, что, разбивая исходную задачу на несколько подзадач, мы решаем ее в несколько шагов, найти решение которых проще, чем решить всю задачу. Пошаговая детализация подразумевает, что эти шаги также будут разбиты на меньшие шаги, и так до тех пор, пока вся задача не будет сведена к набору легко решаемых подзадач.

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

Решения, найденные методом пошаговой детализации, имеют естественную модульную структуру. Этот факт является главной причиной популярности пошаговой детализации в построении алгоритмов. Если алгоритм имеет естественную модульную структуру, тогда его легко адаптировать к модульному представлению, что приводит к созданию легко выполнимой программы. Кроме того, модули, порождаемые этим методом, согласуются с понятием командного (коллективного) программирования, когда несколько человек разрабатывают какой-либо программный продукт сообща. Как только задача разбивается на подзадачи (или модули), члены команды могут работать над этими подзадачами независимо друг от друга.

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

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

Когда вы ступаете с причала в лодку, ваша шляпа падает в воду, и вы не замечаете этого. Скорость течения реки равна 2,5 мили в час, и ваша шляпа плывет вниз по течению. Между тем вы плывете в лодке вверх по течению со скоростью 4,75 миль в час относительно воды. Через 10 минут вы обнаруживаете пропажу шляпы, разворачиваете лодку и пытаетесь догнать шляпу. Через какое время вы ее догоните?

Большинство студентов и любителей карманных калькуляторов начнут решение задачи с определения того, как далеко отплывет лодка и уплывет шляпа за эти 10 минут. Затем они определят, за какое время лодка доберется до места, куда отплыла шляпа. Но, когда лодка достигнет этого места, шляпа переместится дальше вниз по течению. Таким образом, студент начнет применять разные методы вычислений или окажется в ловушке, пытаясь посчитать, где будет находиться шляпа в тот момент, когда лодка достигнет места, где шляпа была.

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

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