Конспект лекций по программированию для начинающих. Гладков В.П. - 147 стр.

                                        149

    begin
       {обработка a[i]}
       i:=i*2
    end.
    В общем случае функция изменения индекса может быть очень сложной. При
ее реализации может потребоваться организация дополнительного цикла для
изменения       шага    основного    цикла       или     организация     специальной
процедуры/функции, вычисляющей значение шага цикла.
    Рассмотрим еще пример. Пусть необходимо обработать элементы массива в
следующей последовательности: сначала - все элементы с нечетными индексами,
затем элементы четные, делящиеся на 2, но не на 4, затем все делящиеся на 4, но не
на 8 и т.д.
    Выпишем требуемую последовательность индексов для n = 10 (количество
элементов в массиве равно 10): 1, 3, 5, 7, 9, 2, 6, 10, 4, 8. Анализируя полученную
последовательность индексов, замечаем, что для ее получения массив должен быть
просмотрен несколько раз. Во время одного просмотра шаг не меняется, а при
переходе к следующему просмотру шаг увеличивается вдвое. Поэтому для такой
схемы перебора необходимо организовать два цикла. В первом (внешнем)
происходит изменение шага, а во втором (внутреннем) - просмотр массива с
выбранным шагом. Индекс начала просмотра определяется значением шага
предыдущего просмотра массива. Обозначим h - шаг просмотра; j - индекс
элемента, с которого начинается просмотр; k - индекс обрабатываемого элемента,
тогда схему перебора можно записать так:
    h:=1; { начало просмотра должно начинаться с элемента, принадлежащего
                     данному массиву }
    j:=h;
    while j<=n do
    begin
       h:=h*2;
       k:=j;
       while k<=n do
       begin
              {обработка a[k]}
              k:=k+h
       end;
       j:=h
    end;
    Упражнение. Проведите трассировку представленной выше схемы перебора.
    В приведенном решении использовалась дополнительная переменная j для
указания индекса начала просмотра и переменная h изменялась в начале тела
цикла. Для устранения этих «недостатков» предлагается другое решение.
Количество просмотров массива можно определить по формуле z=]log2n[+1. Здесь
n - количество элементов в массиве, ]x[ - функция, находящая целую часть х, т.е.
наибольшее целое, не превосходящее данное. Эта формула была получена
следующим образом. Для случая n=10 приведенный алгоритм выполняет четыре
просмотра. В первом просмотре обрабатываются индексы 1,3,5,7,9, шаг просмотра