Курс лекций (стр. 12 из 24)

Рассмотрим в качестве небольшого примера алгоритм вычисления суммы квадратов первых N (N >= 1) натуральных чисел.

(N должно быть задано перед выполнением алгоритма - программы)

Решение задачи - последовательность простых шагов (рис.7).

Задать количество слагаемых N.

Присвоить S значение 0 и i значение 1.

Далее выполнять операцию S = S + i², увеличивая значение i на 1 после очередного выпонения этой операции.

Чтобы обеспечить сложение точно N членов, после каждого изменения i необходимо проверять условие i <= N.

Если условие удовлетворяется, т.е. не все N сложений выполнены, то необходимо повторить действия, начиная с операции (блока), помеченной 4.

Распространен и другой способ описания логики программы до начала ее программирования кроме использования блок-схем. Альтернативный вариант - это применение псевдокода (или языка проектирования программ PDL – Process Design Language). Он занимает промежуточное положение между естественным языком и языком программирования. Он состоит из внешнего синтаксиса и внутреннего синтаксиса.

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

Следование. Записываются последовательно операции одна под другой. Для отделения части последовательности операторов используются операторы – do{do-часть}-(end-do) (выполнить);

Индексная последовательность (цикл по счетчику). Цикл с заранее определенным числом шагов (среднее между обычными последовательностью и циклом) – for{индексный список}-do{do-часть}-(end-do) (для-выполнить);

Цикл-До – do{do-часть}-until{until-тест}-(end-do). Операции структуры, включая модификацию until-теста, выполняются один или более раз до тех пор, пока until-тест не примет значение истина;

Цикл-Пока – while{while-тест}-do{do-часть}-(еnd-do) Do-часть выполняется пока while-тест имеет значение истина. Естественно do-часть модифицирует условие while-теста для того, чтобы окончить вычисления.

Разветвление – if{if-тест}-then{then-часть}-else{else-часть}[els]-(end-if) (если-то-иначе);

Множественный выбор – case{case-тест}-part{список1,case-часть1}-part{список2,case-часть2}-…-part{списокn,case-частьn}-else{else-часть}-(end-do) (выбор);

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

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

Рассмотренный ранее пример, представленный на языке PDL, изображен на рис.9.

5. Методы разработки программного обеспечения

Рассматриваются общие методы (не зависят от используемого языка).

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

Итак, вначале программист представляет задачу как набор задач (рис.10 – в виде блок-схемы и языка PDL). Затем каждая из задач детализируется, например, в виде нескольких предложений языка PDL. Если она относительно сложная, то можно представить в виде отдельной процедуры.

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

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

Введем понятие простой программы (именно для такой программы может быть доказана теорема о возможности ее преобразования в последовательность основных управляющих структур – следования, повторения и разветвления), для которой

1. Существует единственный вход и единственный выход;

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

Примеры простых программ и непростых приведены на рис.11.

Используя указанное определение, нисходящую разработку можно представить в виде следующего алгоритма:

while

проектирование не окончится

do

заменить некоторый узел простой программой

end-do

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

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

Функция F является рекурсивной, если

1. F(N) = G(N,F(N-1)), где G – известная функция

2. F(1) = некоторому известному числу.

Типичным примером можем являться вычисление факториала. Например, Factorial(450) можно получить умножением 450 на Factorial(449). В результате задача сводится к вычислению Factorial(449). Если это преобразование повторить 448 раз, то получим Factorial(2), который есть 2*Factorial(1). Поскольку Factorial(1) известен и равен 1, то задача решена.

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

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

СТРУКТУРЫ ДАННЫХ

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

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

Простейший агрегативный тип – массивы, которые есть упорядоченный набор данных одного типа.

Структуры (в Паскале – записи) – поименованная совокупность данных различных типов.

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

Полезно рассмотреть и другие возможные агрегативные структуры (могут быть организованы с помощью массивов).

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

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

Стеки – упорядоченный список, в один конец которого элементы добавляются, и из него же изымаются. Список LIFO (Last In, First Out). Операции – поместить, извлечь, функция «пусто» = истина, если стек не заполнен.

Множество – совокупность переменных одного типа. Аналогичен списку, за исключением того, что порядок расположения переменных не имеет значения. Операции – добавить, удалить, функция «входит в» = истина, если данная переменная находится в множестве.