2015-10-22
5819
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Павлыш В.Н., Ефименко К.Н., Добровольский Ю.Н.
«ОСНОВЫ АЛГОРИТМИЗАЦИИ»
Донецк 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. Циклический вычислительный процесс.
Любой алгоритм сложной структуры может быть получен путем комбинированного использования типовых структур.
