Реализация алгоритма на ЭВМ.
Здесь мы рассмотрим проблему реализации алгоритма на ЭВМ. Однако, прежде
введем ряд понятий.
Определение 9.1. Программа - алгоритм, представленный в форме пригодной для
его восприятия и выполнения ЭВМ.
Определение 9.2. Алгоритмический язык - формальная алгоритмическая система,
предназначенная для реализации алгоритмов на ЭВМ.
Итак, в чем суть рассматриваемой
проблемы? Программа, т.е. реализация алгоритма на ЭВМ, должна удовлетворять
ряду требований:
Программа должна быть эффективной:
восприниматься однозначно;
не требовать больших затрат на подготовку к выполнению и хранение;
быстро выполняться ЭВМ.
Преобразование алгоритма в форму программы человеком должно быть эффективным:
это должно требовать от человека разумных усилий, чем эти усилия меньше,
тем лучше;
величину этих усилий обычно измеряют временем, необходимым для написания
программы и количеством ошибок, допущенных при написании.
Программа должна быть легко читаемой и понимаемой разными людьми;
Программа должна быть эффективно проверяемой на корректность, т.е.
отсутствие ошибок.
Требование 3 связано с тем, что программа, как правило, эксплуатируется не
только ее автором. Поэтому, если в ходе ее эксплуатации у пользователя
возникают вопросы, связанные с ее работой, то он, прочтя программу, мог бы
найти ответы. Аналогичная ситуация возникает либо, когда мы хотим повторно
использовать уже существующую, не нами написанную программу, как фрагмент в
другой программе, либо когда нам необходимо модифицировать программу без ее
автора. Другой важной причиной для требования ясности текста программы является
обмен алгоритмами между людьми.
Ну и наконец, требование 4. Хорошо известно, что человеку свойственно
ошибаться. Поэтому, даже когда мы записываем алгоритм, корректность которого
была строго доказана, мы не можем гарантировать, что при перезаписи этого
алгоритма в форму программы, мы не сделали ошибок, т.е. в программе нет ошибок.
Корректность программы необходимо проверить.
Определение 9.3. Корректной будем
называть программу, которая для любых исходных данных из множества допустимых
исходных данных, дает правильный результат.
Подробнее мы рассмотрим понятия корректности программы, правильного
результата позднее, в лекции 18.
Заметим, что под множеством
допустимых исходных данных программы мы понимаем область применимости ее
алгоритма, представленную в надлежащей форме.
Итак, алгоритм должен быть записан
на алгоритмическом языке, чтобы быть исполненным. Сам алгоритмический язык
должен быть с одной стороны понятен ЭВМ, а с другой - он должен быть достаточно
выразителен для человека. Чтобы удовлетворять первому условию, алгоритмический
язык должен иметь:
строго определенный синтаксис и словарь.
словарь должен содержать только те действия и типы данных, с которыми может
работать ЭВМ.
Компьютер не может бегать, прыгать, плакать, смеяться, целоваться и т.д.
Поэтому, в словаре алгоритмического языка не может быть таких действий.
Существуют сотни разных
алгоритмических языков. Поскольку все они предназначены для записи алгоритмов,
то естественно что они имеют много общего. При изучении понятия алгоритма мы
уже выделили основные его компоненты:
данные, представленные константами и переменными;
тип данных, как множество возможных значений;
выражения, как действия, определяющие правило вычисления значения; Действия
в выражениях называются операциями.
действия, изменяющие состояние вычислительного процесса, и называемые
операторами.
К последнему пункту относятся действия, определяющие куда разместить
полученные значения, и действия, определяющие порядок вычисления.
Рассмотрим пример.
Пример 9.1.
Написать программу на Pascal, вычисляющую сумму гармонического ряда, т.е. ряда вида . Эта программа представлена
на рис. 9.1.
Program
Harmonic (input, output);
{ Программа Harmonic вычисляет сумму n первых членов гармонического ряда от
1 до п ;
Input: (пÎN)Ù(п>0);
Output: ;
}
1. var n, i :
integer; {n - количество суммируемых членов ряда;
i - параметр цикла
};
s :
real; {s - сумма ряда};
begin
{Ввод исходных данных}
write (¢Введите п= ¢) ; {Приглашение
к вводу}
readln (n) ; {Ввод исходных данных}
{Проверка исходных данных}
if n>0 then
{Вычисление суммы ряда}
begin
s:=1 ; {Инициализация
цикла}
i:=1;
while
i0¢)
end
{Program}.
Рис. 9.1. Программа для примера
9.1.
На этом рисунке строки 1 и 2 определяют набор используемых в программе
переменных и их типы. Операторы в строках 3 и 4 обеспечивают ввод исходного
значения n . Операторы в
строках 5 и 6 определяют начальные значения надлежащих переменных перед входом
в цикл. В строках 7 и 8 записан оператор цикла, организующий вычисление суммы
первых n членов
гармонического ряда. Последовательность действий i:=i+1; s:=s+1/i будет выполняться до тех пор, пока
выражение i