旋转数组和循环数混乱

Question

问题是编写一个函数rotate（ar[]，d，n），该函数将大小为n的arr[]旋转d个元素。解决方案（变戏法）在这里http://www.geeksforgeeks.org/array-rotation/.让我困惑的是，为什么循环数是n和d的gcd。有人知道这个例子吗？

Answer 1

基本上，开发人员要做的是

    Tmp = arr[0]
    for(i=0; i<n-1;i++){
     arr[i*d % n] = arr[(i+1)*d % n]
}
    arr[n-1] = arr[d-1]

其中GCD（n，d）=1，程序运行良好，例如（n，d）=（5,2）

Tmp = arr[0]
arr[0]= arr[2]
arr[2]= arr[4]
arr[4]= arr[1]
arr[1]= arr[3]

arr[3]= arr[5]

但当GCD（n，d）时

Tmp = arr[0]
arr[0]= arr[2]
arr[2]= arr[4]
arr[4]= arr[0] 
arr[0]= arr[2] // probleme because we are not able to go throw each element so we should break from the loop

由于n/GCD（6,2）=3，我们只能正确修改前三个元素，因此他在循环中加入了一个条件，即如果我们返回到第一个元素，他会中断while并将起始元素增加1，因此在下一次迭代中，他会修改arr[1]，arr[3]，arr[5]

Answer 2

为什么循环数是n和d的gcd

所以循环数是两者的完美分割！如果“c”是所涉及的循环数，那么n应该可以被c完全整除，即n=xc，类似地，d=yc。

现在，在算法中，x是数组中的集合数，y是执行的步骤（或迭代）数。在给定的示例中检查并确认这一点。

选择GCD的主要目的是使x和y是整数，而不是一些浮点值。