Недавно я узнал о том, как алгоритм Juggling вращает массив в линейном времени, когда я читал это решение в книге Programming Pearls.
Код для его решения был следующим:
/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int d, int n)
{
int i, j, k, temp;
for (i = 0; i < gcd(d, n); i++)
{
/* move i-th values of blocks */
temp = arr[i];
j = i;
while(1)
{
k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
У меня есть два вопроса относительно этого алгоритма -
- Как GCD определяет количество циклов, необходимых для поворота массив?
- Почему, когда мы заканчиваем цикл, мы начинаем новый цикла из следующего элемента, т.е. не может следующий элемент быть уже часть обработанного цикла?
Я чувствую, что мне не хватает чего-то фундаментального в отношении работы GCD, модуля и циклов.
Следующий вопрос был ответом на мой первый вопрос, но все же я не смог его понять.
Жесткий алгоритм поворота строки
Таким образом, было бы полезно, если бы кто-то мог объяснить это в неспециалистских терминах и принцип, по которому они все гель вместе, чтобы заставить этот алгоритм работать.