Файл: Алгоритмизация как обязательный этап разработки программы.pdf

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

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

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

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

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

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

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

Процедура сортировки требует перестановки значений двух простых переменных. Вспомогательный алгоритм, реализующий эту процедуру, показан на рис. 2. Алгоритм имеет имя Swap и два формальных параметра - переменные a, b. Тело алгоритма состоит из одного блока, где выполняется три оператора присваивания. Сначала оператором c := a значение ячейки a копируется во вспомогательную переменную c, затем оператором a := b из ячейки с адресом b производится копирование значения в ячейку с адресом a, последним оператором b := c из вспомогательной ячейки с адресом c значение копируется в переменную с адресом b. В результате такого кругового копирования содержимое ячеек a и b поменяется местами.

Swap(a, b)

c = a; a = b; b =c

Конец

1

2

3

1. Процедура Swap

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

Основной алгоритм сортировки массива приведен на рис. 3. Алгоритм имеет имя Bubble и содержит два формальных параметра: N - длина массива, Z - имя массива, который нужно отсортировать.

Сортировка производится при помощи двух вложенных друг в друга циклов. Внешний цикл образован блоками 2 - 7 и предназначен для многократного прохода по массиву. Внутренний цикл содержит блоки 3 - 6. Этот цикл нужен для однократного прохода по всем парам соседних элементов массива с целю перестановки несортированных пар элементов. Переменная L играет роль параметра, по которому можно определить производились ли перестановки при выполнении внутреннего цикла.

1

Bubble(N, Z)

L = 0

Конец

2

3

i = 1, N - 1

4

Z_i+1 > Z_i

Perm(Z_i+1, Z_i)

5

L = L + 1

6

да

нет

L = 0

да

нет

7

8

1. Процедура Bubble

Алгоритм работает следующим образом. Сначала в блоке 2 параметр L получает значение 0 (ноль). Далее выполняется внутренний цикл из блоков 3 - 6. В нем счетчик цикла i будет последовательно принимать значения 1, 2, 3, ..., N-1. При каждом таком значении счетчика в блоке 4 производится сравнение соседних элементов с номерами i и i + 1. В том случае, если пара не отсортирована, то в блоке 5, используя вспомогательный алгоритм Swap, эта пара будет отсортирована путем перестановки значений этих элементов. После каждой перестановки счетчик перестановок L будет увеличиваться на 1. После прохода по всем парам элементов по завершении внутреннего цикла выполнится проверка количества совершенных перестановок. Если перестановок не было (т.е. L = 0), то это означает, что массив отсортирован и работа процедуры сортировки завершена. Если же L отлично от 0, то управление предается на блок 2 и процесс сортировки продолжится по той же схеме. Внешний цикл будет выполняться до тех пор, пока при выполнении по внутреннего цикла не будет выполнено ни одной перестановки.

На рис. 4 показан главный управляющий алгоритм, который и решает поставленную задачу. Сначала в блоке 2 задается количество N элементов массива и вводятся значения всех N элементов массива A. Затем в блоке 3 происходит вызов алгоритма сортировки Bubble. В нем на место формального параметра N подставляется фактическое значение параметра N головного алгоритма, а на место формального массива Z подставляется фактический массив A. Теперь управление передается в алгоритм Bubble, который выполнит сортировку массива A. После сортировки в блоке 4 головного алгоритма отсортированный массив будет выведен. В блоке 5 алгоритм закончит свою работу.

Начало

N, A

Конец

1

2

5

Bubble(A, N)

3

A

4

1. Головной алгоритм

Реализация алгоритмов

После разработки алгоритма встает задача его реализации в виде программы, которую можно выполнить на вычислительной машине (компьютере). В ГОСТ 19781-90 дано следующее определение программы.

Программа - это данные, предназначенные для управления конкретными компонентами обработки информации в целях реализации определенного алгоритма.[1]

Для написания программы необходимо в первую очередь выбрать язык программирования (алгоритмический язык). В общем случае алгоритмический язык - это набор символов с заданными правилами образования из этих символов конструкций, с помощью которых описывается процесс выполнения алгоритма. В ГОСТ 19781-90 дано следующее определение алгоритмического языка.[1]

Алгоритмический язык - искусственный язык, предназначенный для выражения алгоритмов.

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

Выбор языка определяется:

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

Например, для программирования сложных (чаще всего системных) задач выбирают язык Ассемблер или С++, а для решения инженерных задач предпочтение отдают Pascal (Object Pascal), Fortran, C# или Basic.

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

Этапы подготовки исполняемой программы.

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

2. Компоновка (редактор связей) - сборка объектного модуля программы, модулей ввода-вывода и компонентов стандартной библиотеки объектных модулей в один модуль, который называется выполняемым файлом или загрузочным модулем.

3. Выполнение файла исполняемого модуля. На этом этапе получаем решение поставленной задачи. При этом возможно прерывание решения (аварийный останов), зацикливание или неправильные результаты. Это возможно по следующим причинам.

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

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

Схема этапов подготовки программы представлена на рис. 5.

Тестирование алгоритма

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

В общем случае отсутствуют универсальные правила выполнения тестирования.

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

Исходный модуль

Объектный модуль

Исполняемая программа

Библиотека объектных модулей

Транслятор

Компоновщик

Этап 1

Этап 2

Этап 3

1. Этапы подготовки программы

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

Величины в алгоритмах

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

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

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

Типы данных: вещественные, целые, логические, текстовые, символьные и другие.

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

Константа - это величина, значение которой не изменяется в процессе выполнения алгоритма.

Переменная - это величина, значение которой может изменяться в процессе выполнения алгоритма.

Используются простые и индексные переменные. Переменная с индексом - это элемент некоторой последовательности значений, которая называется массивом.

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

Массив - совокупность однотипных данных, связанных общим именем.

Массив может быть одномерным, количество индексов - один; двумерным, количество индексов - два и т.д. Количество индексов определяет размерность массива.

Первый компонент одномерного массива - это элемент с номером 1, второй - с номером 2 и т.д., запись в математике - X₁, X₂,... При программировании запись более формализована: X(1), X(2),... (в некоторых языках программирования допускается использование нулевых и отрицательных индексов).

Двумерный массив - это матрица из строк и столбцов. Первый индекс определяет номер строки, второй - номер столбца. Номер строки изменяется от 1 до N, где N - полное число строк, номер столбца от 1 до М, где М - полное число столбцов. При программировании элементы двумерного массива по имени Y будут записаны Y(1,1), Y(1,2), Y(1,3) и т.д. Индексы отделяются запятыми.

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

Основными характеристиками массива являются:

- имя массива;

- тип элементов;