3.2 «Историческое» проектирование

Естественный подход к проектированию

Первое, что приходит в голову – записывать последовательность действий в проектируемом алгоритме в том порядке, в котором они будут выполняться в программе. Для этого удобнее всего использовать графическое представление алгоритма – блок-схему. Блок-схема базируется на трех элементарных конструкциях:

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

проверка условия изображается ромбом, в котором записано условие, и который имеет один вход и два выхода в зависимости от результата (0 – ложь, 1 –истина):

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

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

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

команды обработки данных;
проверки условий;
безусловного и условных переходов.

Поэтому программный код во внутреннем представлении (и на языке Ассемблера) ближе к языку блок-схем, нежели к структурированным конструкциям языков высокого уровня. Между прочим, одна из основных функций фазы генерации кода в трансляторе заключается в распределении линейно адресуемой памяти для структурированных операторов типа if-then-else или do-while.

«Историческому» принципу проектирования также наиболее соответствует блок-схема алгоритма. К этому есть несколько причин:

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

smile История в картинках. 1978 год. Появление тонких ростков структурного программирования в буйных зарослях Ассемблера и Фортрана. Я взялся за свой первый серьезный программный проект – транслятор. Как учили. Взял в общежитии у старшекурсников рулон миллиметровки, расстелил его на столе и стал рисовать блок-схему транслятора. Когда полез на вторую половину стола, начал путаться, куда же вести очередную стрелку. Когда дошел до второго метра блок-схемы, запутался окончательно.

Простой пример. Поиск простых чисел

Обсуждение идеи. Простое число – число, которое делится только на 1 и на само себя. Легко заметить, что это определение «от противного» - оно не делится на числа в диапазоне от 2 до самого себя (до n-1 или до n/2). Если вспомнить, что среди этих чисел есть тоже простые и составные, то достаточно проверить, делится ли это число на уже накопленные простые числа (алгоритм «решето Эратосфена»).

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

массив накапливаемых простых чисел размерности N – A[N];
диапазон проверяемых значений v;
текущее проверяемое число n;
индекс (номер) текущего проверяемого элемент массива j;
количество накопленных простых чисел в A[] – k;

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

Установка начальных значений – k=0, n=2 соответствует состоянию «массив пуст» и проверка начинается с 2. Это может вызвать некоторое замешательство– как следует проверять пустой массив? Заметим, что проблема первого шага при «историческом» подходе возникает практически всегда, он обычно отличается от последующих, и на нем поведение программы нехарактерно. Изменить ситуацию в данном случае можно, записав в массив первое простое число: k=1; n=3; A[0]=2;
Просмотр массива начинаем с j=0.
Проверяем делимость числа n на очередной элемент массива A[j]. При проверке условия возникают два возможных направления продолжения алгоритма: каждое из них рассматривается независимо. Выберем сначала более простое.

Замечание: после этого шага становится ясно, что первый вариант начальных значений (k=0, n=2) приведет в такой блок-схеме к ошибке, поскольку проверка делимости при пустом массиве вообще не должна выполняться.

Если число делится на уже имеющееся простое, то происходит переход к следующему (n++), если интервал просмотра закончился, алгоритм завершается. В противном случае необходимо вернуться на начало проверки очередного числа (возникновение цикла).
Если число не делится на имеющееся простое, переходим к следующему (j++).
Если в массиве есть еще не проверенные числа (j<k), то возвращается к проверке делимости на очередное простое число (возникновение цикла).

Реализация на языке программирования. Для перевода блок-схемы в программный код прежде всего следует учитывать структурированный характер конструкций языков программирования (дань структурному программированию): они являются вложенными друг в друга и операторы перехода включаются туда в порядке исключения. На блок-схеме явно видны два цикла:

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

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

по обнаружении делимости (число – не простое) внутренний цикл должен завершиться «без последствий» - продолжением внешнего цикла;
по завершении просмотра массива без обнаружения делимости – необходимо добавить вновь обнаруженное простое число в массив.

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

//-------------------------------------------------------------------------------------------------------32-01

#define N 100

void main(){

int A[N],n,k,j,v;

printf("v="); scanf("%d",&v);

k=1; A[0]=2;

for (n=3; n<v && k < N; n++){                              // Внешний цикл перебора n     

j=0;

while (n%A[j]!=0){                                   // Внутренний цикл перебора A[]

                        j++;                                          // A[] закончился -

if (j==k) {A[k++]=n; break; }        // добавить очередной в A[]

            }}                                                          // Альтернативный выход по break

for (j=0;j<k;j++) printf("%d ",A[j]);

}

Если же в заголовок внутреннего цикла внести ограничение по завершению просмотра массива (j==k), то добавление нового простого числа A[k++]=n придется делать вне этого цикла (т.е.после). Тогда можно сделать цикл с завершением по любому из двух условий и повторной проверкой условия добавления после выхода.

//-------------------------------------------------------------------------------------------------------32-02

#define N 100

void main(){

int A[N],n,k,j,v;

printf("v="); scanf("%d",&v);

for (k=0,n=3; n<v && k < N; n++){                       // Внешний цикл перебора n     

for (j=0; j<k &&  n%A[j]!=0; j++);             // Внутренний цикл перебора A[] (без тела)

if (j==k) A[k++]=n;                                 // добавить очередной в A[]

            }}                                                          // при выходе по второму условию

for (j=0;j<k;j++) printf("%d ",A[j]);

}

Несмотря на формальные, казалось бы, преобразования, новый вариант несколько отличается: он работоспособен при пустом массиве (проверке, начиная с 2), поскольку условие проверки размерности записано первым, а проверки свойства делимости - вторым. Как видим, при записи алгоритма на языке программирования имеют место некоторые преобразования структуры алгоритма, которые, однако, не должны менять логику программы.

«Историческое» программирование с разных сторон

«Детская болезнь исторического программизма». Коль скоро программа представляет собой последовательность выполняемых действий, то начинающий программист обычно так и поступает: начинает записывать ход своих рассуждений, переводя его на язык логических конструкций языка программирования. Соответственно, получается так называемый «исторический» подход. Как правило, на третьей или четвертой конструкции человек начинает терять нить рассуждений и останавливается. Такой принцип изложения характерен для художественной литературы, да и то не всегда. По той причине, что литературный текст является последовательным, хотя и допускает вложенность («лирические отступления») и даже параллелизм сюжетных линий. С программой сложнее: ее логика включает не только последовательность действий, но и вложенность одних конструкций в другие. Поэтому начало некоторой конструкции может отстоять от ее конца на значительном расстоянии, но обдумываться она должна как единое целое. Тем не менее, эта технология программирования существует и даже имеет свое название: «метод северо-западного угла». Имеется в виду экран монитора или лист бумаги.

Есть несколько признаков, по которым можно отличить «исторического» программиста:

никогда сразу не закрывает синтаксическую конструкцию (оператор), пока не напишет содержимое вложенных в нее конструкций до конца. "Структурный" программист сначала пишет конструкцию, например, пару скобок «{ }», а потом начинает обдумывать и записывать ее содержимое;
начинает обсуждение цикла с первого шага. «Структурный» программист сначала определяет условия протекания циклического процесса, а замет работает с произвольным его шагом.

Самый простой тест. Приводимый ниже пример использовался сначала для определения «нулевого» уровня знаний в разделе «Работа со строками». Оказалось, что его можно с равным успехом использовать для проверки, насколько «исторический» принцип превалирует над логическим. Итак, задана строка в массиве символов. Требуется дописать в конец символ «». Некоторый процент начинающих рассуждает примерно так: необходимо найти конец строки, для чего надо написать цикл движения по строке. Далее: если встречается символ конца строки (символ с кодом 0), то необходимо заменит его на символ "", а вслед за ним записать код конца строки. В результате получается примерно следующее.

char c[80]=”aaaaaaaaaa”;

for (i=0; c[i]!=0; i++)
  if (c[i]!=0) { c[i]=’*’; c[i+1]=0; }

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

for (i=0; i<80; i++)
  if (c[i]!=0) { c[i]=’*’; c[i+1]=0;  break; }

В таком виде программа работоспособна. Но на самом деле, есть более естественный вариант, который продполагает последовательное выполнение двух действий: поиск конца строки и замена его на символ "*".

for (i=0; c[i]!=0; i++);

c[i]=’*’; c[i+1]=0;

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

Шиворот – навыворот. «Исторический» подход в проектировании программы по своей природе выделяет фрагменты программы, лежащие "ближе к земле", то есть самого внутреннего уровня вложенности. При этом внешних, наиболее «абстрактных» конструкций программист не замечает. К пониманию того, что они должны быть, он приходит уже позднее, и в дело вступают различные "заплатки" в виде операторов goto для возвращения на уже пройденные участки программы, как замаскированное проявление незамеченных вовремя циклов. В качестве примера достаточно будет посмотреть на любую сортировку (например, выбором или вставками). Начав с проектирования процесса выбора или вставки (причем, конкретно для первого шага), программист оказывается перед фактом, что уже написанная часто программы должна повторяться. Благо, ему достанет ума включить уже написанную часть в тело цикла и несколько подкорректировать границы параметры-границы протекания процессов. Сохраняющий приверженность "историческому" принципу напишет goto, сопровождая его манипуляциями индексами. Пример: сортировка выбором: выбирается минимальный из неотсортированной части и переставляется с первым из наотсортированной. В результате неотсортированная часть сокращается слева на один элемент.

Итак, «историк» напишет поиск минимального во всем массиве и обмен с первым. Это не составит труда, если он помнит контекст поиска индекса минимального и правило «трех стаканов».

void sort(int A[], int n) {

  for (int i=1,k=0; i<n; i++)
    if (A[i]<A[k]) k=i;

  int c=A[0]; A[0]=A[k]; A[k]=A[0];

  ...

После чего возникнет необходимость «отказаться» от 0-го элемента. Он будет заменен на j-ый, а в программу будет добавлен goto для повтора уже написанного фрагмента.

void sort(int A[], int n){

int j=0;

retry:

for (int i=j+1,k=j; i<n; i++)

            if (A[i]<A[k]) k=i;

int c=A[j]; A[j]=A[k]; A[k]=A[0];

j++; if (j!=n) goto retry;

}

Хорошо еще, если сразу станет понятно, что переменная j соответствует длине упорядоченной части массива и все "нули" в написанном фрагменте нужно заменить на j.

Два в одном – шампунь и бальзам-ополаскиватель. В некоторых достаточно простых случаях удается решить задачу с помощью "исторического" подхода, когда программа заканчивается раньше, чем программист теряет логическую нить рассуждений. Но при этом довольно часто несколько независимых управляющих конструкций алгоритма оказываются "слитыми" в одну. Конечно, это делает программу более компактной, но не более воспринимаемой и управляемой. Простой пример: поиск подстроки в строке. Исторический подход. Берем по очереди i-ый символ строки и проводит в цикле попарное сравнение его с k-ым символом второй строки. Если они совпадают, то переходим к следующей паре (k++ в самом теле цикла и i++ в заголовке). Если не совпадают, то возвращается на начало второй строки и к следующему символу первой (от начала совпадающего фрагмента). Успешное завершение поиска - достижение конца второй строки.

int find(char c1[], char c2[]){

for (int k=0,i=0; c1[i]!=0; i++){

            if (c2[k]==0) return i;

                        if (c1[i]==c2[k]) k++;

                        else      { i-=k; k=0; }

}

return -1; }

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

int find(char c[]){

for (int i=0; c[i]!=0; i++)

            {

            // 1. Попарное сравнение символов c2 - от начала и c1 - от i.

            // 2. Если достигли конца c2 - выйти и вернуть i

            }

return -1; }

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

int find(char c[]){

for (int i=0; c[i]!=0; i++)

            {

            // 1. Попарное сравнение символов c2 - от начала и c1 - от i.

            for (int k=0; c2[k]!=0 && c1[k]==c2[k]; k++);

            // 2. Если достигли конца c2 - выйти и вернуть i

            if (c2[k]==0) return i;

}

return -1; }

Иногда это удается. В простейших случаях удается довести «исторический» процесс программирования до конца и получить даже более компактный код. В качестве примера рассмотрим программу поиска наименьшего общего кратного для массива значений. «Историк» будет рассуждать так:

Установим начальное значение делителя, равное первому элементу массива и начнем просматривать массив.

int F(int A[], int n) { 
  int NOK=A[0];

  for (int i=0; i<n; i++). . .

Если NOK делится на очередной элемент – переходим к следующему.

if (NOK % A[i]==0) continue;

Иначе нужно увеличить NOK на 1 и повторить просмотр с первого элемента.

NOK++; i=0;

Если цикл дойдет до конца, то текущее значение NOK и будет наименьшим общим кратным. Собрав все «до кучи» и убрав лишние ветви, получим

int F(int A[], int n)

{ int NOK=A[0];

for (int i=0; i<n; i++)

if (NOK % A[i]!=0)

{ NOK++; i=0; }

return NOK; }

Для разработанной программы характерно «возвратно-поступательное» изменение индекса i. Это происходит потому, что в теле цикла индекс, регулярно изменяемый в заголовке, периодически сбрасывается. Таким образом, внешне «правильный» цикл ведет себя не так, как это обозначено в заголовке. А это «не есть хорошо». Этот процесс можно разбить на два последовательных, вложенных друг в друга процесса (цикла): внешний перебирает возможные значения NOK, а внутренний – элементы массива с целью определения условия делимости текущего NOK.

//-------------------------------------------------------------------------------------------------------32-03

int F(int A[], int n)

{

for (int NOK=A[0];1;NOK++)       // последовательно проверять NOK

{

for (int i=0; i<n; i++)       // последовательно проверять делимость

if (NOK % A[i]!=0) break;

if (i==n) break;               // все поделились – выход, можно return

}

return NOK; }

Star

Edit on GitHub

3.1. Этапы проектирования программы

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