Juggling算法
最后更新于：2022-04-01 21:40:06
### 问题描述
关于本节问题描述，我们在前几节已经出现，即：***[旋转交换](http://blog.csdn.net/utimes/article/details/8762497)***的引用中问题。提出另一种方案，Juggling算法解决这个问题。（来源于**《编程珠玑》第2版**的第2章第11页问题B）
请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8，i=3，那么向量abcdefgh旋转之后得到向量defghabc。简单编码使用一个具有n个元素的中间向量分n步即可完成此作业。你可以仅使用几十字节的微小内存，花费与n成比例的时间来旋转该向量吗？
### 解析：
直观的想法：由于要对数组整体向左循环移动k位，那么我们就可以对数组中的每一个元素向左移动k位(超过数组长度的可以取模回到数组中)，此时总是能获得结果的。如原串 01234567结果：34567012
步骤：(k表示循环移动的位数)
1)先将x[0]移到临时变量t中
2)将x[k]移动到x[0]中，x[2k]移动到x[k]中，依次类推
3)将x中的所有下标都对n取模，直到我们又回到从x[0]中提取元素。不过这时我们从t中提取元素，结束。
循环的终止条件：当我们要从循环的起始位置点中提取元素时，此次循环结束。由于k，2k...之间的偏移量是相同的，所以整个操作实际上就是讲序列向左移动k个位置。
**注意：**从下标0开始，按照上述步骤移动位置时，一次循环并不一定能够把所有数移到目标位置。这还与n和k是否互质有关。如果，n与k互质，从0开始，每一个元素向前移动k个位置，一次循环就可以处理完所有元素，最后一个元素会从0位置取元素。如果，n与k不互质，仅仅从0开始，每次向前移动k个位置。终止时是不能把所有元素放到目的地的。这是要需要进行gcd(n，k)次循环。即第一次是从0开始，每次向前移动k个位置，直至循环结束。第二次是从1开始，每次向前移动k个位置，直至循环结束。第三次...直到第gcd(n，k)-1次。而且每次循环的最后一个元素都会回到该循环的起点。我们这里把包含gcd(n，k)的元素称为一段，可以看出程序需要进行gcd(n，k)循环才能够把所有数移到目标位置。
### 代码
~~~
#include
//使用辗转相除法求最大公约数
int gcd(int a, int b){
if (a % b == 0) return b;
else return gcd(b, a%b);
}
//杂耍算法
void rotate(char* a,int n,int i){
int step = gcd(n,i);
for(int j = 0; j < step; j++){
int temp = a[j];
int current = j;
while(1){
int next= (current + i) % n;
if(next== j) break;
a[current] = a[next];
current= next;
}
a[current] = temp;
}
}
int main( ){
char a[9] = "abcdefgh";
rotate(a,8,3);
printf("%s\n",a);
return 0;
}
~~~
### 补充知识：
**辗转相除法求最大公约数**
(关于辗转相除法详解：[Euclidean algorithm](http://en.wikipedia.org/wiki/Euclidean_algorithm).)
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的。
原理的证明：
设两数为a、b(b a,b的最大公约数为dc，而不是c。
5）既然m - kn与n互质，所以c = gcd(r,b)。
结论，gcd(a,b)=gcd(b,r）。
**转载请注明出处**：[http://blog.csdn.net/utimes/article/details/8759966](http://blog.csdn.net/utimes/article/details/8759966)
';