使用C++編寫的數組旋轉的逆轉演算法

在給定的問題中，我們有一個數組，我們需要使用反轉演算法將數組旋轉d個元素，例如−

Input : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Output : arr[] = [3, 4, 5, 6, 7, 1, 2]
Explanation : As you can see we have to rotate this array by d = 2 but our main task is to achieve this by using a reversal technique.

我們對數組的旋轉進行了一些反轉技術的計算，並得出結論：

• 首先，我們反轉數組的前d個元素。
• 其次，我們反轉剩下的元素。
• 第三，我們反轉整個陣列。

透過應用這三個步驟，我們可以得到旋轉後的陣列。

解決方案的方法

在這個問題中，首先，我們要寫一個反轉元素的函數；現在我們按照上述步驟進行操作。

範例

#include <bits/stdc++.h>
using namespace std;

void reverseArray(int arr[], int start, int end) { // our reversal algorithm
   while (start < end) { // if start becomes equal to end we break the loop
      int temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;
      start++;
      end--;
   }
   return ;
}
void Rotate(int arr[], int d, int n) { // rotation function
   if (d == 0) // no rotation required
      return;
   d = d % n; // when d becomes equal to n so our array comes to its original form
   reverseArray(arr, 0, d - 1); // reversing first d elements
   reverseArray(arr, d, n - 1); // reversing the remaining elements
   reverseArray(arr, 0, n - 1); // reversing the whole array

   return ;
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int d = 2;
   Rotate(arr, d, n);
   for(int i = 0; i < n; i++) // printing the array
      cout << arr[i] << " ";
   cout << "\n";
   return 0;
}

輸出

3 4 5 6 7 1 2

上述程式碼的解釋

在上述方法中，我們首先建立了一個反轉技術，它將接受三個參數，即陣列、起始索引和結束索引，並將我們的陣列從起始位置到結束位置反轉。由於我們之前已經開發了演算法，我們將使用這個函數來應用該演算法。首先，我們反轉前d個元素。然後，我們反轉剩餘的元素，最後，我們反轉整個陣列。結果是，我們的陣列被旋轉了d個位置。在旋轉函數中，我們將d設定為d % n。這是因為如果我們旋轉數組的前n個元素，得到的答案會與之前相同，所以我們對d取模n。

結論

在本文中，我們解決了一個應用反轉演算法進行陣列旋轉的問題。我們也學習了解決這個問題的C 程序和完整的（正常）方法。我們可以用其他語言如C、Java、Python和其他語言來寫相同的程式。希望本文對您有幫助。

以上是使用C++編寫的數組旋轉的逆轉演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！