3. Алгоритм, алгоритмические языки, программа

Прежде чем любая задача будет решена на ЭВМ, должен быть найден (составлен) алгоритм ее решения.

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

^* (Основы информатики и вычислительной техники: Проб. учеб. пособие для средн. учеб. заведений: В 2 ч./А. П. Ершов, В. М. Монахов, А. А. Кузнецов и др.; Под ред. А. П. Ершова, В. М. Монахова.— М.: Просвещение, 1985.— Ч. I.— С. 17)

В пробном учебном пособии "Основы информатики и вычислительной техники" и в методическом пособии для учителей "Изучение основ информатики и вычислительной техники" приводится достаточно много алгоритмов различного типа.

Вначале рассмотрим так называемые "житейские" алгоритмы, приведенные в учебнике "Основы информатики и вычислительной техники" (ч. I, с. 24). Например, алгоритм пользования междугородным телефоном может быть представлен в виде следующей последовательности приказаний:

1. Снимите телефонную трубку.
2. Опустите в автомат монету в 15 копеек.
3. Дождитесь появления непрерывного сигнала.
4. Наберите код нужного вам города.
5. Дождитесь появления прерывистого сигнала.
6. Наберите номер телефона нужного вам абонента.
7. Если услышите частые прерывистые сигналы, значит ваш абонент занят и вы должны выполнить приказание 10; если же услышите редкие прерывистые сигналы, то выполните приказание 8.
8. Нажмите кнопку "Разговор" и начинайте говорить.
9. В процессе ведения разговора опускайте в автомат монеты в 15 копеек.
10. По окончании разговора повесьте телефонную трубку на рычаг автомата.

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

Теперь рассмотрим некоторые алгоритмы действий с текстом.

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

1. Возьми очередное слово группы слов.
2. Выдели у слова две последние буквы.
3. Сравни эти две буквы с буквосочетаниями -ть, -ти, -чь.
4. Если выделенные две буквы совпадают хотя бы с одним из этих сочетаний, то выполни действие 5, если не совпадают, то выполни действие 8.
5. Сделай вывод: взятое слово есть инфинитив русского глагола.
6. Возьми для исследования следующее слово.
7. Перейди к выполнению действия 2.
8. Сделай вывод: взятое слово не является инфинитивом русского глагола.
9. Перейди к выполнению действия 6.

Второй пример. Пусть необходимо подсчитать, сколько букв в каком-то слове. Эта задача будет решена после выполнения следующего ряда предписаний (приказаний):

1. Очисти счетчик числа букв.
2. Возьми первую букву слова.
3. Прибавь 1 в счетчик числа букв.
4. Возьми очередную букву слова.
5. Если букв уже нет, то выполни приказание 6, если же буквы еще есть, выполни правило 3.
6. Посмотри, какое число находится в счетчике числа букв.

Поиск алгоритма является основной процедурой во всем процессе решения любой задачи с помощью ЭВМ. Человек, решающий такую задачу, должен сочетать в себе аккуратность бухгалтера с проницательностью разведчика, фантазию автора детективных романов с трезвой практичностью экономиста^*.

^* (Ершов А. П. О человеческом и эстетическом факторах в программировании // Научно-техническая революция и человек.- М.: Наука, 1977,- С. 189.)

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

^* (Алгоритм, записанный на таком алгоритмическом языке, называют еще машинным алгоритмом.)

В общем виде алгоритмический язык - это система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения.

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

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

При переводе алгоритма на алгоритмический язык проводится максимальная детализация процесса решения задачи. Алгоритмический язык содержит лишь правила двух типов: безусловные (типа "сделай то-то") и условные, имеющие лишь два возможных выхода - "да" и "нет" (например, если выполнено некоторое условие, переходи к выполнению действия А, если же оно не выполнено, то переходи к выполнению действия Б). Так, приведенный выше алгоритм для определения принадлежности русских слов к инфинитиву глагола может быть представлен на алгоритмическом языке так, как показано на рисунке 4. Фигуры-кружки алгоритмического языка условно обозначают номер ниже- или вышестоящего блока алгоритмического языка, к которому необходимо перейти для дальнейших действий. Номера в кружках показывают также номера блоков алгоритмического языка, от которых пришло "указание" на выполнение действия, зафиксированного в блоке полной конфигурации, на который направлены стрелки от кружков.

Педагогическая практика показывает, что представление алгоритмов решения задач в виде блок-схем является самым эффективным средством для усвоения понятия алгоритма, приемов и методов алгоритмизации задач. Блок-схемы обладают значительно большей наглядностью, чем другие способы записи алгоритмов и языки программирования. К аналогичному выводу приводят и психологические исследования в области усвоения знаний.

Рис. 4

Именно при таком изображении процедуры решения задачи видны ее основные составные части, элементарные действия и связи между ними.

Один раз найденный алгоритм решения какой-либо задачи может быть представлен на любом языке программирования для ЭВМ. При этом каждый блок алгоритма заменяется одним или несколькими операторами (командами) какого-либо языка программирования?

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