กำหนดอาร์เรย์ arr[N] ของจำนวนเต็ม N ภารกิจคือตรวจสอบว่าอาร์เรย์ที่กำหนดนั้นเป็นบิตโทนิกหรือไม่ หากอาร์เรย์ที่ระบุเป็นบิตโทนิก ให้พิมพ์ "ใช่ มันเป็นอาร์เรย์บิตโทนิก" หรือมิฉะนั้น ให้พิมพ์ "ไม่ใช่ ไม่ใช่บิตโทนิคอาเรย์"
อาร์เรย์ Bitonic คือเมื่ออาร์เรย์อยู่ในลำดับที่เพิ่มขึ้นอย่างเคร่งครัดก่อนแล้วจึงค่อยลดลงอย่างเคร่งครัด
เช่นเดียวกับอาร์เรย์นี้ arr[] ={1, 2, 3, 4, 2, -1, -5} เป็นอาร์เรย์บิตโทนิกเพราะจนถึง 4 อยู่ในลำดับที่เพิ่มขึ้นอย่างเคร่งครัดและหลังจาก 4 จะอยู่ในลำดับที่ลดลงอย่างเคร่งครัด
ป้อนข้อมูล
arr[] = {1, 3, 5, 4, 2, 0} ผลผลิต
Yes its a bitonic array
คำอธิบาย
1< 3 < 5 > 4 > 2 >0, so yes it is a bitonic array.
ป้อนข้อมูล
arr[] = {1, 2, 3, 4, 5, 0, -1, -2, 6, -4} ผลผลิต
No its not a bitonic array
แนวทางที่ใช้ด้านล่างมีดังต่อไปนี้ในการแก้ปัญหา
-
วนซ้ำทุกองค์ประกอบของอาร์เรย์และตรวจสอบว่าองค์ประกอบก่อนหน้ามีขนาดเล็กกว่าองค์ประกอบปัจจุบัน
-
เมื่อองค์ประกอบก่อนหน้าไม่เล็กกว่าตัวแบ่งองค์ประกอบปัจจุบัน
-
ตรวจสอบว่าองค์ประกอบก่อนหน้ามีขนาดใหญ่กว่าปัจจุบัน มิฉะนั้นจะคืนค่าเท็จและออก
-
หากถึงจุดสิ้นสุดของอาร์เรย์จะคืนค่าเป็นจริง
อัลกอริทึม
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 ตัวอย่าง
#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;
} ผลลัพธ์
หากรันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้ -
Yes its a bitonic array
