Cho một mảng arr [N] gồm N số nguyên, nhiệm vụ là kiểm tra xem mảng đã cho có phải là bitonic hay không. Nếu mảng đã cho là mảng bitonic thì in "Có, nó là mảng bitonic", nếu không thì in "Không, nó không phải là mảng bitonic".
Mảng Bitonic là khi mảng có thứ tự tăng dần trước và sau đó theo thứ tự giảm dần.
Giống như mảng này arr [] ={1, 2, 3, 4, 2, -1, -5} là một mảng bitonic, vì cho đến 4 thì nó theo thứ tự tăng dần và sau 4 thì theo thứ tự giảm dần.
Đầu vào
arr[] = {1, 3, 5, 4, 2, 0} Đầu ra
Yes its a bitonic array
Giải thích
1< 3 < 5 > 4 > 2 >0, so yes it is a bitonic array.
Đầu vào
arr[] = {1, 2, 3, 4, 5, 0, -1, -2, 6, -4} Đầu ra
No its not a bitonic array
Phương pháp tiếp cận được sử dụng dưới đây như sau để giải quyết vấn đề
-
Lặp lại mọi phần tử của mảng và kiểm tra xem phần tử trước đó có nhỏ hơn phần tử hiện tại không.
-
Khi phần tử trước đó không nhỏ hơn ngắt phần tử hiện tại.
-
Kiểm tra xem phần tử trước đó có lớn hơn phần tử hiện tại hay không, nếu không, trả về false và thoát.
-
Nếu đến cuối một mảng, trả về true.
Thuật toán
Start
Step 1→ Declare array to check for bitonicity of an array
int check(int arr[], int size)
declare int i, j
Loop For i = 1 and i <size and i++
IF (arr[i] > arr[i - 1])
Continue
End
IF (arr[i] <= arr[i - 1])
break
End
IF(i == size - 1)
return 1
End
Loop For (j = i + 1 and j < size and j++
IF (arr[j] < arr[j - 1])
Continue
End
IF (arr[j] <= arr[j - 1])
break
End
End
Set i = j
IF (i != size)
return 0
End
return 1
Step 2→ In main()
Declare int arr[] = { -3, 9, 11, 20, 17, 5, 1 }
Declare int size = sizeof(arr) / sizeof(arr[0])
Do (check(arr, size) == 1) ? cout << "Yes its a bitonic array" : cout << "no its not a bitonic array"
Stop Ví dụ
#include <bits/stdc++.h>
using namespace std;
//function to check bitonic or not
int check(int arr[], int size){
int i, j;
for (i = 1; i < size; i++){
if (arr[i] > arr[i - 1])
continue;
if (arr[i] <= arr[i - 1])
break;
}
if (i == size - 1)
return 1;
for (j = i + 1; j < size; j++){
if (arr[j] < arr[j - 1])
continue;
if (arr[j] >= arr[j - 1])
break;
}
i = j;
if (i != size)
return 0;
return 1;
}
int main(){
int arr[] = { -3, 9, 11, 20, 17, 5, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
(check(arr, size) == 1) ? cout << "Yes its a bitonic array" : cout << "no its not a bitonic array";
return 0;
} Đầu ra
Nếu chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Yes its a bitonic array