Переменная-минимум (максимум)

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

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

Фрагмент if (k > max) max = k; читается так: если новое значение k больше, чем то, которое имеется в max, то мы его запоминаем, иначе оставляем старое.

Если на очередном шаге  переменная max содержит максимальное значение, полученное на предыдущих шагах, то после выполнения if (k > max) max = k; она будет содержать такой же максимум, но уже с учетом текущего шага.

Следует обратить внимание на первый (начальный) шаг. Начальное значение max должно быть меньше первого значения k. Обычно в качестве max выбирают первый элемент последовательности, а алгоритм начинают со второго (или же с первого). Если таковой сразу неизвестен, то состояние поиска первого элемента обозначается специальным значением (признаком). Типичный пример – нахождение  максимального элемента массива:

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

if (A[i] > max) max = A[i];

 

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

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

 

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

for (k = -1, i = 0; i < 10; i++) // k=-1 - нет элемента, принятого за минимальный

{ if (A[i]<0) continue;

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

}

 

Проанализируйте работу фрагмента программы, определите поиск минимума (максимума) и сформулируйте результат работы:

// 1

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

if (A[i] > s) s = A[i];

// 2

for (i = 1,k = 0; i < 10; i++)

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

// 3

char* F6(char* p[]) {

int i,sz,L,k;

for (i = sz = k = 0; p[i]! = NULL; i++)

if ((L = strlen(p[i])) > sz) { sz = L; k = i; }

  return(p[k]);

}                    // strlen(char *) - длина строки

-----------------------------------------------------------------------------------------

Переменная-признак

Признак – это логическая переменная, принимающая значения 0 (false) или 1 (true) в зависимости от наступления какого-либо события в программе (событие наступило – 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;

}

 

Рассмотрим фрагмент программы, подсчитывающий количество пар элементов вида «отрицательный-положительный» в массиве А. Мы чуть выше уже рассматривали такой цикл:

int i, S;

int A[10];

for (i = 1, S =0; i<10; i++)

if (A[i]>0 && A[i-1]<0) S++;

 

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

for (S = 0,k = 0, i = 0; i < n; i++)

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

else              /* здесь A [ i ]>=0 */

{if (k == 1) S ++;     /* и предыдущий элемент < 0 */

            k = 0;

}

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

 

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

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';

}