設向量x長度為L，要將前N位循環左移。
設待移動的初始位為i，則雜技法是x[i] <->x[i+N] <-> x[i+2N] ….. <-> x[i+kN] ，當(i+kN)%L ==i時，不再移位，並將x[i+kN] = x[i] 此時完成一次移位。設L與N的最大公約數為d，則共需要完成d次移位後，才能完成了前N位的循環左移。
想要證明這種方法的可行性，也就是證明這種方法是否完成了所有位的循環左移N位。
1、設當前位為i，則第(i+N)%L將循環左移到第i位，在此，可將向量作為一個首尾相連的圓環來理解，參考圖1）
2、如何證明一共移了L位呢？
證明：在進行d次移位後，可完成前N位的循環左移，考慮每次移位移動了多少位。設L=αd，N=βd，則由於每次移位在(i+kN)%L ==i時結束，設i+kN = mL +i，則 kβd = mαd，由於α和β互素，則k ==α時，是使得等式成立的最小值，這就證明了每一次移位移動了α位後結束。只有在進行d次移位後，才能讓所有L =αd位循環左移。
3、如何證明每一次移位不會對之前所移的位產生影響呢？
證明：這分為兩種情況進行證明
(1)在一次移位中，不存在一個位被兩次操作的情況，也就是證明(i+kN)%L == i可在一次移位中發生兩次。在2中已證明，想要使得等式成立，至少需要移位α次，由此可證在一次移位中，不可能出現二次操作已被操作的位的情況。
(2)多次移位中，不存在已操作的位被再次操作的情況。證明如下：
設從0開始，進行第一次移位，即i=0時，則 x[0]ß x[0+N]、x[0+N] ß x[(0+2N)%L]
…… x[(0+(α-1)N)%L] ß x[0] 在第一次移位中，不會影響1、2、3、4……d-1 及其倍數位，證明如下：設kN%L = x … r 則 kN = xL +r 即kβd– xαd = r => (kβ – xα)d = r
由此證明，r只能是d的倍數，不可能是1、2、3、4……d-1 及其倍數。
當第一次結束時，i=i+1 =1 ，進行下一次循環，同理也可證，移位操作時，不會影響0、2、3、
4……d-1 及其倍數位，當i=d-1執行完時，移位結束，這時共移了αd位。
到此為止 證明結束
圖1
實現代碼1:
int* vector_loop1(int* array,int len,int loop_num)
{
int i=0,j=0,temp;
int d = gcd(len,loop_num);
while(d)
{
temp = array[i];
while((i+loop_num)%len != j)
{
array[i] = array[(i+loop_num)%len];
i = (i+loop_num)%len;
}
array[i] = temp;
j++;
i=j;
d--;
}
return array;
}實現代碼2
int* vector_loop2(int* array,int len,int loop_num)
{
int i=0,j=0,temp;
temp = array[i];
for(int k=0;k<len;k++)
{
if((i+loop_num)%len == j)
{
array[i] = temp;
j++;
i=j;
}
else
{
array[i] = array[(i+loop_num)%len];
i = (i+loop_num)%len;
}
}
return array;
}
本文出自 “向前飛奔” 博客，請務必保留此出處http://speedonward.blog.51cto.com/4500531/1277391
