### 問題描述 關于本節問題描述，我們在前幾節已經出現，即：***[旋轉交換](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)