Файл: Алгоритмизация как основной этап разработки программ (подробно).pdf

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

Алгоритмы для проектирования задачи

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

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

---

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

После того, как задача была четко сформулирована и проанализирована, а данные уточнены, решение может быть разработано [8.]. Оно включает в себя проектирование ввода, вывода, внутренних данных, разработку алгоритма и разработку тестовых данных для алгоритма. Например, компьютер должен знать, состоят ли значения данных из целых или действительных чисел и находятся ли они в принятом десятичном или экспоненциальном формате. Он должен знать, сколько значений данных ожидается и как определить конец списка значений данных. Если алгоритм включает в себя повторные вычисления, предполагаемые предварительные условия и постусловия должны быть распознаны. На этапе проектирования алгоритм может быть представлен структурными схемами, псевдокодом и/или блок-схемами или другими методами логического представления [10.].

Ниже рассматривается простая задача расчета и печати средней глубины воды в озере с помощью набора измерений глубины. Основные этапы расчета:

1. Введите, проверьте и добавьте значения данных по одному, считая количество значений данных;
2. Разделите сумму значений данных на количество значений данных;
3. Напечатайте среднюю глубину.

Первый из этих шагов включает в себя повторный ввод, проверку и добавление. Инструкции программы должны включать информацию о переменных, которые должны быть добавлены и увеличены в цикле, и то, как определить конец данных. Инструкция для вычисления среднего значения и его вывода следует за циклом. Шаг 1 будет работать только в том случае, если есть внутренняя переменная, которая будет использоваться для накопления суммы значений данных, и внутренняя переменная, которая будет использоваться в качестве счетчика. Обе из них должны быть очищены перед обработкой любых данных. Предварительным условием для шага 1 является то, что total = 0 и count = 0, где total и count являются именами для внутренних переменных. Предварительным условием для шага 2 является count > 0. Поэтому должно быть хотя бы одно положительное значение данных. Простейшее описание этого алгоритма в виде псевдокода выглядит следующим образом:

---

1. инициализировать total и count;
2. обработать положительные значения данных в наборе значений данных;
3. рассчитать среднее значение;
4. вывести среднее значение на экран.

Этот алгоритм может быть записан в виде блок-схемы (приведена на рисунке 1).

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

Рисунок 1 – Блок-схема алгоритма вычисления средней глубины

1. Инициализировать total и count нулем (это необходимо для выполнения первого предварительного условия);
2. Для каждого значения входных данных больше 0 (предварительное условие: предположим, что total ≥ 0, count ≥ 0 при каждом получении нового значения данных) выполнить:
   1. Добавить значение данных к total;
   2. Добавить 1 к count;
3. Конец цикла;
4. Разделить total на count, чтобы получить среднюю глубину (предварительное условие; предположим, что count > 0);
5. Распечатать среднюю глубину;
6. Конец.

Этот алгоритм также может быть записан в виде блок-схемы (приведена на рисунке 2).

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

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

1. total ← 0.0;
2. count ← 0;
3. Для каждого найденного значения входных данных выполнить:
   1. Если значение > 0 (предварительное условие: значение найдено);
      1. total ← total + значение данных;
      2. count ← count + 1;
   2. Конец если;
4. Конец для;
5. average ← total / count (предварительное условие: найдено положительное значение);
6. Печать average;
7. Конец.

---

Рисунок 2 – Блок-схема алгоритма вычисления средней глубины с циклом

Следует обратить внимание на то, что было сделано несколько допущений: что существует по крайней мере одно положительное измерение, что измерение является действительным числом, а не целым числом (итоговое значение инициализируется как 0,0, а не 0), и что значение 0 не считается.

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

Основные правила для написания псевдокода:

1. Переменные для сумм и количества должны быть обнулены; другие переменные, которые требуют начальных значений, также должны быть инициализированы.
2. Присвоение значений показано стрелкой, указывающей влево.
3. Указывается начало и конец любого выбранного расчета, а также основание для его включения или исключения.
4. Указывается начало и конец любого повторения, а также основание для продолжения и / или остановки повторения.
5. Условные шаги и шаги повторения имеют отступ.
6. Для арифметики могут использоваться слова или арифметические операции.
7. Завершение алгоритма должно быть четко обозначено.

Понятие структурного программирования

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

1. Последовательная структура

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

1. Структура выбора

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

---

1. Структура с повторением или циклом

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

Разработка и выполнение программы

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

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

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

---