একটি উপাদানকে পিক এলিমেন্ট বলা হয় যখন সেটি তার চারপাশের চারটি প্রতিবেশীর চেয়ে বড় বা সমান হয়। প্রতিবেশী উপাদানগুলো হলো উপরের, নিচের, বাম এবং ডান দিকের উপাদান। এই সমস্যায় আমরা কিছু সীমাবদ্ধতা বিবেচনা করব। ডায়াগোনাল উপাদানগুলোকে প্রতিবেশী হিসেবে বিবেচনা করা হবে না। একটি ম্যাট্রিক্সে একাধিক পিক এলিমেন্ট থাকতে পারে, এবং পিক এলিমেন্টটি আপক perusahaan ম্যাট্রিক্সের সবচেয়ে বড় উপাদান হতে হবে না।
ইনপুট এবং আউটপুট
ইনপুট: ভিন্ন সংখ্যার একটি ম্যাট্রিক্স। 10 8 10 10 14 13 12 11 15 9 11 21 16 17 19 20 আউটপুট: ম্যাট্রিক্সের পিক এলিমেন্ট। এখানে পিক এলিমেন্ট: 21
এলগরিদম
findMaxMid(rows, mid, max)
ইনপুট: ম্যাট্রিক্সের সারি সংখ্যা, মিড কলাম, একটি আউটপুট আর্গুমেন্ট হিসেবে ম্যাক্স এলিমেন্ট।
আউটপুট: ম্যাক্স আইটেম এবং ম্যাক্স এলিমেন্টের ইনডেক্স আপডেট করুন।
শুরু
maxIndex := 0
ম্যাট্রিক্সের সব সারি r এর জন্য, করুন
যদি max < matrix[i, mid], তবে
max = matrix[i, mid]
maxIndex := r
শেষ লুপ
return maxIndex
শেষ
findPeakElement(rows, columns, mid)
ইনপুট: ম্যাট্রিক্সের সারি এবং কলাম, এবং মিড সারি অবস্থান।
আউটপুট: ম্যাট্রিক্সের পিক এলিমেন্ট।
শুরু
maxMid := 0
maxMidIndex := findMaxMid(rows, mid, maxMid)
যদি mid প্রথম বা শেষ কলাম হয়, তবে
return maxMid
যদি maxMid >= মিড কলামের পূর্ববর্তী এবং পরবর্তী সারির আইটেম, তবে
return maxMid
যদি maxMid তার বাম উপাদানের চেয়ে কম হয়, তবে
res := findPeakElement(rows, columns, mid - mid/2)
return res
যদি maxMid তার ডান উপাদানের চেয়ে কম হয়, তবে
res := findPeakElement(rows, columns, mid + mid/2)
return res
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#define M 4
#define N 4
using namespace std;
int arr[M][N] = {
{10, 8, 10, 10},
{14, 13, 12, 11},
{15, 9, 11, 21},
{16, 17, 19, 20}
};
int findMaxMid(int rows, int mid, int &max) {
int maxIndex = 0;
for (int i = 0; i < rows; i++) {
// মিড কলামে ম্যাক্স এলিমেন্ট খুঁজে বের করুন
if (max < arr[i][mid]) {
max = arr[i][mid];
maxIndex = i;
}
}
return maxIndex;
}
int findPeakElement(int rows, int columns, int mid) {
int maxMid = 0;
int maxMidIndex = findMaxMid(rows, mid, maxMid);
if (mid == 0 || mid == columns-1) // প্রথম এবং শেষ কলামের জন্য, maxMid হলো ম্যাক্সিমাম
return maxMid;
// যদি maxMid পিক হয়
if (maxMid >= arr[maxMidIndex][mid-1] && maxMid >= arr[maxMidIndex][mid+1])
return maxMid;
if (maxMid < arr[maxMidIndex][mid-1]) // যদি maxMid তার বাম এলিমেন্টের চেয়ে কম হয়
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
