Уровень 0

Пример нисходящей разработки

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

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

Уровень 0

1. Задача top_down. Абстракция А0

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

Примеры возможных значений данных. Далее на основе этих примеров будут построены функциональные тесты.

1) b=(1,2,3,1) - есть два одинаковых элемента;

-1 0 2 -3 меняем -1 0 2 -3

а= 2 -1 0 2 матрицу: а= 2 -1 0 2

1 1 3 2 1 2 3 1

2) b=(1,2,3,4) - нет двух одинаковых элементов

-1 0 2 -3 -3

а= 2 -1 0 2 -1 1

1 1 3 2 1

минимальные максимальный

элементы из них

строк

2. Входные данные. Ограничения на диапазоны данных там, где они не очевидны, взяты произвольно.

цел n - число элементов массива b; оно же - число столбцов матрицы а;

простая переменная; 0<n<=50; XX;

цел b - исходный одномерный массив; ¦b(i)¦<=10; +XX;

цел m - число строк матрицы a;простая переменная;¦m¦<=50;XX;

цел a - исходная матрица; двумерный массив; ¦a(i,j)¦<=10; +XX.

Типы элементов a и b в общем случае должны совпадать, так как

Входная форма:

3. Выходные данные

цел a - измененная матрица; |a(i,j)|<=10;+XX

или

цел maxmin - максимальное значение

минимальных элементов строк; простая переменная;

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

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

4. Аномалии входных данных

1) Аномалии n: n<=0 или n>50;

реакция-1: n задано неверно обр 4.1

2) Аномалии элементов массива b: хотя бы для одного элемента

|b(i)| >10;

реакция-2: <диагностика ошибок> обр 4.2

3) Аномалии m: m<=0 или m>50;

реакция-3: m задано неверно обр 4.3

4) Аномалии элементов массива а: хотя бы для одного элемента

|a(i,j)| >10;

реакция-4: <диагностика ошибок> обр 4.4

Обсуждение двух взаимосвязанных моментов - способа анализа

данных и формы диагностики ошибок - отложим до момента решения

подзадачи анализа данных.

5. Функциональные тесты

6. Метод

Если хотя бы одно значение хотя бы одного данного ошибочно, будем считать входные данные неверными.

Будем решать задачу, только если все входные данные верны.

Отделим ввод, анализ и вывод входных данных от обработки (решения задачи).

Ввод, анализ, вывод

Принципы:

- ориентируемся на однократный ввод данных;

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

- выводим все, что можно вывести, и как можно раньше, чтобы локализовать ошибки (выявить их место).

Тогда:

- при верном n следует ввести и проанализировать массив b (при неверном - вводить ничего нельзя);

- при верных n и m следует ввести и проанализировать массив a (при неверном m этот массив вводить нельзя).

Будем выводить данные сразу после ввода; если они неверны, сразу же выведем и соответствующие реакции на аномалии.

Для фиксации верности или ошибочности данных используем логические переменные:

истина, если n верно,

лог nver =

ложь, в противном случае;

истина, если m верно,

лог mver =

ложь, в противном случае;

истина, если все элементы массива b верны,

лог bver=

ложь, в противном случае (есть i такое, что b(i) неверно);

истина, если все элементы массива a верны,

лог aver =

ложь, в противном случае (есть i,j такие, что

a(i,j) неверно)

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

Подзадачи проверки массивов с печатью сообщений об ошибках оставим в виде абстракций.

Обработка

Оставим в виде абстракции, так как проверка данных уже достаточно сложна.

Алгоритм (в рамках слева проставлены номера структурных тестов для отдельных конструкций; об этом см. ниже)

алг top_down(n,b,m,a,amax);

арг цел n,m; цел масс b(n),a(n,m);

рез цел maxmin; цел масс a(m,n);

нач лог nver,mver,bver,aver;{результаты анализа данных}

цел i,j; {текущие индексы}

вывод по обр1;

{ввод, анализ, вывод входных данных}

{-------------------------------------}

{проверка n}

ввод(n); вывод (n)по обр2.1;

nver:=истина;

если (n<=0 или n>=50) то {n неверно}

2.1,2.2, nver:=ложь; вывод по обр4.1;

кесли;

{-------------------------------------}

если nver {n верно} то

ввод(b(i),i=1,n); вывод(b(i),i=1,n)по обр2.2;

{------------------------------------}

1.1,1.2, {проверка массива b}

3.1, {вх.:n,b; вых.:bver}

4.1,4.2, provb(n,b,bver);

5.1 А0.1 проверка масс.b

5.2 с выводом диагностики ошибок bver:=provb(n,b);

{------------------------------------}

кесли;

если (nver & bver){предыдущие данные верны} то

ввод(m); вывод(m)по обр2.3;

{------------------------------------}

{проверка m}

1.1,1.2, mver:=истина;

4.1,4.2, если (m<=0 или m>50) то {m неверно}

5.1

4.1,4.2 mver:=ложь; вывод по обр4.3;

кесли;

{------------------------------------}

кесли;

если (nver & bver & mver){предыдущие данные верны} то

ввод((a(i,j),j=1,n),i=1,m);

вывод((a(i,j),j=1,n),i=1,m)по обр2.4;

{---------------------------------------}

1.1,1.2, {проверка массива а}

5.1 {вх.:m,n,a; вых.: aver}

проверка массива а

A0.2 с выводом диагностики ошибок

{---------------------------------------}

кесли;

{обработка}

если (nver & mver & bver & aver) {все данные верны} то

{решение задачи}

{вх: n,b,m,a; вых.: a или maxmin}

1.1,1.2

A0.3 решение задачи с выводом результатов по обр3

иначе {хотя бы одно данное неверно}

2.1,2.2,

3.1, вывод по обр.4.5; 4.1,4.2, 5.1

кесли;

кон;

кон top_down;

Структурные тесты

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

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

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

Поэтому нами выбран следующий вариант:

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

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

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

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

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

1. Условие задачи

2. Входные данные

3. Выходные данные

4. Аномалии

5. Функциональные тесты

Поиск по сайту: