§ 4. Понятие алгоритма

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

 Достать ключ. 
 Вставить ключ в замочную скважину. 
 Повернуть ключ 2 раза против часовой стрелки.

Вынуть ключ. А теперь представьте себе, что вас пригласили в гости. Наверняка вы попросите подробно и точно объяснить, как добраться. Вот как может выглядеть объяснение:

 Выйти из дома. 
 Повернуть направо. 
 Пройти 2 квартала до автобусной остановки. 
 Сесть в автобус № 25, идущий к центру города. 
 Проехать 3 остановки. 
 Выйти из автобуса.

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

  Достать ключ. 
 Повернуть ключ 2 раза против часовой стрелки. 
 Вставить ключ в замочную скважину. 
 Вынуть ключ.

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

Мы можем теперь сказать, что алгоритм - это организованная последовательность действий. Эту формулировку, конечно, нельзя считать определением алгоритма. Например, мы не объяснили, что означают слова "организованная" и "действия". Скажем сразу - абсолютно строгого определения алгоритма мы не дадим. Понятие алгоритма в информатике является фундаментальным. Таким же, какими являются понятия точки, прямой и плоскости в геометрии, пространства и времени в физике, вещества в химии и т. д. Поэтому мы не будем стремиться дать всеобъемлющее определение алгоритма, а будем уточнять смысл этого понятия в последующих параграфах.

Нам предстоит еще неоднократно записывать алгоритмы, поэтому давайте договоримся, выделяя порядок действий в алгоритме, записывать действия в столбик (как и в приведенных примерах).

Вопросы

1. Почему нельзя дать строгого определения алгоритма?

2. Какое общее свойство алгоритмов вы можете назвать?

Задания для самостоятельного выполнения

1. Приведите примеры неопределяемых понятий в следующих школьных предметах:

а) литература;

б) русский язык;

в) история;

г) биология.

2. Некий злоумышленник выдал следующий алгоритм за алгоритм получения кипятка:

 Налить в чайник воду. 
 Открыть кран газовой горелки. 
 Поставить чайник на плиту. 
 Ждать, пока вода не закипит. 
 Поднести спичку к горелке. 
 Зажечь спичку. 
 Выключить газ.

Исправьте алгоритм, чтобы предотвратить несчастный случай. 3. Имеются цинк, 96%-ная серная кислота, вода, а также колба и пробирка. Исправьте ошибки в алгоритме получения водорода:

 Поставить колбу на стол. 
 Налить в колбу кислоту. 
 Налить в колбу воду. 
 Собрать выделяющийся газ в пробирку. 
 Бросить в колбу цинк.

4°. Какие действия вы бы добавили, чтобы был выполним следующий алгоритм переправы через Волгу в районе г. Саратова:

 Подойти к реке. 
 Войти в реку. 
 Идти по дну, пока не выйдешь на другой берег.

5. Пусть дан отрезок АВ. Определить, для решения какой задачи предназначен следующий алгоритм:

 Поставить ножку циркуля в точку А. 
 Установить раствор циркуля равным длине отрезка АВ. 
 Провести окружность. 
 Поставить ножку циркуля в точку В. 
 Провести окружность. 
 Провести прямую через точки пересечения окружностей.

6. Пусть даны действительные числа 6, q и натуральное число п. Какая задача решается с помощью следующего алгоритма?

 Вычислить qn и обозначить результат буквой С. 
 Вычислить 1 - С и обозначить результат буквой D. 
 Вычислить 1 - q и обозначить результат буквой Е. 
 Разделить D на Е и обозначить результат буквой F. 
 Умножить F на b и обозначить результат буквой S. 
 Сообщить S.

7. Дана фраза на английском языке: "Mike goes to school". Составьте алгоритм перехода от утвердительной формы к вопросительной: "Does Mike go to school?"

8. Составьте алгоритм построения биссектрисы угла с помощью циркуля и линейки.

9. Даны число χ и набор действий: разделить полученное число на 3; умножить χ на 2; сообщить результат; прибавить к полученному числу 4; вычесть из полученного числа 7.

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

10. Имеются два кувшина емкостью 3 л и 8 л. Напишите алгоритм, выполняя который можно набрать из реки 7 л воды (разрешается пользоваться только этими кувшинами).

11. (Старинная задача.) Некий человек должен перевезти в лодке через реку волка, козу и капусту. Каждый раз он может перевезти только либо волка, либо козу, либо капусту. На одном берегу нельзя оставить вместе козу и волка, а также козу и капусту. Составьте алгоритм переправы на другой берег. (Эта задача встречается в рукописях VIII века. Уже тогда интересовались алгоритмами!)

12°. Разведывательный дозор в составе двух человек подошел к реке. Мост был разрушен, а река слишком глубока и широка, чтобы переправиться через нее вброд или вплавь. К счастью, около берега в маленькой лодке проплывали два мальчика. Как переправиться на этой лодке через реку, если она может выдержать только либо одного взрослого, либо двух мальчиков?

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