Понятие алгоритма, представление алгоритмов

ТЕМА 1. ВВЕДЕНИЕ В ПРОГРАММИРОВАНИЕ (4 ЧАСА)

Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

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

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

Алгоритм — заранее заданное понятное и точное предписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов.

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

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

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

Пример: Пусть даны числа А, В, С. Найти число Н, равное большему из них.

Решение задачи можно получить, действуя следующим образом. Вначале найдем большое из двух чисел, например А и В. Если А > В, то примем Н = А, иначе (т.е. если А < В), примем Н = В. Сравним теперь Н с С. Если Н > С, то значение Н следует принять в качестве искомого результата. Если Н < С, то Н следует принять равным С. Таким образом, в качестве результата получим величину Н, которая равна наибольшему из чисел А, В и С.

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

1. Если А > В, то принять Н=А и перейти к пункту 3. Иначе перейти к пункту 2.

2. Принять Н=В и перейти к следующему пункту.

3. Если Н > С, то перейти к пункту 5, иначе перейти к следующему пункту.

4. Принять Н=С, и перейти к пункту 5.

5. Стоп.

Наименование	Символ	Описание
Терминатор		Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных).
Процесс		Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения).
Решение		Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа.
Подготовка		Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию (установка переключателя, модификация индекса)
Предопределенный процесс		Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле).
Данные		Символ отображает данные, носитель данных не определен.
Границы цикла		Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие.
Соединитель		Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение.
Комментарий		Символ используют для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры.

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

Формы символов, установленные настоящим стандартом, должны служить руководством для фактически используемых символов. Не должны изменяться углы и другие параметры, влияющие на соответствующую форму символов. Символы должны быть, по возможности, одного размера.

Минимальное количество текста, необходимого для понимания функции данного символа, следует помещать внутри данного символа.

Если объем текста, помещаемого внутри символа, превышает его размеры, следует использовать символ комментария.

В схемах может использоваться идентификатор символов. Это связанный с данным символом идентификатор, который определяет символ для использования в справочных целях в других элементах документации (например, в листинге программы). Идентификатор символа должен располагаться слева над символом.

Потоки данных или потоки управления в схемах показываются линиями. Направление потока слева направо и сверху вниз считается стандартным. В случаях, когда необходимо внести большую ясность в схему (например, при соединениях), на линиях используются стрелки. Если поток имеет направление, отличное от стандартного, стрелки должны указывать это направление.

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

Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.

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

Алгоритмический язык в общем случае представляет собой систему обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Примером такой системы является псевдокод – описание структуры алгоритма на естественном, частично формализованном языке. В псевдокоде применяются формальные конструкции и математические символы.

При записи алгоритма с помощью псевдокода применяются следующие служебные слова и символы:

АЛГ – АЛГоритм;

НАЧ – НАЧало алгоритма;

КОН – КОНец алгоритма;

ВВОД – Ввод данных;

ВЫВОД – Вывод данных;

НЦ – Начало Цикла;

КЦ – Конец Цикла;

:= – присвоить значение;

// – комментарий.

После служебного слова АЛГ указывается название алгоритма.

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

АЛГ Пример

НАЧ

ВВОД А, В, С

ЕСЛИ А>B

ТО H:=A

ИНАЧЕ H:=B

ВСЁ

ЕСЛИ H<C

ТО H:=C

ВСЁ

ВЫВОД H

КОН