Графический способ описания алгоритмов

ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ НА ЭВМ

Так как ЭВМ является "слепым" исполнителем программ, то успешное решение задачи полностью определяется квалификацией программиста.

В общем случае решение задачи на ЭВМ можно разбить на следующие этапы:

* постановка задачи;

* разработка алгоритма;

* составление программы;

* трансляция программы;

* отладка и выполнение программы;

* анализ результатов.

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

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

Алгоритм должен обладать следующими основными свойствами:

* детерминированность (определенность) – при заданных исходных данных обеспечивается однозначность искомого результата;

* массовость – пригодность для задач данного типа при исходных данных, принадлежащих заданному подмножеству;

* результативность – реализуемый вычислительный процесс выполняется за конечное число этапов с выдачей осмысленного результата;

* дискретность – разбиение на отдельные этапы, выполнение которых не вызывает сомнений.

Под программой понимают описание, воспринимаемое ЭВМ и достаточное для решения на ней определенной задачи. Для создания программы используются искусственные языки, называемые языками программирования. ЭВМ, как правило, непосредственно воспринимает и выполняет программы, написанные только на одном из языков программирования – машинном языке для данной ЭВМ. С помощью специальных программ можно получить опосредованное "понимание" других языков. Одна из таких программ – транслятор. Транслятор – это программа, осуществляющая перевод текстов с одного языка на другой, т.е. с входного языка (Паскаль, Си, Пл-1 и т.д.) на машинный язык реальной ЭВМ. Программа, попадающая на вход транслятора, называется исходной, а результат трансляции – объектной программой.

Одним из самых трудоемких этапов решения задачи на ЭВМ является разработка алгоритма. Человечество разработало эффективный алгоритм завязывания шнурков на ботинках. Многие дети с пятилетнего возраста могут это делать. Но дать чисто словесное описание этого алгоритма без картинок и демонстрации - очень трудно.

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

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

Графический способ записи алгоритмов – наиболее наглядный и распространенный. Он основан на использовании геометрических фигур (блоков), каждая из которых отображает конкретный этап процесса обработки данных, соединяемых между собой прямыми линиями, называемыми линиями потока. Обозначение и назначение элементов графических схем алгоритмов приведено в табл.1. В поле каждого блочного символа указывают выполняемую функцию. При необходимости справа можно поместить комментарии, относящиеся к данному блоку или направлению потока. Каждый блочный символ (кроме начального и конечного) помечается порядковым номером. Для отличия ситуаций пересечения и слияния потоков последняя изображается точкой. Линии потока, имеющие направление вверх или направо, дополняются стрелками.

Таблица 1

Геометрическая фигура	Назначение
	Начало и завершение алгоритма, прерывание процесса обработки данных или выполнения программы. a выбирается из ряда 5,10,15мм и т.д.,а b=1,5a или 2a
	Выполнение операции или группы операций, в результате которых изменяются значение, форма представления или расположение данных
	Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий

Окончание табл. 1

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

По своей структуре различают следующие типы алгоритмов: линейные, разветвляющиеся и циклические. В линейных схемах алгоритмов все предписания выполняются одно за другим. Например, алгоритм вычисления длины окружности по известной площади круга (рис.2). В разветвляющихся схемах алгоритмов для конкретных исходных данных выполняются не все заданные предписания. Однако какие именно предписания будут выполняться, конкретно определяется в процессе выполнения алгоритма в результате проверки некоторых условий. Разветвляющийся алгоритм всегда избыточен. Примером разветвляющегося алгоритма является алгоритм, приведенный на рис.3 и определяющий, пройдет ли график функции y=3x+4 через точку с координатами x1,y1.

  Рис. 4

Рис. 3

Рис. 2  

Циклическим алгоритмом называется такой алгоритм, в котором можно выделить многократно повторяющуюся последовательность предписаний, называемую циклом. Для таких алгоритмов характерно наличие параметра цикла, которое перед входом в цикл имеет начальное значение, а затем изменяется внутри цикла. Имеется также предписание о проверке условия окончания цикла. Применение циклов сокращает текст алгоритма и, в конечном итоге, длину программы. Примером циклического алгоритма может служить алгоритм, приведенный на рис.4 и определяющий факториал натурального числа n. В этом алгоритме введена дополнительная переменная i, которая является параметром цикла и изменяется от начального значения 1 до конечного значения n c шагом 1. На каждом шаге итерации искомая величина f умножается на переменную цикла. В реальных задачах, как правило, сочетаются все три типа алгоритмов. Способ описания алгоритма с помощью алгоритмического языка подробно рассматривается в следующем разделе.

Дата добавления: 2014-11-18