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 要素を反転します。
• 2 番目に、残りの要素を反転します。
• 3 番目に、配列全体を反転します。

これらの 3 つの手順を適用すると、回転された配列を取得できます。

解決方法

この問題では、まず要素を反転する関数を作成し、上記の手順に従います。

例

#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

上記のコードの説明

上記のメソッドでは、まず 3 つのパラメーターを受け入れる反転手法を作成します。つまり、配列、開始インデックスと終了インデックスであり、配列を開始位置から終了位置まで反転します。アルゴリズムは以前に開発したので、この関数を使用してアルゴリズムを適用します。まず、最初の d 要素を反転します。次に、残りの要素を反転し、最後に配列全体を反転します。その結果、配列は位置 d だけ回転されます。回転関数では、d を d % n に設定します。これは、配列の最初の n 要素を回転すると前と同じ答えが得られるため、d を法 n とします。

結論

この記事では、配列の回転に反転アルゴリズムを適用する問題を解決しました。また、C プログラムと、この問題を解決するための完全な (通常の) 方法も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ で書かれた配列回転の反転アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。