2.4. Стандартные программные контексты

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

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

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

Стандартные программные контексты присваивания

Наибольшим количеством интерпретаций и «смыслов» обладает присваивание. Понимать его как простое запоминание результатов – слишком примитивно. Ведь запоминать можно не только данные, но и условия, события и обстоятельства работы программы, а это имеет отношение к ее поведению. Программа может запомнить, что с ней было, а потом, в определенных обстоятельствах, вспомнить. Этим она отличается от других формальных систем «без памяти», например конечных автоматов. Следовательно, присваивание поднимает уровень поведения программы от инстинктивного до рефлекторного. Аналогия с животным миром вполне уместна. Инстинктивное поведение – это воспроизведение заданной последовательности действий, хоть и зависящих от внешних обстоятельств, но не включающих в себя запоминания и, тем более, обучения. Поэтому присваивание обеспечивает качественно иной уровень поведения программы.

Присваивание – запоминание фактов и событий в истории работы программы.

Кроме того, такие действия как обмен, сдвиг, перенос данных – это тоже интерпретации присваивания.

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

Правило «трех стаканов». Уже из названия ясно: чтобы поменять содержимое двух стаканов, не смешивая, необходим третий. Стакан – это переменная, жидкость – значение.

// Обмен значений  переменных a,b с использованием переменной c
int a = 5, b = 6, c;

c = a; // перелить содержимое первого стакана в пустой (третий) стакан
a = b; // перелить второй в первый
b = c; // перелить третий во второй

Обратите внимание на слово «не смешивая». Есть еще один вариант, в котором используется сложение и вычитание.

// Обмен значений  переменных a,b с использованием сложения и вычитания
int a = 5, b = 6;

a = a + b; // в переменной a сумма начальных значений a и b
b = a - b; // в переменной b  - (a+b)-b = a
a = a - b; // в переменной a -  (a+b)-a = b

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

Сдвиг элементов в массиве, вставка, удаление. Присваивание вида A[i]=A[i+1] интерпретируется как сдвиг элемента массива (последовательности) на один влево, хотя формально он читается как копирование следующего элемента в текущий. Операции вставки и удаления элементов последовательности сопровождаются таким «массовым» сдвигом. Рассмотрим несколько примеров.

Из последовательности элементов в памяти (массиве) нужно удалить заданный. Для устранения возникшего «пустого места» нужно все элементы справа сдвинуть на одну позицию влево. Чтобы сдвинуть всю оставшуюся часть, нужен цикл, перебирающий все пары слева – направо, начиная с удаляемого, внутри которого происходит сдвиг влево (присваивание вида A[i]=A[i+1]). Для вставки значения на заданную позицию нужно сделать все наоборот – раздвинуть элементы, перемещая их вправо. При этом цикл перебора пар также будет двигаться в обратном направлении от последнего элемента к первому.

// Удаление k-го элемента последовательности
int A[] = {1,7,3,4,7,6,3,7,4,3}, n=10;
int k = 2;
int vv = A[k];

for (int i = k; i < n-1; i++) A[i] = A[i+1];

n--;

//----Вставка k-го элемента в последовательность
int A[20] = {1,7,3,4,7,6,3,7,4,3}, n=10;

int k = 2, vv = 15;

for (int i = n-1; i >= k; i--) A[i+1] = A[i];
A[k]=vv;
n++;

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

Есть еще один оригинальный метод вставки, который вызывает ассоциации с жонглированием. Если мы хотим включить значение vv на позицию k, то нам мешает это сделать находящееся там значение. Образно говоря, «подбросим его вверх» в переменную vv1, а на освободившееся место запишем новое значение. Полученное «лишнее» значение vv1 надо вставить на следующую позицию, т.е. повторить все, что было, в цикле. И еще надо не забыть скопировать vv1 в vv, чтобы следующий шаг начался при тех же условиях. Образно говоря, пока «шарик» в воздухе, на его место помещается новый.

int A[20]={1,7,3,4,7,6,3,7,4,3}, n=10;
int k=2,vv=15,vv1;

for (int i=k;i<=n;i++) {
  vv1=A[i]; // Текущий «подбросить вверх»
  A[i]=vv;  // На его место поместить новый
  vv=vv1;   // «Подброшенный» будет вставляться на следующую
            // позицию 
} 

n++;                                         

Качественно ничего не изменится, если производить удаление или вставку нескольких элементов. Просто перенос происходит не на один, а на несколько элементов вперед или назад. Например, функция, удаляющая в строке слово с заданным номером, после того, как она определит индексы его начала и конца, должна выполнить процесс посимвольного перенесения «хвоста» строки. В нем вместо индексов j и j+1 нужно использовать индексы j и j+m, «разнесенные» на длину слова m, либо индексы начала и конца слова i и j.

//------------------------------------------------------24-01.cpp
//------ Удаление слова с заданным номером
void CutWord(char c[], int n) {
  int j=0; // j - индекс конца слова
  for (j = 0; c[j] != 0; j++)
    if (c[j] != ' ' && (c[j+1] == ' ' || c[j+1] == 0))
      if (n-- == 0) break;      // Обнаружен конец n-го слова
    if (n == -1 && c[j] != 0) { // Действительно был выход по концу слова
      for (int i=j; i>=0 && c[i]!=' '; i--); // Поиск начала слова
      i++;                                   // Вернуться на первый символ слова
      for(j++; c[j]!=0; i++, j++)            // Перенос очередного символа
        c[i]=c[j];                           // ближе к началу
      c[i]=0;                                // Сам конец строки не был перенесен
    }
}

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

• место (конструкция алгоритма), в котором происходит запоминание, определяется условиями, при которых программа туда попадает. Например, при обменной сортировке место перестановки пары элементов запоминается в том фрагменте программы, где эта перестановка происходит.

for (i=0; i<n-1; i++)
  if (A[i]>A[i+1]) { // условие перестановки            
    c=A[i]; A[i]=A[i+1]; A[i+1]=c; // перестановка
    b1=i; // Запоминание индекса в момент перестановки
  }

• запоминающая переменная имеет тот же самый смысл, (ту же самую смысловую интерпретацию), что и запоминаемая. Так, в предыдущем примере, если переменная i является индексом в массиве, то b1 также имеет смысл индекса.

• если запоминание производится в цикле, то по окончании цикла будет сохранено значение последнего из возможных. Так в нашем примере b1 – это индекс последней перестановки. Если же требуется запомнить значение первого из возможных, то присваивание нужно сопроводить альтернативным выходом из цикла через break. Если требуется запоминание максимального/минимального значения, то присваивание нужно выполнить в контексте выбора минимума/максимума.

Стандартные программные контексты переменных

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

Переменная – счетчик. Переменная считает количество появлений в программе того или иного события, количество элементов, удовлетворяющих тому или иному условию. Фрагмент, определяющий смысл переменной-счетчика, выглядит так:

for (m=0,...) { if (...удовлетворяет условию...) m++; }

Логика данного фрагмента очевидна: переменная-счетчик увеличивает свое значение на 1 при каждом выполнении проверяемого условия. Остается сформулировать только смысл самого условия. В следующем примере переменная m подсчитывает количество положительных элементов в массиве.

for (i=0, m=0; i<n; i++) if(A[i]>0) m++;

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

for (m = 0, i = 0; c[i] != 0; i++)
  if (c[i] == ’ ’) m = 0; else m++;

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

for (s=0,...;...;...) { получить k; s=s+k; }

Он дает переменной s единственный смысл - переменная накапливает сумму значений k, полученных на каждом из шагов выполнения цикла. Этот факт достаточно очевиден и сам по себе – на каждом шаге к значению переменной s добавляется новое k и результат запоминается оба том же самом s. Для особо неверующих в качестве строгого доказательства можно привлечь метод математической индукции. Действительно, если на очередном шаге цикла s содержит сумму, накопленную на предыдущих шагах, то после выполнения s=s+k она будет содержать сумму уже с учетом текущего шага. Кроме того, утверждение должно быть верно в самом начале – этому соответствует обнуление переменной s для суммы и установка ее в 1 для произведения.

for (s=0,i=0; i<10; i++) s=s+A[i];

for (s=1,i=0; i<10; i++) s=s*A[i];

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

for (s = 0, i = 0; i < n; i++) // Сумма элементов массива
  s+=A[i];

for (s = 0, i = 0; i < n && A[i] >= 0; i++) // Сумма элементов массива до первого
  s+=A[i];                         // отрицательного

for (s = 0, i = 0; i < n; i++) // Сумма положительный элементов
  if (A[i]>0) s += A[i];       // массива

for (s = 0, x = 0; x <= 1; x += 0.1) // Сумма значений функции sin
  s+=sin(x);                // в диапазоне 0..1 с шагом 0.1

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

for (s=меньше меньшего,...;...;...) { получить k; if (k>s) s=k; }

Доказать это не сложнее, чем в случае с переменной-накопителем. Фрагмент if (k>s) s=k; читается буквально так: если новое значение больше, чем то, которое имеется у вас, вы его запоминаете, иначе оставляете старое. То есть осуществляется обычный принцип выбора «большего из двух зол». Формальное доказательство как иллюстрация метода математической индукции уже было проведено в 2.3. Типичный пример контекста - нахождение максимального элемента массива.

for (s=0,i=0; i<10; i++) if (A[i]>s) s=A[i];

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

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

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

for (s = 0, k = 0, i = 0; i < n && k == 0; i++) {
  s+=A[i];
  if (A[i]<0) k=1;
}

В данном случае переменная-признак k устанавливается в 1 после обнаружения и добавления к сумме отрицательного элемента массива. Установка этого признака нарушает условие продолжения и прекращает выполнение цикла. Эквивалентный вариант с использованием break позволяет обойтись без такого признака.

for (s = 0, i = 0; i < n; i++) {
  s += A[i];
  if (A[i] < 0) break;
}

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

for (i=0,s=0,k=0; i<10; i++)
  if (A[i]<0) k=1;
  else { 
    if (k == 1) s++;  k=0; 
  }

Несложно догадаться, что смысл переменной-признака k - элемент массива является отрицательным, причем в начале следующего шага признак сохраняет свое значение, полученное на предыдущем. Счетчик s увеличивается, если выполняется ветка else - текущий элемент массива положителен, и в то же самое время условие k==1 - соответствует отрицательному значению предыдущего элемента массива, поскольку его сброс в 0 происходит позже. Следовательно, фрагмент подсчитывает количество пар элементов вида «отрицательный - положительный».

Еще один пример - обнаружение комментариев в строке. Признак com устанавливается в 1, если программа находится «внутри комментария». Процесс переписывания происходит при нулевом значении признака, то есть «вне комментария»

void copy(char dst[], char src[]) { 
  int i,com=0,j=0;

  for (com=0,i=0; src[i]!=0; i++)
    if (com==1) { // внутри комментария
      if (src[i]==’*’ && src[i+1]==’/’) { 
        com=0; i++; // не в комментарии, пропустить символ 
      } 
    } else { // вне комментария
      if (src[i]==’/’ && src[i+1]==’*’) { 
        com=1; i++; // в комментарии, пропустить символ
      } else dst[j++] = src[i]; // переписать символ в выходную строку
    }
  
  dst[j]=0; 
}

Кстати, для исключения вложенных комментариев можно предложить другую смысловую интепретацию переменной – уровень вложенности, увеличивая ее на 1 при входе и уменьшая при выходе.

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

for (k=-1,i=0; i<n && A[i]<0;i++);             // Пропуск до первого положительного

for (; i<n; i++){                                       // Цикл среди оставшихся

if (A[i]<0) continue;                     // Пропуск отрицательных

if (A[i]<A[k]) k=i;                                    // Сравнение «в пользу минимального»

            }

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

for (i=0,k=-1; i<10; i++) {             // k=-1 – защелка, не обнаружен положительный

if (A[i]<0) continue;         // пропуск отрицательных

            if (k==-1) k=i;                 // срабатывает защелка на первом положительном

else  if (A[i]<A[k]) k=i;    // на втором и последующих - сравнение

Стандартные программные контексты циклов

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

Предыдущий, текущий, следующий. Если имеется последовательность адресуемых по номеру элементов, например, элементов массива, то по отношению к i-му элементу, с которым программа работает на текущем шаге цикла, i-1 будет предыдущим, а i+1 – последующим. Так и следует, особенно не задумываясь, переводить с формального на естественный язык и обратно.

int F(char c[]){

int nw=0;

if (c[0]!=0) nw=1;                                    // Строка начитается на с пробела – 1 слово

for (int i=1; c[i]!=0; i++)                           // Сочетание не пробел, а перед ним -пробел

            if (c[i]!=’ ‘ && c[i-1]==’ ‘) nw++;

return nw;}

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

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

//---------------------------------------24-02.cpp

// Поиск чисел с возрастающими цифрами

void main(){

for (int a=100000; a<200000; a++){

            int n,k,kp=10,m=1;                                 // m - признак убывания

            for(n=a;n!=0;n=n/10){                              // kp - предыдущая цифра

                        k=n%10;                                   // k - очередная цифра

                        if (k>=kp){ m=0; break; }             // нет убывания - выход

                        kp=k;                                        // текущая стала предыдущей

                        }

            if (m!=0) printf("%d\n",a);

            }}

Аналогичные присваивания производятся в итерационных циклах, где каждый шаг характеризуется «текущим» значением переменной, вычисляемой или выводимой из ее «предыдущих» значений, точнее, значений на предыдущих шагах того же цикла. В них при переходе к следующему шагу «текущее» значение становится «предыдущим», а иногда и «вчерашнее» - «позавчерашним» (см. 4.3).

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

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

Количество индексов в программе соответствует количеству независимых перемещений по массиву (степеней свободы).

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

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

//-------------------------- «Переворачивание» строки

void swap(char c[]){

int i,j;

// Цикл поиска конца строки для j

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

// Цикл попарного обмена

for (j=0,i--; i>j; i--,j++)                            

            { char s; s=c[i]; c[i]=c[j]; c[j]=s; }}

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

//-------------------------- Слияние упорядоченных последовательностей

 void sleave(int out[], int in1[], int in2[], int n){

 int i,j,k;                                                // Каждой последовательности - по индексу

 for (i=j=k=0; i<2*n; i++){

            if (k==n) out[i]=in1[j++];              // Вторая кончилась - сливать первую

            else

if (j==n) out[i]=in2[k++];             // Первая кончилась - сливать вторую

            else                                         // Сливать меньший из очередных

            if (in1[j] < in2[k]) out[i]=in1[j++];

            else out[i]=in2[k++]; }}

Обратите внимание, что синтаксис …=in1[j++] понимается как «взять очередной и переместиться к следующему».

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

//----------------------- Разделение массива относительно медианы

 int two(int in[], int out[], int n, int mid){

 int i,j,k;

 for (i=0,j=0,k=n-1; i<n; i++){                   // j,k - по концам выходного массива

            if (in[i]<mid) out[j++]=in[i];           // Переписать в левую часть

            else      out[k--]=in[i];                  // Переписать в правую часть

} return j; }                                 // Вернуть точку разделения

Еще один маленький нюанс. Индексы j, k указывают на очередные свободные позиции выходного массива, а синтаксис out[j++]=… понимается как «записать очередным и переместиться к следующему свободному».

Результат цикла – место его остановки. Как известно, тело цикла представляет собой описание повторяющегося процесса, а заголовок – параметры этого повторения. Можно представить себе «бестелесный» цикл. Тогда возникает резонный вопрос: зачем он нужен? Ответ: результатом цикла является место его остановки. Оно, в свою очередь, определяется значениями переменных, которые используются в заголовке цикла. Такие циклы либо вообще не имеют тела (пустой оператор), либо содержат в теле проверки условий, сопровождаемых альтернативными выходами через break.

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

//-----------------------------Вставка с сохранением порядка

void ins_sort(int A[], int &n, int v){

int j,k;                    

for (k=0; k<n && v>A[k]; k++);                // Цикл (пустой) останавливается на месте включения

for (j=n-1; j>=k; j--) A[j+1]=A[j];               // Вставка на позицию k – сдвиг влево

A[k]=v;

n++;}

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

//------------------------------------------------------24-03.cpp

//--- Поиск подстроки в строке

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

for ( int i=0; c1[i] !='\0'; i++){

              for ( int j=0; c2[j] !='\0'; j++)

                           if (c1[i+j] != c2[j]) break;

              if (c2[j] =='\0') return i;

              }

return -1;}

 

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

for (int i=0,j=0; c1[i]!='\0'; i++,j++){

            if (c2[j]==0) return i-j;

            if (c1[i]!=c2[j]) { i=i-j; j=-1; }

            }

return -1;}

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

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

Второй вариант лишен всех этих сложностей, в нем индексы совершают сложное возвратно-поступательное движение в рамках одного цикла. Аналогично, происходит попарное сравнение i-го и j-го символов в строках. При их совпадении оба индекса продвигаются вперед, пока не будет обнаружен конец второй строки. При несовпадении второй индекс явно возвращается в начало, а первый – на j-1 назад (i=i-j; i++ в заголовке цикла). Это соответствует переход к попарному сравнению в первой строке на один символ вперед. Основным недостатком этого варианта является отсутствие структурированности – он не раскладывается на независимые циклы.

Свойства всеобщности и существования

«Ваше кредо? Всегда».

Ильф и Петров. «Двенадцать стульев».
Из высказываний О.Бендера

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

A={ A1, A2,…,An}

"усл(A)= усл(A1)& усл(A2)& … & усл(An)

\$усл(A)= усл(A1)| усл(A2)| … | усл(An)

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

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

//-------------- Проверка свойств «для всех» и «существует» при помощи счетчика

int i,s=0;                      

for (i=0;i<n;i++) if (A[i]<0) s++;

if (s==0) «все >=0»

if (s==n) «все <0»

if (s!=0) «существуют <0»

if (s!=n) «существуют >=0»

На самом деле не всегда нужно выполнять проверку до конца. Если на очередном шаге проверяемое условие не выполняется, то это означает нарушение свойства «для всех», и дальнейшая проверка теряет смысл. Этот факт можно зафиксировать отдельным признаком.

//--------------- Проверка свойств «для всех» и «существует» с помощью признака
int i,s=1;                       // признак «оптимистически» установлен в значение «для всех»

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

            if (A[i]<0)           // условие всеобщности нарушается

{s=0; break; }     // сбросить признак и выйти

if (s==1) «все >0»

else «существуют <=0»

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

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

//-------------- Проверка свойств «для всех» и «существует» по месту остановки цикла

for (i=0; i<n && A[i]>0;i++);         // «пустой» цикл с выходом по двум условиям

if (i==n) «все >0»                      // был выход по окончании последовательности

else      «существуют <=0»       // был выход по обнаружению неположительного

Из формальной логики известно, что свойства всеобщности и существования взаимосвязаны. Отрицание свойства «для всех» эквивалентно свойству существования для обратного условия, и наоборот.

!"усл(A) ≡ \$!усл(A) !\$усл(A) ≡ "!усл(A)

Пример. Свойство всеобщности проверяется при проверке, является ли заданное число простым. Число простое, если оно делится только на 1 и на само себя. Слово «только» означает исключительное выполнение условия для этих значений, на самом деле сформулировать это условие нужно иначе: «для всех» чисел k=2..m-1 (m – само число) число m не делится на k. Этот факт можно установить путем анализа условий завершения цикла проверки.

//--------------------------------------------------------------------24-04.cpp

//------- Поиск простых чисел - проверка всех делителей

void F1(int val, int A[], int n){

int i,m,k;

for (i=0, m=2; i<n-1 && m<val; m++) {

            for (k=2; k<m && m%k!=0; k++);                        // Пустой цикл проверки делимости

            if (m==k) A[i++]=m;                               // Дошли до конца - на все НЕ ДЕЛИТСЯ

            }

 A[i] = 0;}

Более эффективный алгоритм не имеет ту же схему: проверяется свойство «не делится» по отношению ко всем уже накопленным простым числам (решето Эратосфена). Если в первом случае проверялось, дошло ли проверяемой значение k до проверяемого (k==m), то во втором случае – дошел ли индекс k до конца последовательности накопленных простых чисел (k==i).

//--------------------------------------------------------------------24-04.cpp
//------- Поиск простых чисел - проверка деления на накопленные простые

void F2(int val, int A[], int n){

int i,m,k;

for (i=0, m=2; i<n-1 && m<val; m++) {

            for (k=0; k<i && m%A[k]!=0; k++);

            if (k==i) A[i++]=m;                                 // Цикл дошел до конца массива простых -

            }                                                           // на все НЕ ДЕЛИТСЯ

 A[i] = 0;}

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

//----- Неструктурированный вариант проверки свойства «для всех»

int i;                 

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

            if (A[i]<0) { что-то делать с отрицательным… goto M; }

что-то делать, когда все положительны

M: общее продолжение…

При проверке свойства «для всех» можно обойтись и без goto. Если вынести в заголовок цикла проверку самого условия, а проверку конца последовательности делать в теле цикла, то действие при обнаружении свойства «для всех» можно запихнуть туда же.

//----- Неструктурированный вариант проверки свойства «для всех» без goto

k=2;

while(m%2!=0){                                      // пока нет делителей для n

            k++;

            if (k==m){                                  // просмотр закончен – число простое

                        { A[i++]=n;  break; }       // сохранить простое и выйти

}

Другие стандартные контексты

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

• простой линейный перебор последовательности элементов или значений какой-либо переменной;

• перебор возможных пар элементов (4.6);

• рекурсивный комбинаторный перебор подмножеств, сочетаний и т.п. (7.4).

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

int i,n1,n2;                                 // Первое деление  - общее кратное

i=n1;  while (1) if (i%n1==0 && i%n2==0) break;

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

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

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

• для поиска элемента с максимальным или минимальным значением необходимо перебрать все множество с использованием соответствующего контекста;

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

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

Для сравнения приведем варианты поиска первого, последнего и минимального положительного элемента в массиве.

int A[20]={...}; int i,k;

for (k=-1,i=0; i<20; i++){              // Первый положительный

            if (A[i]<0) continue;

            k=i; break; }

for (k=-1,i=0; i<20; i++){              // Последний положительный

            if (A[i]<0) continue;

            k=i; }

for (k=-1,i=0; i<20; i++){              // Минимальный положительный

            if (A[i]<0) continue;

            if (k==-1 || A[i] < A[k]) k=i; }

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

int i,n1,n2; 

for (i=n1-1; !(n1 % i ==0 && n2 % i ==0); i--);                    // Первый общий делитель - наибольший

for (i=n1; !(i % n1 ==0 && i % n2 ==0); i++);                    // Первое общее кратное - наименьшее

Житейский смысл логических операций. Безусловно, нет нужды повторять определение логических операций И, ИЛИ, НЕ, используемых в любом языке программирования. Уместно напомнить как «переводятся» эти операции на естественный язык при чтении программ:

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

• содержательный смысл логической операции ИЛИ передается фразой "хотя бы один..." и заключается в объединении условий;

• содержательный смысл логической операции НЕ передается фразой "хотя бы один..." и заключается в проверке обратного условия.

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

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

// Цикл завершается при обнаружении пары "меньше 0 - больше 0"

for (i=1; i<20 && !(A[i-1]<0 && A[i]>0); i++);

• оператор прерывания цикла break по условию, размещенный в начале тела цикла, может быть вынесен в заголовок цикла в виде инвертированного условия продолжения цикла, объединенного с имеющимся ранее по И;

for (int i=0; i<20; i++){                             // До конца массива

            if (A[i]<0) break;                         // Отрицательный - выход

...}

for (int i=0; i<20 && A[i]=>0){                  // Пока не кончился массив

            ...}                                            // И элемент неотрицательный

• инверсия условий, объединенных по И, раскрывается как объединение по ИЛИ обратных условий и наоборот.

// Цикл прекращается, когда одновременно оба равны 0
for (i=1; !(A[i-1]==0 && A[i]==0); i++)...

// Цикл продолжается, пока хотя бы один не равен 0

for (i=1; A[i-1]!=0 || A[i]!=0; i++)...

Стандартные контексты в других областях программирования. Каждая область программирования имеет свои контексты, интерпретации и наработанные приемы. Например, при решении арифметических задач остаток от деления на 10 интерпретируется как младшая десятичная цифра числа, а последовательность остатков в цикле деления исходного числа на 10 дает нам цифры числа в обратном порядке (4.2).