দেওয়া সমস্যায়, আমাদের একটি অ্যারেতে থাকা সব উপাদানের র্যাঙ্ক নির্ণয় করতে হবে, যেখানে সবচেয়ে ছোট সংখ্যাটির র্যাঙ্ক সবচেয়ে ছোট এবং সবচেয়ে বড় সংখ্যাটির র্যাঙ্ক সবচেয়ে বড় হবে। একই সংখ্যা একাধিকবার থাকলে তাদের র্যাঙ্ক পরিবর্তন করতে হবে। উদাহরণস্বরূপ:
Input : 20 30 10 Output : 2.0 3.0 1.0 Input : 10 12 15 12 10 25 12 Output : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0 এখানে 10-এর র্যাঙ্ক 1.5 কারণ অ্যারেতে দুটি 10 আছে। যদি তাদের আলাদা র্যাঙ্ক ১ ও ২ ধরা হয়, তবে গড় ১.৫ হয়। Input : 1, 2, 5, 2, 1, 60, 3 Output : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের জন্য দুটি ভিন্ন পদ্ধতি আছে।
ব্রুট ফোর্স পদ্ধতি
এই পদ্ধতিতে, আমরা লুপ চালিয়ে প্রতিটি উপাদান বেছে নিব এবং তার র্যাঙ্ক নির্ণয় করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main() { int arr[] = {1, 2, 5, 2, 1, 25, 2}; // দেওয়া অ্যারে int n = sizeof(arr) / sizeof(arr[0]); // অ্যারের আকার float rank[n] = {0}; // র্যাঙ্ক সংরক্ষণের অ্যারে for (int i = 0; i < n; i++) { int r = 1; // arr[i] চেয়ে ছোট উপাদানların সংখ্যা int s = 1; // arr[i] এর সমান উপাদানların সংখ্যা for (int j = 0; j < n; j++) { if (j != i && arr[j] < arr[i]) r += 1; if (j != i && arr[j] == arr[i]) s += 1; } rank[i] = r + (float)(s - 1) / (float) 2; // সূত্র ব্যবহার করে র্যাঙ্ক নির্ণয় } for (int i = 0; i < n; i++) // র্যাঙ্ক আউটপুট করুন cout << rank[i] << ' '; return 0; }
আউটপুট
1.5 4 6 4 1.5 7 4
এই প্রোগ্রামের সময় জটিলতা O(N*N), যেখানে N হল অ্যারের আকার। এটি উচ্চ কনস্ট্রেইন্টের জন্য উপযুক্ত নয়, তাই আমরা দক্ষ পদ্ধতি ব্যবহার করব।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা একটি নতুন অ্যারে लेकर সেটিকে সর্ট করব। সর্ট হওয়ায় একই র্যাঙ্কের উপাদানগুলো একসাথে থাকবে। সেগুলোকে স্বাভাবিকভাবে র্যাঙ্ক দিয়ে তারপর নির্দিষ্ট উপাদানের র্যাঙ্ক ক্যালকুলেট করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main() { int arr[] = {1, 2, 5, 2, 1, 60, 3}; // দেওয়া অ্যারে int n = sizeof(arr) / sizeof(arr[0]); // অ্যারের আকার float rank[n] = {0}; // র্যাঙ্ক অ্যারে int old[n]; for(int i = 0; i < n; i++) old[i] = arr[i]; sort(arr, arr+n); // অ্যারে সর্ট করুন int prev = arr[0]; int r = 1; // র্যাঙ্ক int s = 0; // ফ্রিকোয়েন্সি int tot = 0; // একটি উপাদান যা র্যাঙ্ক ধারণ করবে map<int, float> rrank; for (int i = 0; i < n; i++) { if(prev == arr[i]) { s++; tot += r; } else { float now = 0; now = (float)tot/s; // র্যাঙ্কগুলো সমান ভাগ করুন rrank[prev] = now; prev = arr[i]; tot = r; s = 1; } r++; } rrank[arr[n-1]] = (float)tot/s; for (int i = 0; i < n; i++) // র্যাঙ্ক আউটপুট করুন cout << rrank[old[i]] << " "; return 0; }
আউটপুট
1.5 3.5 6 3.5 1.5 7 5
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা আমাদের অ্যারেটিকে সর্ট করি, এবং তারপর প্রতিটি উপাদানকে শুরু থেকে র্যাঙ্ক দিই (র্যাঙ্ক ১ থেকে শুরু)। এখন, যদি পূর্বের উপাদান বর্তমান উপাদানের সমান হয়, তবে আমরা s বাড়াই এবং র্যাঙ্কের যোগফল tot-এ যোগ করি। যখন উপাদান পরিবর্তন হয়, তবে আমরা পূর্বের উপাদানদের র্যাঙ্ক সমান ভাগ করি, s এবং tot রিফ্রেশ করি, এবং কোড চালিয়ে যাই।
উপসংহার
এই আর্টিকেলে, আমরা একটি অ্যারেতে সব উপাদানের র্যাঙ্ক নির্ণয় করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ ও দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়।
