|
|
|
|
|
|
|
|
|
|
|
Если I = 3 и N = 12, то на этой фазе элементы перемещаются в следующем порядке:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если при этом были перемещены не все элементы, то начнем с элемента X [2] и будем продолжать указанные действия, пока не переместим все элементы. Будьте внимательны! В задаче 3 вам брошен вызов: превратить эту идею в программу.
Следующий алгоритм является следствием другого подхода к задаче: циклически сдвинуть вектор X - это значит в действительности поменять местами две части вектора АВ так, чтобы получился вектор В А, где А соответствует первым I элементам вектора X. Предположим, что А короче, чем В. Разделим В на две части ^ и Вд так, чтобы часть Вд имела такую же длину, что и А. Поменяем местами А и BR, чтобы трансформировать ABlBj^ в Bj^A. Последовательность элементов А на своем конечном месте, поэтому мы можем сосредоточиться на перестановке двух частей В. Так как эта новая задача аналогична исходной, решать ее можно рекурсивно. Такой алгоритм может привести к изящной программе (в решении задачи 3 описано итеративное решение из восьми строк, предложенное Гризом и Миллзом), но требует искусного программирования и некоторых раздумий, чтобы убедиться в его эффективности.
Эта задача выглядит трудной до тех пор, пока вас не посетит ага! Озарение: давайте посмотрим на нее как на трансформацию массива АВ в массив ВА, но предположим, что у нас есть подпрограмма, которая реверсирует (меняет порядок элементов на обратный) заданную часть массива. Начав с массива АВ, мы реверсируем его часть А, чтобы получить ARB; реверсируем часть В, чтобы получить ARBR; а потом реверсируем их совокупность и получаем (A BR)R, что в точности соответствует массиву ВА. Это приводит к следующей программе для циклического сдвига (в комментариях показаны результаты при циклическом сдвиге последовательности ABCDEFGH на 3 элемента):
|
|
|
|
|
|
|
|
Reverse(1,1) Л CBADEFGH */
Reverse(I+i,K) /* CBAHGFED */ Reverse(1,N) /I DEFGHABC */
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
