Определите смысл и назначение переменных-признаков.

// 1

int F1(char с[]) {

int i,old,nw;

for (i = 0, old = 1, nw = 1; c[i]! = '\0'; i++) {

if (c[i] == ' ') old = 0;

else { if (old == 0) nw++; old = 1;

     }

if (c[i] == '\0') break;

}

return nw;

}

// 2

void F2(char c[]) {

int i, k;

for (i = 0, k = 1; c[i]!= '\0'; i++) {

if (c[i] == '.') k = 1;

if (c[i] >= 'a' && c[i] <= 'z' && k == 1) {

k = 0;

c[i] += 'A'-'a';

      }

}

}

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

Переменная – защелка

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

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

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

 

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

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

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

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

}

 

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

 

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

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

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

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

 

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

//1

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

if (A[i]<0) continue;

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

}

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

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

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

Первый, последний, максимальный, минимальный из возможных

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

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

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

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

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

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

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

 

int i,n1,n2;

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

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

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

Поиск – полный перебор

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

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

//Поиск наименьшего общего кратного чисел n 1, n 2

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

i=n1;

while (1) {

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

i++;

}

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