Trong bài toán đã cho, chúng ta được cung cấp một mảng và chúng ta được yêu cầu xoay mảng theo d phần tử bằng cách sử dụng thuật toán đảo ngược, ví 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.
Chúng tôi thực hiện một số tính toán cho vòng quay của mảng bằng kỹ thuật đảo ngược và chúng tôi kết luận rằng -
- Đầu tiên, chúng tôi đảo ngược d phần tử đầu tiên của mảng.
- Thứ hai, chúng tôi đảo ngược các yếu tố còn lại.
- Thứ ba, chúng tôi đảo ngược toàn bộ mảng.
Và bằng cách áp dụng ba bước này, chúng ta có thể có được mảng được xoay vòng của mình.
Phương pháp tiếp cận để tìm ra giải pháp
Trong bài toán này, trước tiên, chúng ta sẽ tạo một hàm để đảo ngược các phần tử; bây giờ chúng tôi làm theo các bước được đưa ra ở trên
Ví 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;
} Đầu ra
3 4 5 6 7 1 2
Giải thích về đoạn mã trên
Trong cách tiếp cận ở trên, trước tiên chúng ta tạo kỹ thuật đảo ngược của mình, kỹ thuật này sẽ nhận ba tham số, tức là mảng, chỉ số bắt đầu và chỉ số kết thúc và đảo ngược mảng của chúng ta từ đầu đến cuối ngay bây giờ. Như chúng tôi đã phát triển thuật toán của mình trước đó, chúng tôi sẽ áp dụng thuật toán đó bằng cách sử dụng hàm này. Trước hết chúng ta đảo ngược d phần tử đầu tiên. Bây giờ, thứ hai, chúng tôi đảo ngược các phần tử còn lại, và cuối cùng, chúng tôi đảo ngược toàn bộ mảng. Kết quả là, mảng của chúng ta được xoay bởi d. Trong hàm xoay, chúng ta đang thực hiện d =d% n. Điều này là do nếu chúng ta xoay n phần tử đầu tiên của một mảng, câu trả lời chúng ta nhận được sẽ giống như trước đó, vì vậy đó là lý do tại sao chúng ta tạo một mod của d với n.
Kết luận
Trong bài này, chúng tôi giải quyết một vấn đề để áp dụng thuật toán đảo ngược cho phép quay mảng. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.