“В МИР ИНФОРМАТИКИ” № 67

Н.М. Тимофеева,
г. Обнинск Калужской обл.

Школа программирования. Как решать задачи?

Стремление решить задачу заложено в самой природе человека.
Д.Пойа

Для чего нужно разрабатывать программы? Прежде всего для того, чтобы поручить компьютеру решить задачу, причем часто такую, которую человек может решить и сам. Только компьютер сделает это быстрее. Конечно, надо “объяснить” компьютеру, как именно надо решать задачу. А для того чтобы объяснить, как решать (хоть компьютеру, хоть соседу по парте), надо самому знать, как. Очень понятно о решении задач писал известный математик Джордж Пойа. Родился он в Венгрии в 1887 году, преподавал в Швейцарии и в США. Его имя и фамилию произносят по-разному в разных странах. Так, в Венгрии он известен как Дьердь Пойа, в Германии — как Георг Полиа, а в США — как Джордж Пойа.

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

Пойа был сторонником применения технологий решения задач при изучении математики. Более всего он известен благодаря своим выдающимся книгам “Как решать задачу” и “Математика и правдоподобные рассуждения” с примерами, доступными школьникам.

В кратком изложении идеи его книг можно выразить следующим образом.

1. Понимание задачи

Прежде всего вы должны понять задачу.

• Что неизвестно? Что дано? Что является условием?
• Возможно ли выполнить условие? Условие достаточно для определения неизвестных величин? Или оно недостаточно? Или избыточно? Или противоречиво?
• Сделайте рисунок. Введите соответствующие обозначения.
• Разделите условие задачи на части. Вы можете записать их?

2. Разработка плана

• · Определите связь между исходными данными и неизвестным. Если прямая связь не может быть найдена, возможно, вам придется рассмотреть вспомогательную задачу. В итоге вы должны получить план решения.
• · Встречалась ли вам такая задача раньше? Может быть, вы сталкивались с подобной задачей в несколько другом виде?
• · Вы знаете похожую задачу? Известна вам теорема или формула, которая может быть применена?
• · Посмотрите на искомую величину! И постарайтесь вспомнить знакомую задачу с таким же или похожим неизвестным.
• · Вот задача, похожая на вашу и решенная раньше. Можете вы воспользоваться ею? Можете применить ее результат? Можете воспользоваться способом решения этой задачи? Можете ввести некоторые вспомогательные элементы, чтобы можно было использовать решенную задачу?
• ·· Могли бы вы переформулировать задачу? Могли бы вы сформулировать ее еще по-другому? Вернитесь к условию задачи.
• · Если вы не можете решить предлагаемую задачу, постарайтесь сначала решить какую-нибудь подобную задачу. Не могли бы вы представить более понятную подобную задачу? Более общую задачу? Более частную задачу? Аналогичную задачу? Можете решить часть задачи? Оставьте только часть условия, отбросьте другую часть; насколько неизвестная величина тогда будет определена, как можно ее изменить? Можно ли извлечь что-либо полезное из исходных данных? Не могли бы вы представить себе другие данные, подходящие для нахождения неизвестного. Не могли бы вы изменить неизвестное и исходные данные или и то и другое, если необходимо, для того чтобы новое неизвестное и новые исходные данные стали ближе друг к другу?
• · Все исходные данные вы применили? Вы полностью применили условие? Все математические понятия, включенные в задачу, вы приняли во внимание?

3. Выполнение плана

• · Выполните свой план.
• · Проверяйте каждый шаг, выполняя свой план решения. Вам ясно, что шаг верен? Можете доказать, что он безошибочен?

4. Взгляд назад

• · Проверьте полученное решение.
• · Можете проверить результат? Можете проверить ход решения?
• · Можете решить по-другому? Можете понять это сразу?
• · Можете применить этот результат или способ решения для какой-нибудь другой задачи?

Другими словами, идею книги Джорджа Пойа “Как решать задачу” можно выразить так: понять, запланировать, выполнить, проверить.

Далее мы расскажем, как о технологии решения задач по Пойа применительно к программированию пишет Грэм Саммерс в своем учебнике “Программирование на Visual Basic”. Эта технология в учебнике используется в каждом примере программирования. В ближайших выпусках газеты “В мир информатики” будут рассмотрены несколько примеров из книги, поэтому знакомство с указанной технологией будет для вас полезным. Итак, отрывки из книги Г.Саммерса.

Джордж Пойа преподавал математику в Станфордском университете (Калифорния). Он известен своими статьями о решении задач. Однажды он написал: “Пытаясь решать задачи, вы должны наблюдать и повторять то, что делают другие, когда решают задачи, и в конце концов вы учитесь решать задачи, решая их”.

В течение этого курса¹ вы будете наблюдать и повторять, но, что более важно, вы будете решать задачи самостоятельно. В своей книге под названием “Как решать задачу” Пойа описал шаги, необходимые для решения задачи:

1. определить задачу;
2. запланировать решение;
3. выполнить решение;
4. оглянуться назад.

1. Определение задачи

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

2. Планирование решения

После исследования задачи рассматриваются шаги, которые требуются для решения², и порядок, в котором они должны быть выполнены. Шаги, которые необходимы для решения задачи и их последовательность, — это и есть алгоритм³. Такое определение может использоваться и как компьютерный термин, и в обычной жизни. Например, существуют алгоритмы для вязания джемперов, выполнения умножения столбиком, выпекания хлеба и т.д. В компьютерной терминологии планирование решения означает разработку алгоритма.

3. Выполнение решения

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

4. Взгляд назад

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

Рассмотрим несколько примеров алгоритмов:

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

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

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

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

Ошибки

Существуют три основных типа ошибок, которые могут проявиться при попытке выполнить процесс. Первый тип — синтаксические ошибки. Это ошибки в записи алгоритма, которые делают его непонятным для исполнителя. Это может быть ошибка правописания или символ, который не может быть переведен, например, инструкция “добавить 20@0 грамм простой муки”.

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

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

1. Какие 4 главных шага надо сделать при решении задачи?

2. Дайте определение понятия “алгоритм”.

3. Почему при решении задачи так важен последний шаг — “взгляд назад”?

4. Ниже представлены примеры процессов.

1. Выпекание хлеба.
2. Установка вашего видеомагнитофона на запись в ваше отсутствие.
3. Выполнение умножения двух чисел столбиком.

Для каждого случая ответьте на следующие вопросы:

1. в какой форме обычно выражается соответствующий алгоритм;
2. приведите примеры простых шагов, на которые может быть разделен алгоритм;
3. что является вводом;
4. что является выводом;
5. в чем будет заключаться “взгляд назад”?

5. Приведите несколько примеров неправильного ввода для следующих процессов:

— изготовление модели планера из древесины;

— функционирование уличного телефона;

— деление одного целого числа на другое.

6. Какие из следующих процессов могут завершиться:

— вымешивание теста для хлеба;

— деление числа 3 на 11 столбиком;

— поиск лох-несского чудовища;

— приготовление обжаренных в масле овощей?

При каких обстоятельствах это может произойти?

7. Определите разницу между:

— синтаксической ошибкой и ошибкой исполнения;

— ошибкой исполнения и логической ошибкой.

Литература

1. Summers Graeme. Programming with Visual Basic. Second Edition (Visual Basic version 6). Nelson, 1999.

2. Пойа Д. Как решать задачу: Пособие для учителей. Перевод с англ. М.: Учпедгиз, 1959.

3. http://www.mathgym.com.au/htdocs/polyab.htm.

¹ Речь идет о курсе, обсуждаемом на страницах книги Г.Саммерса. — Ред.

² Для этого, конечно, надо ответить на вопросы, на которые обращает внимание Д.Пойя (см. выше по тексту). — Ред.

³ Возможно, что на уроках информатики вы рассматривали другое определение понятия “алгоритм”. — Ред.

⁴ Ясно, что термин “:процессор” здесь не имеет непосредственного отношения к процессору компьютера, а связан с понятием “исполнитель алгоритма”. — Ред.