1. 首頁
  2. 問答
  3. 使用Juggling算法旋轉陣列

使用Juggling算法旋轉陣列

2014-04-27 35 views
18

我最近在閱讀Programming Pearls書中的解決方案時瞭解瞭如何在線性時間內旋轉數組。使用Juggling算法旋轉陣列

的代碼來解決這個問題如下：

/*Function to left rotate arr[] of siz n by d*/ 
void leftRotate(int arr[], int d, int n) 
{ 
    int i, j, k, temp; 
    for (i = 0; i < gcd(d, n); i++) 
    { 
    /* move i-th values of blocks */ 
    temp = arr[i]; 
    j = i; 
    while(1) 
    { 
     k = j + d; 
     if (k >= n) 
     k = k - n; 
     if (k == i) 
     break; 
     arr[j] = arr[k]; 
     j = k; 
    } 
    arr[j] = temp; 
    } 
}

我有一個關於這個算法的兩個問題 -

  1. 怎樣的GCD決定旋轉 所需的週期數陣列？
  2. 爲什麼一旦我們完成了一個循環，我們就從下一個元素開始新的 循環。下一個元素是否已經是已處理循環的一部分？ ？

我的感覺，我缺少關於工作GCD，模和週期一些基本的東西。

以下問題解答了我的第一個問題，但仍然無法理解。

Juggling algorithm of string rotation

所以，這將是有益的，如果有人能在淺白和後面怎麼都凝膠在一起，使這種算法的工作原理解釋。

來源

2014-04-27 Balasubramanian

+1

爲小數組寫出所有步驟可能也會幫助您理解算法。 –

+0

使用k =（j + d）％n代替檢查k> = n並且減去它是否更好？ – avmohan

+0

使用減法代替MOD操作是一個微妙的優化 - 因爲MOD（％）操作比使用減法和if檢查使用更多的CPU週期。從算法中可以看出，k永遠不會大於2 * n。所以，做一個減法就足夠了。 – Balasubramanian

回答

20

GCD如何決定旋轉陣列所需的週期數？

因爲在d步驟內環增量，並且當它到達回到起點停止，即總跨度是的n某一倍數。那個倍數是LCM(n, d)。因此該週期中的元素數量爲LCM(n, d)/d。這些週期的總數是n/(LCM(n, d)/d)，等於GCD(n, d)。

爲什麼一旦我們完成了一個循環，我們就從下一個元素開始新的循環，即下一個元素不能成爲處理循環的一部分？

否內循環以d的步長遞增，這是GCD(n, d)的倍數。因此，當我們開始i第 - 個週期時，對於一次打擊，我們需要(k*GCD + z) % n == i（對於0 <= z < i）。這導致(k*GCD) % n == (i - z)。這顯然沒有解決辦法。

來源

2014-04-27 08:47:31

+0

感謝您的回答。我花了一些時間來了解它的工作。但是，我有一個疑問，爲什麼（k * GCD）％n ==（i-z）不能有解決方案。我試圖解決它，但發現它有點複雜的理解。你能詳細解釋一下嗎？ - 謝謝 – Balasubramanian

+0

@Balasubramanian：因爲'（k * GCD）％n'是'GCD'的倍數。 '（i-z）'不能是GCD的倍數。 –

+0

感謝您的解釋:) – Balasubramanian

2

GCD確實是數學美的一個例子。有時候，當你在腦海中想到這件事時，你的頭腦會爲它所做的事情回答自己的問題，並把它放在一邊。

現在出現了問題，旋轉任務可能只是用for循環工作。雜耍算法可能比它有一些優勢（我沒有找到什麼）。

現在到了爲什麼GCD。 GCD給出了要執行的旋轉的確切數字。它實際上最大限度地減少了旋轉。

例如，如果你想30個號碼

與d的執行旋轉

= 1 外環將被旋轉一次，並內將旋轉30次1*30=30

與d = 2 外環將旋轉兩次而內將旋轉15次2*15=30

其中d = 3 th e外部循環將旋轉三次，內部將旋轉10次3*10=30

所以，GCD在這裏將確保旋轉不超過值30.並且，當您得到的是一個數字，它是總元素的除數，不會讓跳過任何元素

來源

2017-11-09 11:54:59

相關問題

 相關問題