Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Формы представления алгоритма

Раздел 5 Алгоритмизация и программирование

Тема 5.1 Алгоритм и его свойства. Способы записи алгоритма

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

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

Свойства алгоритма

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

2) Определенность (или детерминированность). Это свойство состоит в том, что каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует дополнительных указаний или сведений о решаемой задаче.

3) Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

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

Формы представления алгоритма

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

· словесная – запись на естественном языке,

· графическая – запись в виде схемы (блок-схемы),

· запись на специальном языке (алгоритмическом языке или псевдокоде).

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

Например: записать алгоритм определения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Евклида). Алгоритм может быть следующим:

· задать два числа;

· если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;

· определить большее из чисел;

· заменить большее из чисел разностью большего и меньшего из чисел;

· повторить алгоритм с шага 2.

Данный способ плохо формализуем и практически применяется редко.

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

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

Основные элементы блок-схемы алгоритма. Правила выполнения схем и обозначения для отдельных операций процесса обработки данных регламентирует Государственный стандарт (ГОСТ 19.701-90 «Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения»).

Алгоритмические языки близки к естественному языку, поэтому для них характерны: алфавит, операции – слова, операторы – предложения, синтаксис – правила написания.

Правила построения конструкций в алгоритмическом языке более «жесткие». Это означает, что алгоритмические языки допускают меньше разнообразия для описания действий алгоритма, чем естественный язык и привычная математическая символика, и машина однозначно понимает любую конструкцию языка. Например, для умножения двух переменных a и b общепринятая математическая символика допускает несколько возможных форм записи:

ab a×b a´b a*b.

На алгоритмическом же языке эту операцию можно записать только единственным образом как a*b. Алгоритмический язык занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в алгоритмическом языке используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.

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

Общий вид алгоритма:

алг название алгоритма (аргументы и результаты)

нач описание промежуточных величин

| последовательность команд (тело алгоритма)

кон

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон – телом алгоритма.

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

Примеры предложений алг:

алг объем_и_площадь_цилиндра (аргвещ R, H, резвещ V, S)

алг диагональ (аргцел N, аргцелтаб A[1:N, 1:N], резлит otvet)

Пример записи на алгоритмическом языке:

алг произведение (аргцел n, m, резцел s)

начцел i

| ввод n, m

| s:=0

| i:=0

| нцпока i<n

| | s:=s+m

| | i:=i+1

| кц

| вывод s

кон