2. Функциональная структура программы

2. Функциональная структура программы

2.1. Алгоритм и алгоритмизация

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

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

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

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

На практике получили известность два способа изображения алгоритмов:

- в виде пошагового словесного описания;

- в виде блок-схем.

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

2. Блок-схема и ее элементы

Блок-схема – это последовательность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19002-80 и ГОСТ 19003-80 "Схемы алгоритмов и программ".

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

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

При соединении блоков следует использовать только вертикальные и горизонтальные линии потоков.

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

Прочие потоки могут быть помечены или оставлены непомеченными.

Линии потоков должны быть параллельны линиям внешней рамки или границам листа

Название	Элемент	Комментарий
Процесс		Вычислительное действие или последовательность вычислительных действий
Решение		Проверка условия
Модификация		Заголовок цикла
Предопределенный процесс		Обращение к процедуре
Документ		Вывод данных, печать данных
Перфокарта		Ввод данных
Ввод/Вывод		Ввод/Вывод данных
Соединитель		Разрыв линии потока
Начало, Конец		Начало, конец, пуск, останов, вход и выход во вспомогательных алгоритмах
Комментарий		Используется для размещения надписей
Горизонтальные и вертикальные потоки		Линии связей между блоками, направление потоков
Слияние		Слияние линий потоков
Межстраничный соединитель		Нет

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

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

Пример блок-схемы алгоритма вычисления периметра Р и площади S квадрата со стороной длины A.

Рис. 1. Линейный алгоритм

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

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

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

Для пояснения рассмотрим решение задачи нахождения значения функции z = y/x.

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

5. Циклические алгоритмы

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

Различают циклы с наперед известным и наперед неизвестным количеством проходов.

Пример 1. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное количество проходов. Для этого решим следующую задачу. Указать наименьшее количество членов ряда натуральных чисел 1, 2, 3,..., сумма которых больше числа К.

Рис.3. Циклический алгоритм

Пример 2. Теперь приведем пример алгоритма, содержащего цикл с наперед известным количеством проходов (повторений). Алгоритм решает задачу накопления суммы положительных элементов одномерного массива Z длины N (под длиной массива понимается количество его элементов). Блок-схема алгоритма дана на рис. 4.

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

На рис. 5 приведены структуры цикла и заголовка цикла.

Рис. 5. Структура цикла и заголовка цикла.

6. Алгоритмы со структурами вложенных циклов

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

Пример 1. Рассмотрим задачу сортировки одномерного массива Z длины N. Отсортировать массив – значит расположить его элементы в порядке роста или убывания.

Опишем метод сортировки массива в порядке роста. Сначала выполняется проход по массиву с целью определения в нем наименьшего элемента. Затем производится перестановка этого элемента с первым. Далее совершается второй проход по массиву, начиная со второго элемента. Найденный наименьший элемент переставляется со вторым и т. д. После (N-1)-го прохода с выполнением названных операций массив окажется отсортированным.

Блок-схема этого алгоритма сортировки показана на рис. 6.

Рис. 6. Алгоритм сортировки массива

Пример 2. Дан двумерный квадратный массив Z, состоящий из N строк и N столбцов. Необходимо найти среднее арифметическое S его отрицательных элементов и заменить положительные элементы побочной диагонали массива средним арифметическим S.

Блок-схема алгоритма показана на рис. 7.

7. Вспомогательные алгоритмы

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

Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан весь набор необходимых входных и выходных величин. Нередко один и тот же параметр может оказаться входным и выходным одновременно. Например, на вход такого

Рис. 7. Алгоритм обработки матрицы

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

Среди вспомогательных алгоритмов различают процедуры и функции. На рис. 8. приведен пример процедуры и головного алгоритма, использующего ee.

Рис. 8. Пример функции и головного алгоритма

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

Рассмотрим задачу вычисления факториала числа N! = 1. 2. 3... N. Результатом будет одно число, поэтому лучше алгоритм оформить в виде функции. Пример блок-схемы подпрограммы функции приведен на рис. 9.

Рис. 9. Подпрограмма-функция

8. Декомпозиция алгоритма

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

Метод, при помощи которого обычно выполняется декомпозиция, достаточно прост. Сначала вычленяют основные этапы предстоящей работы. Наиболее сложные этапы оформляет в процедуры или функции верхнего уровня. Затем, если необходимо, такие этапы делят на этапы более низкого уровня. Наиболее сложные из них также оформляют процедурами или функциями и т. д. Следуя методу "от сложного к простому", в конечном итоге достигают решения поставленной задачи.

Приведем пример декомпозиции для решения задачи сортировки массива.

Решение задачи декомпозиции состоит из трех основных этапов: 1) ввода данных, 2) сортировки массива и 3) вывода отсортированного массива. Первый и третий этапы вследствие их простоты не нуждаются в дальнейшей декомпозиции, поэтому выполняются в головном алгоритме. Второй этап представляет достаточно сложный и самостоятельный фрагмент вычислений, поэтому его целесообразно выделить в отдельную процедуру, которой можно дать имя Sort.

Этап сортировки, в свои очередь, состоит из двух этапов: 1) установления необходимости сортировки и (N–1) – кратного прохода по массиву и 2) нахождения наименьшего элемента во фрагменте массива и перестановки этого элемента с начальным элементом фрагмента. Поскольку последний этап многократно повторяется при выполнении первого этапа, то его можно оформить в отдельную процедуру. Этой процедуре можно дать имя Tra (от английского transposition – перестановка).

Блок-схемы головного алгоритма, процедуры Sort и процедуры Тrа показаны на рис. 10. соответственно.

Рис. 11. Декомпозиция алгоритма сортировки.

9. Пример алгоритмической декомпозиции предметной области «Школа. Отдел кадров»

9.1. Декомпозиция головного алгоритма программы

9.2. Декомпозиция подпрограммы «Подменю Администратор»

9.2.1. Алгоритм функции «Ввод пароля»

Функция «Ввод пароля» возвращает в вызывающую функцию 0 при неуспешном вводе пароля и 1 при успешном вводе.

9.2.2 Декомпозиция подпрограммы «Подменю добавление»

9.2.2.1. Декомпозиция подпрограммы «Подменю добавление штатной единицы»

9.2.2.1.1. Алгоритм функции проверки открытия файла

Аргумент функции - указатель на начало списка штатных единиц. Функция возвращает -0, если список пуст, 1 – если в списке есть элементы

9.2.2.1.2. Декомпозиция функции «Прочитать файл»

9.2.2.1.2.1. Алгоритм функции «Прочитать данные о ШЕ (F1)»

Функция читает данные из файла F1 и сохраняет их в К.

9.2.2.1.3. Алгоритм функции «Ввод данных о ШЕ»

Функция запрашивает данные о ШЕ с клавиатуры и сохраняет их в К.

9.2.2.1.4. Алгоритм функции «Добавление в массив (К,MSE)»

Функция добавляет запись К в начало динамического массива MSE. Функция возвращает адрес первого элемента массива.

9.2.2.1.5. Алгоритм функции «Запись в файл (К,F1)»

Функция записывает К в файл F1.

9.3. Декомпозиция подпрограммы «Подменю Пользователь»

Рис. 14. Декомпозиция подпрограммы «Подменю Пользователь»

9.4. Декомпозиция подпрограммы «Выход»

Рис. 15. Декомпозиция подпрограммы «Выход»

10. Определение типов входных и выходных данных.

10.1. Функция «Ввод пароля»

Входных данных нет.

Выходные данные – целое число.

10.2. Функция проверки открытия файла.

Входные данные – указатель на начало массива MSE

Выходные данные – целое число.

10.3. Функция «Прочитать данные о ШЕ (F1)»

Входные данные – указатель на файл.

Выходные данные – структура данных K, содержащая информацию о штатной единице.

10.4. Функция «Ввод данных о ШЕ»

Входных данных нет.

Выходные данные - структура данных K, содержащая информацию о штатной единице.

10.5. Функция «Добавление в массив (К,MSE)»

Входные данные – указатель на начало массива MSE, структура данных K, содержащая информацию о штатной единице.

Выходные данные - указатель на начало массива MSE.

10.6. Функция «Запись в файл (К,F1)»

Входные данные - структура данных K, содержащая информацию о штатной единице. Указатель на начало массива MSE.

Дата добавления: 2015-09-29