回転配列とサイクル数の混乱

Question

問題は次のとおりです。d要素でサイズnのarr []を回転する関数rotate（ar []、d、n）を書く。 解決策（ジャグリング方法）はこちらhttp://www.geeksforgeeks.org/array-rotation/です。私を混乱させる理由は、サイクル数がnとdのgcdである理由です。誰かが例をもって証明を知っていますか？

Answer 1

サイクル数をnの最大公約数ている理由

とD

サイクルの数は、完全に両方を分割されるように！ 'c'が関係するサイクルの数である場合、nはcによって完全に割り切れるべきであり、すなわちn = x cであり、同様にd = ycである。

ここで、アルゴリズムでは、xは配列内で作られたセットの数であり、yは実行されたステップ（または反復）の数です。この例でこれを確認し、確認してください。

GCDを選択する主な目的は、xとyが整数であり、いくつかの浮動小数点数ではないことです。開発者がやろうどのような基本的

Answer 2

は

GCDは、（N、D​​）= 1プログラムが正常に動作します

Tmp = arr[0] 
    for(i=0; i<n-1;i++){ 
    arr[i*d % n] = arr[(i+1)*d % n] 
} 
    arr[n-1] = arr[d-1] 

、例えば（N、D）=（5,2）

Tmp = arr[0] 
arr[0]= arr[2] 
arr[2]= arr[4] 
arr[4]= arr[1] 
arr[1]= arr[3] 

arr[3]= arr[5] 

です

しかし、GCDは、（N、D​​）> 1、ここでNので/ GCD（6,2）= 3の問題、例えば（6,2）

Tmp = arr[0] 
arr[0]= arr[2] 
arr[2]= arr[4] 
arr[4]= arr[0] 
arr[0]= arr[2] // probleme because we are not able to go throw each element so we should break from the loop 

を起動したとき、我々は最初の3つのみを変更することができます素子正確には、彼は最初の要素に戻ったときに中断し、開始要素を1だけインクリメントするので、次の反復ではarr [1]、arr [3]、arr [ 5]