我最近了解了当我在Programming Pearls书中阅读解决方案时,Juggling算法如何在线性时间内旋转数组.
解决它的代码如下:
/*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工作,模数和周期的基本原理.
以下问题回答了我的第一个问题,但我仍然无法理解.
因此,如果有人可以用外行术语解释它以及它们如何凝聚在一起以使该算法起作用的原理将是有帮助的.
Oli*_*rth 35
GCD如何确定旋转阵列所需的周期数？
因为内循环以步长递增d,并且当它回到起始点时停止,即总跨度是某个倍数n.那个倍数是LCM(n, d).因此,该周期中的元素数量是LCM(n, d) / d.这些周期的总数n / (LCM(n, d) / d)等于GCD(n, d).
为什么一旦我们完成一个循环,我们从下一个元素开始新的循环,即下一个元素不能已经成为已处理循环的一部分？
不.内循环以步长递增d,这是...的倍数GCD(n, d).因此,当我们开始第 - i个循环时,我们需要(k*GCD + z) % n == i(for 0 <= z < i).这导致了(k*GCD) % n == (i - z).这显然没有解决方案.
GCD 确实是数学之美的一个例子。有时，当你在脑海中思考这件事时，你的大脑会为它所做的事情做出自己的回答，而不管它是如何发生的。
现在提出问题，轮换任务完全可以用 for 循环来处理。杂耍算法可能比它有一些优势（我没有找到什么）。
现在来点为什么 GCD。GCD 给出了要执行的精确旋转数字。它实际上最大限度地减少了旋转。
例如，
如果要执行 30 个数字的轮换
当 d = 1 时，外环将旋转一次，内环将旋转 30 次 1*30=30
当 d = 2 时，外环将旋转两次，内环将旋转 15 次 2*15=30
当 d = 3 时，外环将旋转三次，内环将旋转 10 次 3*10=30
因此，GCD Here 将确保旋转不超过值 30。当您得到一个作为总元素除数的数字时，它不会跳过任何元素
聚会有点晚了。
虽然奥利弗的回答解释得很好，但我还想对他的解释细节进行更多的阐述。（可能对某人有用！）
GCD 如何决定旋转阵列所需的周期数？
让我们找出为什么外循环的长度应该是GCD(n,k)其中 n 是数组的长度，k 是移位。让我们假设外环的长度应该是x
在数组旋转的杂耍方法中，在内循环中我们基本上将一个数组元素的值j与另一个数组元素的值交换(j+k) mod n
arr[j] = arr[ (j+k) % n ]
因此，假设对于外循环索引，i=0j 的可能值为0, (0+d) mod n, (0+2d) mod n, (0+3d) mod n.....其中 m 是等于 i 的(0+m*d) mod n 最小整数（因为它是循环的）。(0+m*d) mod n
j现在，当的值变得等于i
因此，内部循环终止，
(0+m*d) mod n = i
m*d mod n = 0
因此m*d是可被 n 和 d 整除的最小数，根据定义，可被两个数整除的最小数称为这两个数的 LCM。所以m*d = LCM(n, d)。这只是一个内部循环。所以一个内部循环运行大约LCM(n, d)长度（注意这不是内部循环的运行时间，而只是它覆盖的长度）。因此，旋转一个循环的元素将LCM(n,d)/d 像我们用来d跳转到下一个索引的那样。
因此，一个循环覆盖LCM(n,d)/d
外循环将运行 x 次，并将覆盖数组的所有 n 个元素，因此，
x * LCM(n,d) / d = n
我们可以简化上面的方程并重写如下
x = (n*d) / LCM(n,d)
即 GCD(n,d)。即 GCD 可以通过两个数字的乘积除以它们的 LCM 来计算。
x = GCD(n,d).
为什么一旦我们完成一个循环，我们就从下一个元素开始新的循环，即。下一个元素不能已经是已处理循环的一部分吗？
您可能已经观察到，由于我们k在内循环中将跳跃单位作为时间，一旦内循环完成第一个游程长度 ( LCM(n,d))，它只会在相同的索引上重复，而不会在不同的索引上重复。因此，由于某个起始位置而在第一次运行中未覆盖的索引i将不会被触及，除非您更改i. （这就是外循环改变 的原因i）。例如让我们取一个数组A = [1,2,3,4,5,6]wheren=6并让我们取d=2。
j所以如果我们追踪内循环的索引fori=0它将是
j => 0, 2, 4, 0
并且 fori=1它将是j = 1, 3, 5, 1
在本例中GCD(6,2)为 2。
如果我们选择一个长度为 5 的数组，d=2那么轨迹就会是j => 0, 2, 4, 1, 3, 0，并且只有一个外循环也满足GCD(5,2)= 1。