Типовые структуры алгоритмов

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования «СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ИНДУСТРИАЛЬНЫЙ УНИВЕРСИТЕТ»

Кафедра прикладной информатики

ТИПОВЫЕ СТРУКТУРЫ АЛГОРИТМОВ

Рекомендации к выполнению лабораторной работы по дисциплине «Информатика»

Специальности:

Городское строительство и хозяйство (270105) Производство строительных материалов, изделий и конструкций

(270106)

Теплогазоснабжение и вентиляция (270109) Водоснабжение и водоотведение (270112)

Проектирование зданий (270114) Экспертиза и управление недвижимостью (270115)

Новокузнецк 2010

УДК 004.421(07) Т343

Рецензент:

Кафедра систем информатики и управления ГОУ ВПО СибГИУ

(Зав. кафедрой д.т.н., проф. Т.В. Киселева)

Т343 Типовые структуры алгоритмов: метод. указ. / Сост. Л.Д. Павлова, Н.В. Балицкая; – 2-е изд. испр. и перераб. : СибГИУ. – Новокузнецк, 2010. – 26 с.

Описаны типовые структуры алгоритмов, способы их представления, технологии создания блок-схем.

Предназначена для студентов специальностей: 270105 Городское строительство и хозяйство, 270106 Производство строительных материалов, изделий и конструкций, 270109 Теплогазоснабжение и вентиляция, 270112 Водоснабжение и водоотведение, 270114 Проектирование зданий, 270115 Экспертиза и управление недвижимостью, а также может быть рекомендована для студентов других специальностей.

ЦЕЛЬ РАБОТЫ

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

ВВЕДЕНИЕ

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

В 20-х годах прошлого века задача точного определения понятия алгоритма стала одной из центральных проблем математики. Попытки выработать такое определение привели к возникновению теории алгоритмов.

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

3

ОБЩИЕ СВЕДЕНИЯ

Определение алгоритма

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

Термин «алгоритм» применяют весьма широко не только в области вычислительной техники и программирования. У каждого человека сформировано свое, пусть даже большей частью интуитивное, понимание смысла этого термина.

Полагают, что термин «алгоритм» происходит от имени средневекового персидского математика IX века Абу Джафара Мохамеда ибн Мусы аль-Хорезми. Редакция последней части имени ученого в европейских языках привела к образованию термина «алгорифм» или «алгоритм». Приведем несколько вариантов определения алгоритма из различных источников.

Алгоритм [algorithm - англ.] - это заранее заданная последовательность четко определенных правил или команд для получения решения задачи за конечное число шагов [7].

Алгоритм – это система операций, применяемых по строго определенным правилам, которая после последовательного их выполнения приводит к решению поставленной задачи [6].

Алгоритм – это формальное описание способа решения задачи путем ее разбиения на конечную во времени последовательность действий (элементарных операций) [1].

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

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

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

4

получит результат даже в том случае, когда он не понимает существа решаемой задачи.

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

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

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

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

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

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

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

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

Существуют следующие способы представления алгоритмов:

словесное описание, построчная запись, графическое описание, запись на языке программирования.

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

5

может оказаться очень объемным и трудным для восприятия человеком.

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

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

Запись алгоритма на языке программирования представляет собой форму изображения алгоритма в виде программы на конкретном алгоритмическом языке (языке программирования высокого уровня).

ПРАВИЛА ПОСТРОЕНИЯ БЛОК-СХЕМ

При графическом описании отдельные функции алгоритмов отображаются в виде условных графических изображений - символов. Перечень условных графических символов, их наименование, форма, размеры, отображаемые функции и правила выполнения алгоритмов приведены в ГОСТ 19.701-90 [4].

Стандартом устанавливаются следующие соотношения между геометрическими размерами символов:

-размер а (высота блока), должен выбираться как величина кратная 5: 10, 15, 20… (мм);

-размер b (ширина блока) определяется по формуле b = 1,5·а

(мм).

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

а=10 мм, b=15 мм.

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

6

Таблица - Основные графические символы, используемые для описания алгоритмов

Название

Изображение

Назначение

символа

символа

символа

Пуск - останов

Начало

или завершение

0,5a

процесса

обработки

данных

b

Данные

0,25a

Ввод или вывод данных

a

b

Процесс

Вычисление по формулам

a

b
Решение	Проверка	условия	и
a	выбор	решения	в
	зависимости от условия
b

Подготовка

0,25a

Организация

циклических

a

вычислительных

процессов

b

Предопределенный

Использование отдельно

процесс

a

описанных

алгоритмов

или программ

b

Комментарий

а

Применяется

для

пояснения

символов

на

схеме

0,5а

7

Название

Изображение

Назначение

символа

символа

символа

Соединитель

ø 0,5а

Указывает

на

связь

между

прерванными

линиями

потока,

соединяющими символы

на блок-схеме

Линии

потока

Обозначают

направление

информации

потока

информации

от

одного символа на схеме

к другому. Если линия

потока

информации

направлена

снизу

вверх

или справа налево, то она

заканчивается стрелкой

Пересечение линий

Применяют

в

случае

потока

пересечения не связанных

информации

линий потока на схеме

Слияние

линий

Применяют

в

случае

потока

слияний

линий

потока

информации

информации, каждая

из

которых

направлена

к

одному символу на схеме

Выполнение алгоритма всегда начинается с блока Пуск и заканчивается блоком Останов.

Блок Данные используется для ввода или вывода данных. Блок Процесс используется для описания тех действий,

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

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

Блок Подготовка определяет начало циклической группы действий в алгоритме.

8

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

Комментарии используются для записи пояснительного текста к блокам. Наличие комментариев делает блок-схему понятной для любого пользователя.

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

Если информация передается снизу вверх или выполняется правосторонний обход, то такое направление считается противоестественным. В этом случае направление линии потока информации обязательно указывается стрелкой.

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

ТИПОВЫЕ СТРУКТУРЫ АЛГОРИТМОВ

Различают следующие виды алгоритмов: линейные,

разветвляющиеся, циклические, комбинированные (смешанные).

Линейный алгоритм

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

Задача. Составить алгоритм вычисления высот треугольника по формулам:

h	A	=	t	;	h =	t	;	h =	t	,
			2a		B	2b		C	2c
где t = p( p −a)( p −b)( p −c),						p = a +b +c ;
								2

a, b, c - стороны треугольника.

9

Блок-схема линейного алгоритма

Ввод: a, b, c

p =a+2b+c

t = p( p −a)( p −b)( p −c)

hA = 2ta ; hB = 2tb ; hC = 2tc

Вывод: hA, hB, hC

Выполнение линейного алгоритма

1.Вводятся значения переменных a, b, c.

2.Вычисляется значение переменной р.

3.Вычисляется значение переменной t.

4.Вычисляются значения переменных hA, hB, hC.

5.Выводятся значения переменных hA, hB, hC.

Разветвляющийся алгоритм

Разветвляющимся называется такой алгоритм, в котором естественный порядок выполнения действий нарушается в зависимости от условия задачи.

Задача. Составить алгоритм вычисления значения функции Y для заданных значений а, х:

	x,		если x ≥ 0
a
Y =
	2	,	если x < 0
ax

10