### 问题描述 关于本节问题描述，我们在前几节已经出现，即：***[旋转交换](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<stdio.h> //使用辗转相除法求最大公约数 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），用gcd(a,b）表示a，b的最大公约数。r=a mod b，r为a除以b以后的余数，辗转相除法即是要证明gcd(a,b)=gcd(b,r）。 证明证明步骤如下： 1）令c=gcd(a,b），则设a=mc，b=nc 2）r = a mod b，所以r = a - k*b = mc - k*nc = (m - kn) * c。即，r = (m - kn) * c 3）由r = (m - kn) * c 可知：c也是r的因数 4）可以肯定m - kn与n互质（why？)    假设他们不互质，必然存在大于1的整数d，使得m-kn = xd, n = yd。那么，m = xd + kyd = (x + ky)d    那么，a = mc = (x + ky)dc , b = nc = ydc 。=> 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)