Задача на сообразительность: Циклический сдвиг массива
Теперь я предлагаю Вашему вниманию еще одну интересную задачку. Пусть у нас
есть массив размером N. Нам надо написать процедуру, которая бы выполняла циклический
сдвиг вправо на K элементов. K может быть любым, в т.ч. больше N. При этом запрещено:
- выделять буфер соизмеримый по размеру с N и K
- использовать рекурсию
- Сложность алгоритма должна быть o(N).
Ниже приведено решение, которое прислал наш читатель. Если у Вы знаете альтернативный
вариант - присылайте. Я его опубликую.
Решение от Mr. Wanderer.
void rev(unsigned char * B, int N)
{
// Разворачиваем строку. С применением алгоритма из
// предыдущей задачи :)
unsigned char * E = B + N - 1;
for(N = N/2; N; --N)
{
*B ^= *E;
*E ^= *B;
*B++ ^= *E--;
}
}
void shift(unsigned char * B, int N, int K)
{
// Начнем с того, что надо сдвигать по модулю. Сдвиг на N -
// это как поворот на 360 градусов :)
if (K %= N) {
// Теперь K заведомо не достает до N, но и не 0
// Любимый метод Цезарей - разделять и властвовать :)
// У кого же это было описано... Не у Бентли ли?
// Автору рассылки надо было просить сдвинуть влево - все же<BR> // интереснее, лишнее действие :)
// Словом, развернем массив задом наперед
rev(B,N);
// а теперь отсчитаем, сколько надо, и развернем хвосты
rev(B,K);
rev(B+K,N-K);
}
// Буферов вообще нет, только одна дополнительная переменная в rev...
// Рекурсии не видно.
// Операций xor - порядка 3N, 3 деления на 2 и N декрементов
// В o(N) вроде вписывается...
// Конечно, можно было бы раскрыть rev прямо в shift, но так понятнее :)
}
void main()
{
unsigned char * s = "abcdefgh";
printf("%s\n",s);
shift(s,8,0);
printf(" 0: %s\n",s);
shift(s,8,1);
printf(" 1: %s\n",s);
shift(s,8,5);
printf(" 5: %s\n",s);
shift(s,8,15);
printf("15: %s\n",s);
}
Коментарии к статье|
Сам алгоритм отличный.
как раз недавно чтото подобное приходилось реализовывать.
Хочу указать на недостати.
Вот это с точки зрения процессора:
unsigned char * E = B + N - 1;
for(N = N/2; N; --N)
{
*B ^= *E;
*E ^= *B;
*B++ ^= *E--;
}
1) Очень сильно \"гуляет \" по памяти => слабая помощи кыша и предвыборки
2) Нагрузка на АЛУ. тогда как цепоченые команды могли бы отработать быстрее |
|
