3.7. Инвариант цикла

Начнем, как обычно, с задачки. В строке, содержащей цепочки одинаковых символов, нужно их обнаружить и заменить на счетчик повторений и один такой символ. Например, из строки «abcdddddddddefggggggggggggggggggx» получить «abc9def18gx». Извечный вопрос русской интеллигенции: «Что делать?».

Типичный ход рассуждений: «Будем просматривать строку в цикле. Если обнаружим повторяющийся фрагмент…» содержит одну существенную недосказанность: как процесс обнаружения повторяющегося фрагмента связан с циклом посимвольного просмотра неповторяющихся символов. Это отдельный процесс – цикл, или он является частью предыдущего.

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

//---------------------------------------------------------37-01.cpp
// "Склеивание" повторяющихся символов строки.
// Использование счетчика повторений. "Грязная программа"
void F1(char in []) {
  int i, k;

  for (i = 0, k = 1; in [i] != 0; i++)
    if ( in [i] == in [i + 1]) k++;
    else {
      if (k > 1) printf("%d", k);

      printf("%c", in [i]);
      k = 1;
    }
}

void main() {
  F1("abcdddddddddddddddefffffffffffffffffffffg");
}

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

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

if (i != strlen(in) && in[i] == in[i+1]) k++; // Символ не последний и за ним такой же
else { // Либо последний, либо пара разных

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

//---------------------------------------------------------37-02.cpp
// Использование счетчика повторений. Переписывание строки
void F2(char in [], char out[]) {
  int i, j, k;

  for (i = 0, j = 0, k = 1; in [i] != 0; i++)
    if ( in [i] == in [i + 1]) k++; // Пара различных - счетчик+1
    else { // Пара одинаковых
      if (k > 1) { // Есть повторения
        int k1, j1; // Записать k в виде символов-цифр
        for (k1 = k; k1 != 0; k1 = k1 / 10, j++);
        for (j1 = j - 1; k != 0; k = k / 10, j1--)
          out[j1] = k % 10 + '0';
      }

      out[j++] = in [i]; // Переписать текущий символ
      k = 1;
    }

  out[j] = 0;
} // Добавить "конец строки"

Инвариант цикла

Заметим, что логика работы программы сильно зависит от предположения, которое мы не отметили явно: за один шаг цикла программа просматривает один символ строки. А есть ли другие варианты? Можно сделать так, что программа будет «выделять» фрагмент за один шаг. Тогда основной цикл станет неравномерным, поэтому неправильно будет писать в его заголовке i++. Вот пример «грязной» программы.

//--------------------------------------------37-03.cpp
// Отдельный цикл "измерения" повторений. "Грязная программа"
void F3(char in []) {
  int i, j, k;

  for (i = 0; in [i] != 0;) {
    for (k = 1; in [i] == in [i + k]; k++); // Измерить длину цепочки
    if (k > 1) printf("%d", k);
    printf("%c", in [i]);
    i = i + k; // Шаг цикла – длина цепочки
  }
}

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

//--------------------------------------------37-04.cpp
// Отдельный цикл "измерения" повторений. "Сжатие строки"
void F4(char in []) {
  int i, j, k;

  for (i = 0; in [i] != 0;) {
    for (k = 1; in [i] == in [i + k]; k++); // Измерить длину цепочки

    if (k == 1) i++; // Нет повторения - пропустить

    else {
      j = i + k; // Запомнить начало "хвоста"
      int k1, j1; // Записать k в виде символов-цифр
      for (k1 = k; k1 != 0; k1 = k1 / 10, i++);

      for (j1 = i - 1; k != 0; k = k / 10, j1--)
        in [j1] = k % 10 + '0'; // Затереть символы цифрами числа

      i++; // «Оставить» один символ
      j1 = i; // i – начало следующего шага

      do {
        in [j1++] = in [j];
        // j1 – куда, j - откуда
      } while ( in [j++] != 0);
    }
  }
}

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

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

Инвариант цикла и метод математической индукции

 Есть еще одна неожиданная параллель между программированием и математикой. В математических доказательствах иногда используется метод математической индукции (ММИ). Звучит он примерно так: если утверждение верно при i=0, и если из того, что оно верно при произвольном i, можно вывести, что оно будет верно при i+1, то оно будет верно всегда.

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

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

Инвариант цикла может быть разным. Самым простым является утверждение типа: «в начале каждого шага цикл находится в…». Например, программа обработки слов в строке может быть построена по принципу «один шаг = одно слово». Тогда инвариантным утверждением будет: «в начале шага программа находится на начале очередного слова».

//--------------------------------------------37-02.cpp
// Пословная обработка: "1 шаг = 1 слово". "Грязная программа"
void F1(char in []) {
  int i = 0, k;

  while ( in [i] == ' ') i++; // ДЛЯ ПЕРВОГО ШАГА

  while ( in [i] != 0) { // 1 шаг = 1 слово
    // Начало слова
    while ( in [i] != ' ' && in [i] != 0) i++;

    // Конец  слова
    while ( in [i] == ' ') i++;
  }
}

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

Аналогичный порядок рассуждений применим и для контекста, обеспечивающего нахождение максимума (минимума). Выражение if (A[i]>s) s=A[i]; сохраняет свойство переменной s быть максимальным значением элементов массива от 0 до i-го. Действительно, если в операции сравнения переменная s содержит максимальное значение в диапазоне от 0 до i-1, то выражение в целом определяет максимальное значение с учетом текущего шага: максимум изменяется, если текущее значение A[i] превышает старое значение максимума, иначе – ничего не происходит.

В соответствии с ММИ необходимо обеспечить справедливость утверждения (инварианта) на первом шаге. Для контекста суммирования это естественно: сумма последовательности из 0 элементов равна 0. Для контекста поиска максимума максимальное значение последовательности из 0 элементов или не определено, или не должно быть «меньше меньшего». Поэтому следует в качестве максимума выбирать значение первого элемента, либо использовать «защелку» для первого шага.

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

for (k = -1, i = 0; i < n; i++) { // поиск минимального из положительных
  if (A[i] < 0) continue; // пропуск отрицательных

  if (k == -1) k = i; // «защелка» на первый положительный
  else if (A[i] < A[k]) k = i; // сравнение минимального с очередным                     
}

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

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

• на этой последовательности формально-логически или интуитивно формулируется искомая зависимость;

• справедливость установленной зависимости доказывается (или, наоборот, опровергается) с использованием ММИ.

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

Снова проведем аналогию с программированием:

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

• на конкретном примере определяются составные части цикла и из них составляется фрагмент циклической программы;

• определяется инвариант цикла;

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

При проектировании циклов часто встречаются два вида ошибок, которые имеют прямое отношение к индуктивному принципу его построения:

• ошибка «первого шага». Первый шаг цикла всегда является особенным, и поведение цикла на этом шаге нужно учитывать как при его проектировании, так и при проверке уже написанной программы. Согласно ММИ шаг цикла получает инвариант от предыдущего шага и сохраняет его с учетом текущего. Поскольку у первого шага нет предыдущего, то это свойство либо следует установить явно и принудительно, либо в теле цикла предусмотреть действия, выполняемые только на первом шаге;

• ошибка «+/- метр от столба». При проектировании цикла легко ошибиться в терминологии «предыдущий-текущий» и «текущий-следующий». Это приводит к тому, что выполняется либо один лишный шаг, либо последний шаг цикла пропускается.