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

                                      163

    Недостатком предложенного алгоритма является его медленная работа. В
самом деле, для сдвига массива на r элементов требуется просмотреть массив r раз.
Если воспользоваться алгоритмом переворота части массива, то можно получить
результат за один просмотр массива. Для этого последовательно выполняем
следующие операции (операции показаны на примере массива a={1,2,3,4,5,6,7,8,9}
и r=3):
    1) переворачиваем часть массива между индексами 7 - 9; получаем:
a={1,2,3,4,5,6,9,8,7};
    2) переворачиваем часть массива между индексами 1 - 6; получаем:
a={6,5,4,3,2,1,9,8,7};
3) переворачиваем весь массив; получаем: a={7,8,9,1,2,3,4,5,6}.
    Упражнения:
    1. Запишите описанный алгоритм на Паскале.
    2. Докажите, что в этом алгоритме массив просматривается один раз при любом
r.
    3. Напишите аналогичный алгоритм для сдвига массива влево.
    4. Утверждается, что приведенная ниже программа сдвигает на L элементов
влево одномерный массив a, состоящий из n элементов. Проведите трассировку и
проверьте правильность утверждения.
    x:=L;
    y:=n;
    while x<>y do
       if xn then next:=next-n;
               while next<>i do
               begin a[this]:=a[next];
                       this:=next;
                       next:=next+L;
                       if next>n then next:=next-n
               end;
               a[this]:=temp
    end.

                     11.6.3. Решение задач третьего класса
   В общем случае, когда обрабатываются несколько массивов одновременно, для
каждого массива нужно выбрать подходящую схему перебора, завести свой
индекс, следить, чтобы индекс не вышел за границы массива. В некоторых частных
случаях для обработки нескольких массивов бывает достаточно одного индекса,
потому что элементы массива обрабатываются «синхронно», т.е., зная индекс
элемента одного массива, можно вычислить по некоторой формуле индекс