算法要求：试设计一个算法，将数组A[0..n-1]中的元素循环右移K位，并要求只用一个元素大小的存储
空间。元素移动或交换的次数为O（n）
【分析】：本题的应用环境很广泛，在实用中有很重要意义，如：实现高阶乘除法，在游戏选关和各种
特效中经常用到。目前手机等移动设备应用开发方兴未艾，对此常用算法做一个深入的探讨很有必要。
作者： 天津大学计算机系 常兴龙 MSN：cxl82116@msn.com 本题的难点在于同时对空间复杂度与时间复杂度都做了很高的要求，但就本题来讲，仍有很多种解
法。这里，探讨常见的三种解法：
1.由于每个元素，跟与它相距r×k位形成了一个“循环”，因此算法保证每次都有一至
二个元素正确归位，设一个计数变量，当计数变量到达n时，算法结束
2.对1解法求精，1解中可能使一个元素多于一次的移动，但如果找到n与k的最大公约数
，就可以解决此问题，从而保证每个元素只移动一次。
3.第三种思想有一定的技巧，直观理解比较困难，但手有有一副扑克牌，就能清楚地看
到整个过程（把整个排列看成是一个环形）。它的算法是：先逆转前n-k个元素，再逆转后K个元素，再
把整个序列逆转。
void EMove(int A[n] , int k)
{
for(int i = 0 ; i < n;) //i为到位的元素个数，做为算法出口
{
/**//**//**//* t是需要到位的元素的静态指针 s 指向下一个K步到达的位置 ，
r初值为1 ,在每一循环圈中置初值一次,做为步进值*/
s = ( t + r * k ) % n ;
A[t]<-->A[s]; //用A[t]为缓冲空间 , 使此链上一个记录到位,到位位置的记录缓存到缓冲区中
r++ ; i++;
s = ( t +r *k) %n;
if(s == t) //使两个记录到位，一圈结束
{
t++; //选择亲的起始点
r=1;
i++;
}//if
}//for
}
[解二]
void EMove(int A[n] , int k)
{
for ( int i = 1; i <= k; i++ )
if ( n%i == 0 && k%i ==0 ) p = j;
/**//**//**//*上面为求最大公约数的O(n)写法之一，还可以这么写:
int p= int(); //这也是一个C++新奇的写法,int = 0,稍用一下构造函数
while( n !=0 && k !=0)
{
n>k ? n%=k:k%=n;
}
p = n==0?k:n;
p为n与k的最大公约数
比较性能：注释中的log(N)性能更好，但是破坏原来数据，
如果保留原数据，辗转一下，得不偿失，这也是弃用的理由
*/
for ( i = 0 ; i < p ; i++) //最大公约数，实质为保证每个元素都到位的子圈数目
{ //极限情况，若 n与k最大公约为1,则一圈就能成功,无需另先起点
j = i;
m = ( i + k ) % n;
temp = A[i]; //缓存
while( m != i)
{
//利用A[j]，交换 temp 与A[m]的值
//A[j]为本次要到位的元素
//A[m]存本次己位的元素
//temp 缓存下次要到位的元素
A[j] = temp ;
temp = A[m] ;
A[m] = A[j] ;
//前进一步
j = m ;
m = ( j + k ) % n ;
}//while
}//for
}//Emove
[解三]
void Emove ( int A[n] , int k )
{
for ( i=0 ; i < ( n - k ) / 2 ; i++ )
{
A[i]<-->A[ n-k-1-i];
}//逆转前n-k
for( i = n - k ; i < ( 2*n - k) /2 ; i++)
{
A[n-k+i]<-->A[k-1+i];
} //逆转后K项
for ( i = 0 ; i < n/2 ; i++ )
{
A[i]<-->A[n-1-i];
}//逆转整个链
}
补充：
[1]反转链的下标确定方法，可以通俗的描写
从 『链开始下标』到 (『链终止下标』-『链开始下标』)/2 ，反复做
交换 『链开始下标+i』，『链终止下标-i』
[2]定义符号<-->为
Swap( int & i , int & j )
{
int temp = i ;
i = j ;
j = temp
}
关于交换算法，还有一种线性代数矩阵的写法
//交换x,y
Swap( int & x , int & y )
{
x=x+y;
y=x-y;
x=x-y;
}
【思考】如果把本题扩充一下，改为把A中的一个子序列扩右移K位（其余要求不变）的算法？（进一步
要求能够处理K>子序列长度的情况？）（下次提供答案）