একটি আইটেমকে একটি শীর্ষ উপাদান বলা হয় যখন এটি সেই উপাদানটির চারটি প্রতিবেশীর চেয়ে বড় বা সমান হয়৷ প্রতিবেশী উপাদান হল উপরের, নীচে, বাম এবং ডান উপাদান। এই সমস্যার জন্য, আমরা কিছু সীমা বিবেচনা করব। তির্যক উপাদান প্রতিবেশী উপাদান হিসাবে চেক করা হয় না. একটি ম্যাট্রিক্সে একাধিক পিক এলিমেন্ট থাকতে পারে এবং পিক এলিমেন্টটি ম্যাট্রিক্সের সবচেয়ে বড় উপাদান নয়।
ইনপুট এবং আউটপুট
Input: A matrix of different numbers. 10 8 10 10 14 13 12 11 15 9 11 11 15 9 11 21 16 17 19 20 Output: The peak element of the matrix. Here the peak element is: 21
অ্যালগরিদম
findMaxMid(সারি, মধ্য, সর্বোচ্চ)
ইনপুট: ম্যাট্রিক্সের সারি সংখ্যা, মধ্য সারি, আউটপুট আর্গুমেন্ট হিসাবে একটি সর্বোচ্চ উপাদান।
আউটপুট: সর্বাধিক উপাদানের সর্বাধিক আইটেম এবং সূচক আপডেট করুন।
Begin maxIndex := 0 for all rows r in the matrix, do if max < matrix[i, mid], then max = matrix[i, mid], maxIndex := r done return maxIndex End
findPeakElement(সারি, কলাম, মধ্য)
ইনপুট - ম্যাট্রিক্সের সারি এবং কলাম, এবং মধ্য সারির স্থান।
আউটপুট - ম্যাট্রিক্সের শীর্ষ উপাদান।
Begin maxMid := 0 maxMidIndex := findMaxMid(rows, mid, maxMid) if mid is first or last column, then return maxMid if maxMid>= item of previous and next row for mid column, then return maxMid if maxMid is less than its left element, then res := findPeakElement(rows, columns, mid – mid/2) return res if maxMid is less than its right element, then res := findPeakElement(rows, columns, mid + mid/2) return res End
উদাহরণ
#include<iostream>
#define M 4
#define N 4
using namespace std;
intarr[M][N] = {
{10, 8, 10, 10},
{14, 13, 12, 11},
{15, 9, 11, 21},
{16, 17, 19, 20}
};
intfindMaxMid(int rows, int mid, int&max) {
intmaxIndex = 0;
for (int i = 0; i < rows; i++) { //find max element in the mid column
if (max <arr[i][mid]) {
max = arr[i][mid];
maxIndex = i;
}
}
return maxIndex;
}
intfindPeakElement(int rows, int columns, int mid) {
intmaxMid = 0;
intmaxMidIndex = findMaxMid(rows, mid, maxMid);
if (mid == 0 || mid == columns-1) //for first and last column, the maxMid is maximum
return maxMid;
// If maxMid is also peak
if (maxMid>= arr[maxMidIndex][mid-1] &&maxMid>= arr[maxMidIndex][mid+1])
return maxMid;
if (maxMid<arr[maxMidIndex][mid-1]) // If maxMid is less than its left element
return findPeakElement(rows, columns, mid - mid/2);
return findPeakElement(rows, columns, mid+mid/2);
}
int main() {
int row = 4, col = 4;
cout<< "The peak element is: "<<findPeakElement(row, col, col/2);
} আউটপুট
The peak element is: 21
