算法要求：試設(shè)計一個算法，將數(shù)組A[0..n-1]中的元素循環(huán)右移K位，并要求只用一個元素大小的存儲
空間。元素移動或交換的次數(shù)為O（n）
【分析】：本題的應(yīng)用環(huán)境很廣泛，在實用中有很重要意義，如：實現(xiàn)高階乘除法，在游戲選關(guān)和各種
特效中經(jīng)常用到。目前手機等移動設(shè)備應(yīng)用開發(fā)方興未艾，對此常用算法做一個深入的探討很有必要。
作者： 天津大學計算機系 常興龍 MSN：cxl82116@msn.com 本題的難點在于同時對空間復(fù)雜度與時間復(fù)雜度都做了很高的要求，但就本題來講，仍有很多種解
法。這里，探討常見的三種解法：
1.由于每個元素，跟與它相距r×k位形成了一個“循環(huán)”，因此算法保證每次都有一至
二個元素正確歸位，設(shè)一個計數(shù)變量，當計數(shù)變量到達n時，算法結(jié)束
2.對1解法求精，1解中可能使一個元素多于一次的移動，但如果找到n與k的最大公約數(shù)
，就可以解決此問題，從而保證每個元素只移動一次。
3.第三種思想有一定的技巧，直觀理解比較困難，但手有有一副撲克牌，就能清楚地看
到整個過程（把整個排列看成是一個環(huán)形）。它的算法是：先逆轉(zhuǎn)前n-k個元素，再逆轉(zhuǎn)后K個元素，再
把整個序列逆轉(zhuǎn)。
void EMove(int A[n] , int k)
{
for(int i = 0 ; i < n;) //i為到位的元素個數(shù)，做為算法出口
{
/**//**//**//* t是需要到位的元素的靜態(tài)指針 s 指向下一個K步到達的位置 ，
r初值為1 ,在每一循環(huán)圈中置初值一次,做為步進值*/
s = ( t + r * k ) % n ;
A[t]<-->A[s]; //用A[t]為緩沖空間 , 使此鏈上一個記錄到位,到位位置的記錄緩存到緩沖區(qū)中
r++ ; i++;
s = ( t +r *k) %n;
if(s == t) //使兩個記錄到位，一圈結(jié)束
{
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;
/**//**//**//*上面為求最大公約數(shù)的O(n)寫法之一，還可以這么寫:
int p= int(); //這也是一個C++新奇的寫法,int = 0,稍用一下構(gòu)造函數(shù)
while( n !=0 && k !=0)
{
n>k ? n%=k:k%=n;
}
p = n==0?k:n;
p為n與k的最大公約數(shù)
比較性能：注釋中的log(N)性能更好，但是破壞原來數(shù)據(jù)，
如果保留原數(shù)據(jù)，輾轉(zhuǎn)一下，得不償失，這也是棄用的理由
*/
for ( i = 0 ; i < p ; i++) //最大公約數(shù)，實質(zhì)為保證每個元素都到位的子圈數(shù)目
{ //極限情況，若 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];
}//逆轉(zhuǎn)前n-k
for( i = n - k ; i < ( 2*n - k) /2 ; i++)
{
A[n-k+i]<-->A[k-1+i];
} //逆轉(zhuǎn)后K項
for ( i = 0 ; i < n/2 ; i++ )
{
A[i]<-->A[n-1-i];
}//逆轉(zhuǎn)整個鏈
}
補充：
[1]反轉(zhuǎn)鏈的下標確定方法，可以通俗的描寫
從 『鏈開始下標』到 (『鏈終止下標』-『鏈開始下標』)/2 ，反復(fù)做
交換 『鏈開始下標+i』，『鏈終止下標-i』
[2]定義符號<-->為
Swap( int & i , int & j )
{
int temp = i ;
i = j ;
j = temp
}
關(guān)于交換算法，還有一種線性代數(shù)矩陣的寫法
//交換x,y
Swap( int & x , int & y )
{
x=x+y;
y=x-y;
x=x-y;
}
【思考】如果把本題擴充一下，改為把A中的一個子序列擴右移K位（其余要求不變）的算法？（進一步
要求能夠處理K>子序列長度的情況？）（下次提供答案）