Trong bài toán này, chúng ta được cho một mảng số và chúng ta phải in các phần tử của mảng theo thứ tự tăng và giảm xen kẽ trong khi in. Thứ tự thay thế sẽ theo cách mà hai phần tử đầu tiên theo thứ tự tăng dần và sau đó ba phần tử tiếp theo lại có thứ tự giảm dần bốn phần tử tiếp theo theo thứ tự tăng dần.
Hãy lấy một ví dụ để hiểu rõ vấn đề hơn,
Input : {1, 4, 0, 2, 7, 9, 3}
Output : 0 1 9 7 4 2 3 Giải thích - mảng theo thứ tự tăng dần các phần tử là 0 1 2 3 4 7 9. 2 phần tử đầu là 0 1. 3 phần tử cuối là 9 7 4. 4 phần tử tiếp theo là 2 3 (có thể lấy 4 phần tử nhưng có chỉ có 2 trong mảng).
Để giải quyết vấn đề này, trước tiên chúng ta sẽ sắp xếp mảng theo thứ tự tăng dần. Bây giờ, chúng ta sẽ sử dụng hai con trỏ một để in các phần tử từ đầu và một để in phần tử cuối cùng. Chúng tôi cũng sẽ sử dụng một phần tử cờ để kiểm tra xem quá trình in được thực hiện từ đầu hay từ cuối.
Thuật toán
Step 1 : Sort elements of the array. Step 2 : Initialise left = 0 , right = n-1 , flag = 2. Step 3 : while l is less than equal to r. Do : Step 4 : If flag%2 == 0. Do : Step 4.1 : loop from i = left to left + flag. And print arr[i]. Step 4.2 : update left = i ; flag ++; Step 5 : else. Do : Step 5.1 : loop from i = right to right - flag. And print arr[i]. Step 5.2 : update right = i and flag ++. Step 6 : EXIT
Ví dụ
Bây giờ, hãy tạo một chương trình để minh họa hoạt động của thuật toán này.
#include <bits/stdc++.h>
using namespace std;
void printAlternateSeq(int arr[], int n){
sort(arr, arr + n);
int left = 0, right = n - 1, flag = 2, i;
while (left <= right) {
if (flag%2 == 0) {
for (i = left; i < left + flag && i <= right; i++)
cout<<arr[i]<<" ";
left = i;
} else {
for (i = right; i > right - flag && i >= left; i--)
cout<<arr[i]<<" ";
right = i;
}
flag++;
}
}
int main(){
int n = 6;
int arr[] = {23, 45, 78, 32, 89, 10 };
printAlternateSeq(arr, n);
return 0;
} Đầu ra
10 23 89 78 45 32