2. Проектирование программных модулей.

Структурное программирование

Процесс проектирования программных модулей состоит из двух этапов: проектирование внешних функций и проектирование логики.

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

1. входные данные (точное указание структуры и диапазона);

2. выходные данные (описание всех реакций системы);

3. возможные изменения состояния системы при каждом виде входных данных с точки зрения пользователя;

4. характеристики надежности ( как какой-либо отказ повлияет на систему, файлы, пользователя);

5. требования эффективности (время, память и т.д.);

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

Проектирование логики модуля (внутреннее проектирование) представляет собой следующую последовательность шагов:

1. Проверка внешних спецификаций (они должны соответствовать информации о сопряжениях и подтверждаться анализом вызывающих модулей);

2. Выбор алгоритма и структуры данных;

3. Объявление данных из сопряжения;

4. Объявление остальных данных;

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

6. Осуществление ручной проверки программы;

7. Тестирование модуля компиляцией.

Идея пошаговой детализации логики программных модулей составляет методологическую основу структурного программирования – одного из направлений в проектировании и программировании программных продуктов. Научные основы структурного программирования были заложены на рубеже 60 – 70-х годов в трудах Дейкстры и Вирта. Метод пошаговой детализации позволяет существенно упростить проектирование модулей со сложной логикой.

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

Алгоритм 3

Begin

for k := 1 to n – 1 do

begin m := номер допустимой строки;

if m<>k then строка[m]строка[k];

for i := k+1 to n do

преобразовать строку [i];

end;

End;

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

На следующем шаге детализации абстрактные функции «номер допустимой строки», «преобразовать строку», процедуру обмена строк () необходимо наполнить конкретным содержанием с расшифровкой механизма реализации каждой процедуры.

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

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

Часто структурное программирование называют программированием без goto. Это не совсем верно. Подобная легенда возникла, видимо, из-за того, что в первой работе по структурному программированию, опубликованной Дейкстрой в 1968 году, говорилось «о вреде оператора goto». Согласно изложенной в статье концепции, между текстом программы и последовательностью выполнения ее операторов должно быть простое соответствие, благодаря которому, читая текст программы, можно достаточно просто отслеживать выполняемые действия. Неограниченное использование оператора goto, особенно goto назад по тексту программы, серьезно нарушает это соответствие.

На самом деле можно привести массу примеров, когда наличие или отсутствие операторов goto не улучшает и не ухудшает программу. Можно дать следующее, более правильное определение структурного программирования, принадлежащее Майерсу [7]: это программирование, ориентированное на общение с людьми, а не с машиной. Чтобы удовлетворять этому определению, программа должна обладать следующими качествами:

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

2. Операторов goto надо избегать всюду, где возможно;

3. Текст программы должен быть написан с правильными сдвигами (лесенкой);

4. Каждый модуль должен иметь ровно один вход и один выход;

5. Текст программы должен быть физически разбит на части для облегчения чтения;

6. Программа должна представлять собой простое и ясное решение задачи.

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

Пример 2.2. Функция модуля – выдать все возможные значения целочисленных переменных _i, i=1…n, удовлетворяющих следующим условиям: , dN.

Неструктурный вариант программы:

Алгоритм 4

Begin

for i := 1 to n do _i := 0;

s := 0;

10: _n := d – s

writeln(₁, ₂,…, _n);

k := 1;

20: _k := _k + 1;

s := s + 1;

if s  d then goto 10;

s := s - _k;

_k := 0;

k := k + 1;

if k  n-1 then goto 20;

End;

В этом варианте два раза используется goto назад.

Структурированный вариант программы:

Алгоритм 5

Begin

for i := 1 to n do _i := 0;

s := 0;

repeat

if s  d then

begin

_n := d – s

writeln(₁, ₂,…, _n);

k := 1;

_k := _k + 1;

s := s + 1;

end else

begin

s := s - _k;

_k := 0;

k := k+1;

_k := _k + 1;

s := s + 1;

end;

until k > n-1;

End;

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

Контрольные вопросы и задания

1. Написать структурный вариант алгоритма генерации чисел _i (пример 2.2). За основу рекомендуется взять следующую идею. Пусть (k₁, k₂, … ,k_n-1) – некоторое сочетание (n-1) элементов из d возможных. Тогда числа _i и k_i связаны следующим соотношением:

_i = k_i –k_i-1, i=1,…,n-1; k₀=0; (1)

_n = d – k_n-1.

Алгоритм генерации сочетаний можно найти в [6].

2. Написать структурный вариант программы бинарного метода возведения целую неотрицательную степень m произвольного вещественного числа x. За основу взять следующий неструктурный алгоритм [4, т.2]:

Шаг 1. Начальная установка: N := m; Y := 1; Z := x.

Шаг 2. Установить N := [N/2] и одновременно определить, было ли старое значение N четно или нечетно. Если N было четно, перейти к шагу 5.

Шаг 3. Установить: Y :=Y * Z.

Шаг 4. Если N=0, то алгоритм закончен, ответ равен Y.

Шаг 5. Установить Z := Z * Z. Вернуться к шагу 2.

3. Доказать соотношение (1).

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

Варианты заданий

1. Дан однонаправленный список L₁. Включить в него перед вторым вхождением элемента с заданным значением E подсписок L₂.

2. Дан однонаправленный список L₁. Включить в него перед предпоследним вхождением элемента с заданным значением E подсписок L₂.

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

4. Дан однонаправленный список L₁. Определить, есть ли в нем подряд идущие элементы, составляющие список L₂.

5. Дан однонаправленный список L из элементов целого типа. Из каждой группы подряд идущих равных элементов оставить в списке только один.

6. Даны однонаправленные списки L₁ и L₂. Сформировать список L=L₁ L₂.

7. Даны однонаправленные списки L₁ и L₂. Сформировать список L=L₁ L₂.

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

9. Дан однонаправленный список L. Включить в него k новых элементов, вставляя их на заданные места в списке, одновременно удаляя другие заданные элементы. Места включаемого и удаляемого элемента не должны совпадать.

10. Дан однонаправленный список L. Пусть L_i, L_i+1 – два последовательных элемента списка. Получить все вещественные корни квадратного уравнения x²+L_ix+L_i+1=0, i=1,…,n.

11. Дан однонаправленный список L. Найти за один просмотр списка три его максимальных элемента и переместить их в начало списка в порядке убывания.

12. Дан однонаправленный список L. Если в нем три подряд идущих элемента составляют выпуклую тройку – исключить два крайних элемента всех таких троек.

13. Дан однонаправленный список L из элементов целого типа. Считая, что два первых его элемента L₁ и L₂ соответствуют 1-му и 2-му членам арифметической прогрессии, оставить в списке только члены этой прогрессии.

14. В однонаправленном списке L содержится n элементов (n≤12,тип элемента integer), среди которых могут быть совпадающие. Определить, сколько в списке пар одинаковых элементов, сколько троек, четверок, …, n-ок. Если в списке есть k совпадающих элементов, то при подсчете (k-1)-ок, (k-2)-ок и т.д. эти элементы не учитывать. Указание: воспользоваться алгоритмом генерации сочетаний [6] .