§ 5. Исполнители алгоритмов

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

Что же такое исполнитель? Упрощенно исполнителя можно представить себе как некоторое устройство управления, соединенное с набором инструментов. Устройство управления понимает алгоритмы и организует их выполнение, командуя соответствующими инструментами. А инструменты производят действия, выполняя команды управляющего устройства. Скажем, если человека рассматривать, как исполнителя алгоритмов, то мозг - его управляющее устройство, а инструменты - руки, ноги, глаза, нос, рот, уши... (продолжите список самостоятельно). У роботов-манипуляторов, станков с программным управлением и ЭВМ управляющее устройство - процессор; что же касается набора инструментов, то он зависит от того, для решения каких задач предназначен тот или иной исполнитель.

Ясно, что как бы ни были разнообразны возможности исполнителя, они всегда ограничены. Иначе для решения любой задачи годился бы один-единственный алгоритм:

 Получить исходные данные. 
 Найти решение. 
 Сообщить ответ.

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

Исполнитель! Не допускай недопустимых действий!

Поясним сказанное на примере. Допустим, требуется решить уравнение х² - 9х + 8 = 0. Ученик десятого класса, который хорошо знает, как решать квадратные уравнения, не нуждается в объяснениях. Для него алгоритм решения будет состоять из двух действий:

Решить уравнение. Сообщить результат.

Для ученика восьмого класса, который еще не знает формулу корней квадратного уравнения, придется написать более длинную инструкцию:

 Вычислить значение выражения 92 - 4 · 8 (дискриминант уравнения). 
 Извлечь из полученного числа квадратный корень и обозначить результат буквой р. 
 Вычислить значение выражения (9 + р) / 2 и обозначить результат буквой у. 
 Вычислить значение выражения (9 - р) / 2 и обозначить результат буквой z. 
 Сообщить числа у и z.

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

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

Задачи на вычисления - один из наиболее широких классов задач, решаемых на ЭВМ. Исполнителя, который будет выполнять вычислительные алгоритмы, мы назовем ВЫЧИСЛИТЕЛЕМ. Он имеет дело с числами и переменными, обозначающими числа. На первых порах мы ограничимся следующим набором его допустимых действий:

1. Запросить исходные данные и обозначить их буквами. Соответствующую команду можно записывать, например, так: "Запросить...", указывая вместо многоточия буквы, обозначающие соответствующие данные.

Например:

 Запросить А. 
 Запросить А, В и С.

2. Сообщить результаты вычислений или какой-нибудь текст: "Сообщить...". Здесь вместо многоточия ставятся буквы или алгебраические выражения либо текст, заключенный в кавычки. Выполняя это действие, ВЫЧИСЛИТЕЛЬ печатает значения указанных выражений или текст (без кавычек). Вот примеры таких действий:

 Сообщить X. 
 Сообщить X и Y, а также Z. 
 Сообщить "Я работаю ВЫЧИСЛИТЕЛЕМ!".

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

 Присвоить... значение...

Вместо второго многоточия пишется выражение, значение которого надо вычислить, а вместо первого многоточия - латинская буква, которой ВЫЧИСЛИТЕЛЬ обозначит это значение. Например:

 Присвоить С значение А + В. 
 Присвоить X значение 2С.

Разумеется, записывая в своих тетрадях алгоритмы, вы можете писать команды по-разному. Можно сокращать слова или, наоборот, добавлять слова, поясняющие, скажем, смысл переменных. Например:

 Запр. v,

или

 Запросить значение скорости v.

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

 Сообщить X или У.

поскольку ВЫЧИСЛИТЕЛЬ не может сам выбрать, какое из чисел ему сообщать (у него нет соответствующего допустимого действия).

Совсем иначе будет обстоять дело при записи программ для ВЫЧИСЛИТЕЛЯ, имитируемого ЭВМ. К сожалению, ЭВМ не способна понимать всевозможные фразы русского языка. Поэтому приходится жестко фиксировать запись команд. Например, при работе на ЭВМ переменные разрешается обозначать только латинскими буквами, а в записи команды присваивания слово "Присвоить" не пишется, а вместо слова "значение" ставится знак " = ". Скажем, вместо команды

 Присвоить С значение А + В

вы будете писать

 С = А + В

Обратите внимание, что точка в конце команд не ставится. О том, как записываются при работе на ЭВМ другие команды ВЫЧИСЛИТЕЛЯ, вы узнаете на лабораторной работе 2. Вот пример алгоритма для ВЫЧИСЛИТЕЛЯ.

 Запросить А, В. 
 Присвоить С значение (А + В)/2. 
 Сообщить С.

Этот алгоритм выполняется так. Сначала ВЫЧИСЛИТЕЛЬ запросит у нас два числа. Когда мы сообщим их ему, он обозначит первое число буквой А, второе число - буквой В. Затем ВЫЧИСЛИТЕЛЬ найдет полусумму чисел А и В, а результат обозначит через С. После этого он сообщит значение С.

У вас, наверно, возникло ощущение, что с допустимыми действиями ВЫЧИСЛИТЕЛЯ вы освоились. И действительно, действия "Запросить" и "Сообщить" довольно просты. А вот действие "Присвоить" похитрее. Давайте немного изменим разобранный только что алгоритм:

 Запросить А, В. 
 Присвоить А значение (А + B)/2. 
 Сообщить А.

Теперь полусумма чисел А и В будет обозначена не буквой С, а буквой Л. Что же произойдет с тем числом, которое было обозначено буквой А до выполнения действия "Присвоить..."? ВЫЧИСЛИТЕЛЬ его забудет! И следующим своим действием он сообщит новое значение переменной А (т. е. полусумму исходных чисел).

Переменную удобно представить себе как ящик, в котором можно хранить любое число. Когда в этот "ящик" кладут новое число, старое бесследно исчезает - допустимые действия ВЫЧИСЛИТЕЛЯ не позволяют никакой переменной присваивать два значения одновременно. Букву, обозначающую переменную, будем называть именем этой переменной. Имена переменных можно использовать в записи различных алгебраических выражений. При вычислении значений этих выражений имена заменяются числами из соответствующих "ящиков". Запросив число, ВЫЧИСЛИТЕЛЬ "кладет" его в "ящик", предварительно обозначив этот "ящик" соответствующей буквой.

Вот как можно представлять себе выполнение последнего из приведенных алгоритмов.

По команде "Запросить А, В" ВЫЧИСЛИТЕЛЬ возьмет два "ящика", "прикрепит" на первый ящик табличку "А", на второй - "В":

Затем он обратится к нам с вопросом, какие числа надо обозначить буквами А, В. Узнав эти числа, скажем, 2 и 12, ВЫЧИСЛИТЕЛЬ "положит" их в соответствующие "ящики":

После этого он приступит к выполнению второго действия. Взяв значения переменных А и В, ВЫЧИСЛИТЕЛЬ найдет их полусумму - число 7. Это число он "положит" в "ящик" с табличкой "А":

Ничто не исчезает так бесследно, как старое значение переменной после присваивания нового значения

Как видите, число 2 уже забыто. Следующим действием ВЫЧИС ЛИТЕЛЬ сообщит значение переменной А - число 7, взяв его из соответствующего "ящика".

С имитацией на ЭВМ действий ВЫЧИСЛИТЕЛЯ вы познакомитесь во время лабораторной работы 2.

Итак, для решения задачи надо выбрать исполнителя и лишь затем составлять алгоритм решения, используя только допустимые действия этого исполнителя. А что требуется от исполнителя составленного нами алгоритма? Только четкое выполнение каждого действия, входящего в алгоритм. Ему не надо знать, для каких целей предназначается алгоритм (компьютеру "безразлично", управляет он доменным процессом или предсказывает погоду на завтра).

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

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

Один и тот же исполнитель может быть сымитирован на ЭВМ многими способами. При этом содержание действий остается неизменным, а их названия могут быть разными. Так, при имитации ВЫЧИСЛИТЕЛЯ средствами языка Бейсик вместо слов "Запросить" и "Сообщить" используются английские слова "INPUT" и "PRINT".

Вопросы

1. Что такое исполнитель алгоритмов?

2. Что такое допустимые действия исполнителя?

3. Какие действия допустимы для ВЫЧИСЛИТЕЛЯ?

4. Что означают для ВЫЧИСЛИТЕЛЯ следующие команды?

а) Запросить а, 6, с.

б) Сообщить "Спасибо!".

в) Сообщить а + b.

г) Присвоить а значение х + у - z.

5. Что значит сымитировать исполнителя с помощью ЭВМ?

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

1. Исполнитель умеет:

умножать число на 2;

увеличивать число на 1.

а) Составьте для этого исполнителя алгоритм получения числа 100 из единицы.

б*) Сколько действий в самом коротком из таких алгоритмов?

2. Исполнитель умеет из любой дроби а /b получать любую из дробей (a - b)/b, (a + b)/b и b/a. Как получить из дроби 1/2 дробь 1/4? А как получить 67/91?

3. Составьте алгоритм нахождения с помощью карандаша и линейки центра тяжести фигур на рисунке 4.

Рис. 4. Фигуры

4. На столе лежат две двухкопеечные монеты и три пятака так, как показано на рисунке 5.

Рис. 5. Монеты

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

Рис. 6. Монеты

При этом исполнитель не может раздвигать монеты или менять их местами. Составьте для этого исполнителя алгоритм преобразования цепочки монет на рисунке 5 в цепочку монет на рисунке 7:

Рис. 7. Монеты

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

а) Составьте необходимый алгоритм;

б*) Решите эту задачу при дополнительном ограничении: монеты запрещается поднимать над поверхностью стола.

6*. Исполнитель умеет заменять в слове одну букву на другую так, чтобы получившееся слово имело смысл. Например,

"СЛОН"→"СЛОГ" Напишите алгоритм превращения "МУХИ" в "СЛОНА".

7. Какие задачи решит ВЫЧИСЛИТЕЛЬ, выполнив следующие алгоритмы:

а)

 Запросить a, d, n. 
 Присвоить S значение (a + d (n - 1)) n/2. 
 Сообщить S.

б)

 Запросить b, q, n. 
 Присвоить S значение  
 Сообщить S.

8. Злоумышленник поменял местами действия в алгоритме вычисления среднего арифметического из квадратов трех чисел, предназначенном для ВЫЧИСЛИТЕЛЯ:

 Присвоить а значение  
 Запросить а, b, с. 
 Сообщить "Среднее арифметическое квадратов равно". 
 Сообщить а.

Восстановите правильный порядок действий.

9. Исправьте следующий алгоритм решения уравнения х² - 2х - 14 = 0, предназначенный для ВЫЧИСЛИТЕЛЯ:

 Присвоить d значение 22 + 4 · 14. 
 Присвоить р значение . 
 Присвоить х значение . 
 Сообщить "Корни уравнения равны". 
 Сообщить первое значение х. 
 Сообщить второе значение х.

10. Автомобиль проехал три участка пути разной длины с разными скоростями. Составьте для ВЫЧИСЛИТЕЛЯ алгоритм нахождения средней скорости автомобиля.

11. Даны длины сторон треугольника.

а) Составьте для ВЫЧИСЛИТЕЛЯ алгоритм, выполняя который он сначала вычислит (используя действие "Присвоить"), а затем сообщит полупериметр треугольника, его площадь и радиус вписанной окружности.

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

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

12*. Какими допустимыми действиями вы снабдили бы исполнителя, который будет производить построения с помощью циркуля и линейки?