Алгоритмы и способы их описания

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Павлыш В.Н., Ефименко К.Н., Добровольский Ю.Н.

МЕТОДИЧЕСКОЕ ПОСОБИЕ

«ОСНОВЫ АЛГОРИТМИЗАЦИИ»

Донецк 2012

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Павлыш В.Н., Ефименко К.Н., Добровольский Ю.Н.

МЕТОДИЧЕСКОЕ ПОСОБИЕ

«ОСНОВЫ АЛГОРИТМИЗАЦИИ»

Утверждено

на заседании кафедры ВМиП

Протокол № 1 от 30 августа 2012 г.

Утверждено

методической комиссией ДонНТУ

Протокол № 4 от 27 октября 2012 г.

Донецк 2012

УДК 681.3.06 (071)

Методические пособие. «ОСНОВЫ АЛГОРИТМИЗАЦИИ» / В.Н. Павлыш, К.Н. Ефименко, Ю.Н. Добровольский. – Донецк: ДонНТУ, 2012. – 75 с.

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

Рекомендации по выбору вариантов приведены в конце пособия.

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

Авторы: В.Н. Павлыш

К.Н. Ефименко

Ю.Н. Добровольский

Отв. за выпуск: В.Н. Павлыш, проф.

Ó Павлыш В.Н., 2012

Ó ДонНТУ, 2012

СОДЕРЖАНИЕ

1. Алгоритмы и способы их описания 2. Алгоритмы линейной структуры 3. Алгоритмы разветвляющейся структуры 4. Алгоритмы циклической структуры 4.1. Структура и основные типы циклов 4.2. Алгоритмы нахождения суммы, произведения и количества вычисленных значений 4.3. Циклы с неизвестным числом повторений 4.4. Вложенные циклы 5. Алгоритмы обработки одномерных массивов 5.1. Ввод и вывод элементов одномерного массива 5.2. Нахождение максимального и минимального элементов массива 5.3. Сортировка элементов массива 5.4. Циклический сдвиг элементов массива 5.5. Добавление и удаление элементов массива 6. Алгоритмы обработки двумерных массивов 7. Алгоритмы, содержащие вспомогательные подзадачи Задания к контрольной работе Задание №1. Организация линейного и разветвляющегося вычислительных процессов Задание №2. Организация циклов с известным числом повторений Задание №3. Организация циклов с неизвестным числом повторений Задание №4. Организация вложенных циклов Задание №5. Обработка одномерных массивов Задание №6. Обработка двумерных массивов Задание №7. Использование процедур и функций Рекомендации к выполнению контрольной работы

АЛГОРИТМЫ И СПОСОБЫ ИХ ОПИСАНИЯ

Алгоритм – это строгая последовательность арифметических и логических действий, которая однозначно определяет процесс вычисления результата в зависимости от исходных данных. Слово “алгоритм” произошло от арабского слова “algoritmi”, возникшего из имени хорезмийского математика IX века аль-Хорезми.

Основными свойствами алгоритма являются:

результативность – алгоритм должен обеспечивать получение результата за конечное число шагов;

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

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

Наиболее распространенными способами описания алгоритма являются:

словесно-формульный – алгоритм записывается в виде текста с формулами по пунктам, определяющими последовательность действий;

аналитическая запись – алгоритм записывается с использованием формул или специальных символов, например, стенографических;

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

Образцом словесно-формульного описания алгоритма может служить следующий пример:

вычислить значение выражения y = 2 ∙ a – (x + 6)

1. Ввести значения величин а и х. 2. Выполнить сложение х и 6 ® x+ 6. 3. Выполнить умножение а на 2 ® 2 a. 4. Вычесть из полученного произведения значение полученной суммы ® 2 a-(x+ 6 ). 5. Вывести значение полученного результата у.

Программа, записанная на каком-либо языке программирования, также является формой представления алгоритма.

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

Таблица 1. Графические символы, применяемые

при составлении блок-схем

№ п/п	Наименование блока	Обозначение	Выполняемое действие
	Начало или конец алгоритма		Показывает начало или конец алгоритма
	Ввод или вывод		Обеспечивает ввод или вывод данных в алгоритме
	Арифметический		Выполняет арифметические вычисления
	Логический		Выполняет проверку заданного логического условия
	Модификации		Заголовок цикла «Для»
	Предопределенный процесс		Вызов подпрограммы
	Линии потока		Указывают связь и направление движения между блоками
	Соединитель		Указывает связь между прерванными линиями потока
	Межстраничный соединитель		Указывает связь между частями блок-схемы, которые расположены на разных страницах
	Комментарии	текст	Запись пояснения к блоку или к линии потока

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

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

Существует три основных типовых структуры алгоритма:

1. Линейный вычислительный процесс.

2. Разветвляющийся вычислительный процесс.

3. Циклический вычислительный процесс.

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