Поиск минимального или максимального значения в последовательности встречается достаточно часто. Следующая логическая схема демонстрирует получение в переменной 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';
}
