1.2. Общие свойства алгоритмов
Для любого алгоритма характерны следующие свойства:
1) Детерминированность1) алгоритма. Описываемый метод должен быть общедоступен и настолько точно описан, что не остается место произволу. Его можно сообщить другому лицу в виде конечного списка указаний о том, как надлежит поступить в любой возникшей ситуации. При этом система величин, получаемых в данный момент времени, однозначно определяется величинами, полученными в предшествующие моменты, и эта однозначность не зависит от произвола действующего лица, а также от того, кто его выполняет.
2) Массовость алгоритма. Алгоритм служит для решения целой серии
(в принципе бесконечной) однотипных задач.
3) Дискретность алгоритма. Алгоритмический процесс происходит дискретно во времени, начало которого задается конечной системой величин, полученных в предыдущих шагах.
4) Направленность (результативность) алгоритма. Алгоритмический процесс, будучи применен к любой задаче заданного типа, должен завершиться через конечное число шагов и выдать результат.
5) Элементарность шагов (доступность) алгоритма. Система указаний должна состоять из команд настолько простых и элементарных, что процесс вычислений можно было бы поручить и машине.
Уровень «простоты» указаний естественно зависит от «интеллекта» исполнителя. В этом легко убедится, сравнив команды в программах, предназначенных для ЭВМ первого и пятого поколений.
1.3. Способы задания алгоритмов
Наиболее распространенный способ задания алгоритма в математике (и не только) – это словесный. Алгоритм задается в виде конечного перечня простейших указаний, не оставляющих возможности произвола исполнителя. Именно так описаны алгоритмы в примерах 1, 2, 7, 9, 10. Рассмотрим ещё один школьный пример – правило умножения обыкновенных дробей: «чтобы умножить дробь на дробь, умножают числитель на числитель и знаменатель на знаменатель. Первый результат есть числитель произведения, второй – его знаменатель. Если среди сомножителей имеются смешанные числа, то их предварительно обращают в неправильную дробь. Ещё до перемножения можно сокращать любой множитель числителя с любым множителем знаменателя».
Зададим это правило в виде последовательности простейших указаний:
а) Рассмотрим две дроби p 0 и q 0;
б) Если p или q
– смешанные числа, то запишем их в виде
неправильной дроби p
=
, q =
,
(a, b, c, d N).
Причем
HOD (a, b) = 1 и HOD (c, d) = 1;
в) Найдем HOД (a, d) = k и HOД (b, c) = r;
г) Сократим a и d на общий множитель k и получим соответственно числа a1 и d1;
d) Сократив b и с на общий множитель r и получим соответственно числа b1 и c1;
e) Умножим а1 и c1 и получим числитель произведения s=a1c1;
ж) Умножим b1 и d1 и получим знаменатель произведения t=b1d1;
з) Число
искомое;
и) Если дробь неправильная (т.е. s > t), то превратим его в смешанную дробь;
k) Конец
Задание алгоритма в виде конкретной программы для ЭВМ – так же является описательной формой, но только на искусственном языке (Бейсик, Фортран, Паскаль, Пролог…). Очень часто такому заданию предшествует графическая форма задания алгоритма (в виде блок схемы). Это форма имеет ряд преимуществ благодаря наглядности, обеспечивающая в частности, высокую «читаемость » алгоритма и явное отображение управления в нём.