-
Построение мат. модели. В первом приближении большинство задач, встречающихся на практике, не имеют четкого и однозначного описания. По возможности задачу необходимо формализовать. Так как в этом случае мы можем узнать, существуют ли методы и алгоритмы решения нашей задачи. Возможно, поставленная задача не имеет решения в рамках математических законов (не решена соответствующая математическая задача). Практически любую область математики или других наук можно привлечь к построению модели определенного круга задач. Для числовых задач можно построить модели на основе систем линейных уравнений (например, для расчета электрических цепей или напряжений в закрепленных балках). Дифференциальные уравнения могут быть полезны при решении задач прогноза роста популяций или расчета скорости протекания химических реакций. Для задач с символьными или текстовыми данными (написание компиляторов, распознавание слов) применяется теория формальных грамматик.
-
Написание алгоритма. Когда построена подходящая модель исходной задачи, ищется алгоритм ее решения. В начальных версиях алгоритма часто применяются обобщенные операторы (например, выбрать произвольную незакрашенную вершину), которые затем переопределяются в виде более мелких, четко определенных инструкций. Этот процесс называется пошаговой кристаллизацией алгоритма. Таким образом, весь алгоритм записывается в виде конечной последовательности инструкций. Каждая такая инструкция имеет четкий смысл и может быть выполнена с конечными вычислительными затратами за конечное время. Примером такой инструкции может служить целочисленный оператор присваивания x=y+z. Инструкции могут выполняться в алгоритме любое число раз, при этом они сами определяют число повторений. Однако, требуется, чтобы при любых входных данных алгоритм завершался после выполнения конечного числа инструкций. Таким образом, программа, написанная на основе разработанного алгоритма, при любых начальных данных никогда не приведет к бесконечным циклическим вычислениям.
-
Написание программы.
Резюме.
Схематически
процесс программирования выглядит
так:
На первом этапе создается модель исходной задачи, для чего привлекаются соответствующие математические модели. На этом этапе для нахождения решения также строится неформальный алгоритм.
На следующем этапе алгоритм записывается на псевдоязыке – смеси конструкций языка Си и менее формальных и обобщенных операторов на простом «человеческом» языке. Продолжением этого этапа является замена неформальных операторов последовательностью более детальных и формальных операторов. С этой точки зрения программа на псевдоязыке должна быть достаточно подробной, так как на этом этапе определяются различные типы данных, над которыми выполняются операторы. Затем на основе выбранных типов данных создаются абстрактные типы данных и пишутся процедуры для выполнения операций над этими типами.
Третий этап процесса программирования обеспечивает реализацию каждого абстрактного типа данных в виде структуры данных или класса. На этом этапе заменяются все неформальные операторы псевдоязыка на код языка Си. Результатом этого этапа должна быть выполняемая программа. После ее отладки получается работающая программа.
Типы данных, структуры данных и абстрактные типы данных
Хотя термины тип данных, структура данных и абстрактный тип данных звучат похоже, но имеют они различный смысл. В языках программирования тип данных (или просто тип) переменной обозначает множество значений, которые может принимать эта переменная. Набор базовых типов данных отличается в различных языках: в языке Си это типы целых (int) и действительных (float, double) чисел, символьный (char) тип. Правила конструирования составных типов данных на основе базовых типов также различаются в разных языках программирования.
Enum – перечислимый, union – объединение.
Enum light_type = {red, amber, green};
Абстрактный тип данных – это математическая модель плюс различные операторы, определенные в рамках этой модели. Например, эллипс, многоугольник.
Мы можем разрабатывать алгоритм в терминах АТД, но для реализации алгоритма в конкретном языке программирования необходимо найти способ представления АТД в терминах типов данных и операторов, поддерживаемых данным языком программирования.
Для представления АТД используются структуры данных, которые представляют собой набор переменных, возможно, различных типов, объединенных определенным образом.
В языке Си существует несколько способов реализации АТД – это структура (struct {…}), класс (class) и объединение union.
Строительным блоком структуры данных является ячейка (переменная). Она предназначена для хранения значения определенного базового или составного типа данных. Структуры данных создаются путем задания имен совокупностям ячеек. Некоторые ячейки могут содержать в себе указатели на другие ячейки.
Самый простой механизм создания совокупностей ячеек – массивы. Массивы это последовательность ячеек определенного типа. Массив также можно рассматривать как отображение множества индексов (целые числа 1, 2, … , n) в множество ячеек. Ссылка на ячейку массива состоит из имени массива и значения из множества индексов данного массива.
В отличие от Паскаля, Си позволяет использовать в качестве индексов только множества последовательных целых чисел.
Другим общим для различных языков программирования механизмом создания совокупности ячеек является структура записи. Запись можно рассматривать как ячейку, состоящую из нескольких других ячеек, называемых полями. Причем эти ячейки могут содержать данные различных типов. Записи также могут быть объединены в массивы.
struct { /* Сведения о студенте */
char name[25]; /* Фамилия И.О. */
int age; /* Возраст */
char sex; /* Пол */
} student[30] ;
Третий метод объединения ячеек, который существует в различных языках программирования – файл. Файл является последовательностью значений в общем случае различных типов. Причем эти значения могут быть записаны в файл в произвольном порядке. Поэтому файл не может иметь индексов, а элементы в файле доступны только в том порядке в котором они были записаны в файл. В отличие от файла, массивы и записи являются структурами с «произвольным доступом», под этим подразумевается, что время доступа к элементам массива или записи не зависит от значения индекса массива. Достоинство файла в том, что он не имеет ограничения на количество составляющих его элементов и это количество может изменяться во время выполнения программы.