Книга: Пять уроков Великого Магистра, или повесть о том, как Петя Бочкин изучал программирование

ЧТО ТАКОЕ АЛГОРИТМ?

ЧТО ТАКОЕ АЛГОРИТМ?

В математике существует несколько определений алгоритма. Я не стану их здесь приводить. Смысл этих определений, максимально упрощая дело, сводится к тому, что под словом «алгоритм» подразумевается порядок действий, которые необходимо выполнить, чтобы решить ту или иную задачу.

В нашей повседневной жизни мы то и дело используем самые различные алгоритмы.

Сегодня утром, перед тем, как выйти на улицу, я поглядел в окно. Шел дождь, и я надел плащ. Таким образом, почти не раздумывая, автоматически я решил задачу, которую можно сформулировать так: что делать, когда за окном идет дождь? А вот и алгоритм его решения: ЕСЛИ за окном идет дождь, ТО перед выходом на улицу нужно надеть плащ. Ба, да ведь это же старая наша знакомая — конструкция РАЗВЕТВЛЕНИЯ!

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

Тоже знакомая конструкция, не правда ли?

А знаете, чем я занимался весь сегодняшний день? Копал картошку. Не один, конечно, а вместе со всем своим родным коллективом. Привезли нас на поле, раздали ведра и — вперед! Из земли — в ведро, из ведра — в мешок, мешок — в грузовик. Была у нас женщина-бригадир из местных, красивая, с перстнем на пальце. Она картошку не копала, а только командовала.

— А домой нас скоро отпустят? — спросил у нее кто-то.

— А вот, миленькие, десять машин в город отправите тогда и сами поедете, — словоохотливо ответила женщина.

Так составилась задача под названием «Когда домой?» Вот алгоритм ее решения: из земли — в ведро, из ведра — в мешок, мешок — в машину. Повторять, ПОКА не нагрузим десять машин.

Узнаете? Правильно, это конструкция ЦИКЛА.

Надо сказать, что алгоритмы решения не только житейских, но и любых других задач сводятся к последовательности выполнения некоторых действий (программисты часто называют их «шагами»). А любая последовательность шагов может быть описана на языке вот этих самых только что перечисленных конструкций. Можно сказать, что любая программа, введенная в машину, представляет из себя не что иное, как алгоритм, записанный на языке таких конструкций. Поэтому-то машинные языки называются алгоритмическими.

А все ли задачи имеют алгоритмы для решения? Далеко не все.

Те, кто читал роман В. Гюго «Собор Парижской богоматери», помнят историю урода Квазимодо, который полюбил красавицу Эсмеральду. Понятно, что Квазимодо очень хотелось бы, чтобы и Эсмеральда полюбила его. Однако, увы, эта задача решения не имела. Какие бы действия ни предпринимал Квазимодо, в какой бы последовательности он ни выстраивал их, сердце красавицы (вообще говоря, весьма глупой барышни, лично я отказываюсь понимать, что в ней такого нашел Квазимодо) навсегда осталось закрытым для него.

Существуют такие задачи и в науке. В 1900 году в Париже состоялся Всемирный математический конгресс. Со своим докладом на нем выступил знаменитый математик Давид Гильберт. Для того, чтобы «проникнуть в предстоящие успехи нашей науки и тайны ее развития в начинающемся столетии», Гильберт выбрал двадцать три математические проблемы. С тех пор эти проблемы называются задачами Гильберта. До сегодняшнего дня они привлекают внимание всех математиков мира. Вот, например, как формулируется десятая проблема Гильберта. Дано: произвольное алгебраическое уравнение с целыми коэффициентами. Требуется: выяснить, существует ли у данного уравнения решение в целых числах? Оказывается, нет. Нет такого алгоритма, который позволил бы решить эту задачу. Это доказал советский математик Ю. В. Матиясевич.

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

Но вот я спрашиваю: кто знает, как написать гениальный роман? Или хотя бы гениальное стихотворение? Ага, никто не знает! Тем не менее, гениальные произведения создавались и будут создаваться. Но алгоритм, или, что то же самое, рецепт, инструкцию для их написания создать невозможно. Итак, составление алгоритма — это первое, с чего начинается процесс программирования.

Второй шаг — запись алгоритма в виде программы. В одном из алгоритмических языков (их множество: фортран, алгол, пи-эл, бэйсик, паскаль…).

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

Кто может писать без ошибок? Никто. В том числе и программисты.

Введенную программу нужно отладить, то есть найти и устранить все ошибки.

Поэтому — четвертый шаг — отладка программы.

Вот, пожалуй, и все. Дальше начинается работа непосредственно самой машины.

Оглавление книги