Trong bài toán cho trước, ta được cho một mảng, và ta được yêu cầu xoay mảng d phần tử bằ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] Giải thích : Như bạn thấy ta phải xoay mảng này d = 2 nhưng nhiệm vụ chính là đạt được điều này bằng kỹ thuật đảo ngược.
Ta làm một số tính toán cho xoay mảng bằng kỹ thuật đảo ngược, và ta kết luận −
- Đầu tiên, đảo ngược d phần tử đầu tiên của mảng.
- Thứ hai, đảo ngược các phần tử còn lại.
- Thứ ba, đảo ngược toàn bộ mảng.
Và bằng cách áp dụng ba bước này, ta có thể được mảng đã xoay.
Phương pháp tìm giải pháp
Trong bài toán này, đầu tiên ta sẽ tạo hàm đảo ngược phần tử; bây giờ ta làm theo các bước cho trước
Ví dụ
#include <bits/stdc++.h> using namespace std; void reverseArray(int arr[], int start, int end) { // thuật toán đảo ngược của ta while (start < end) { // nếu start bằng end ta thoát vòng lặp int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } return ; } void Rotate(int arr[], int d, int n) { // hàm xoay if (d == 0) // không cần xoay return; d = d % n; // khi d bằng n mảng quay về dạng ban đầu reverseArray(arr, 0, d - 1); // đảo ngược d phần tử đầu reverseArray(arr, d, n - 1); // đảo ngược phần tử còn lại reverseArray(arr, 0, n - 1); // đảo ngược toàn bộ mảng return ; } int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // mảng cho trước int n = sizeof(arr) / sizeof(arr[0]); // kích thước mảng int d = 2; Rotate(arr, d, n); for(int i = 0; i < n; i++) // in mảng cout << arr[i] << " "; cout << "\n"; return 0; }Kết quả
3 4 5 6 7 1 2
Giải thích mã trên
Trong phương pháp trên, ta trước tiên tạo kỹ thuật đảo ngược, nhận ba tham số: mảng, chỉ số bắt đầu và chỉ số kết thúc, và đảo ngược mảng từ start đến end. Bây giờ, như ta đã phát triển thuật toán trước, ta sẽ áp dụng thuật toán đó dùng hàm này. Ta trước hết đảo ngược d phần tử đầu. Bây giờ thứ hai, ta đảo ngược các phần tử còn lại, và cuối cùng, ta đảo ngược toàn bộ mảng. Kết quả là mảng bị xoay d. Trong hàm rotate, ta làm d = d % n. Điều này là vì nếu xoay n phần tử đầu của mảng, kết quả sẽ giống như trước, đó là lý do ta lấy modulo d với n.
Kết luận
Trong bài viết này, ta giải quyết bài toán áp dụng thuật toán đảo ngược cho xoay mảng. Ta cũng học chương trình C++ cho bài toán này và phương pháp hoàn chỉnh (Bình thường) để giải quyết bài toán. Ta có thể viết cùng chương trình bằng ngôn ngữ khác như C, Java, Python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết hữu ích.