এই আর্টিকেলে আমরা C++-এ হাইপোটেনাস এবং এরিয়ার সম্ভাব্য পেয়ার সংখ্যা বের করব যা সমকোণ ত্রিভুজ তৈরি করতে পারে।
আমাদের বের করতে হবে হাইপোটেনাস এবং এরিয়ার (H, A) সকল সম্ভাব্য পেয়ার সংখ্যা যাতে H হাইপোটেনাস এবং A এরিয়া হিসেবে একটি সমকোণ ত্রিভুজ তৈরি হয়।
এই উদাহরণে −
x = সমকোণ ত্রিভুজের বেস
y = সমকোণ ত্রিভুজের উচ্চতা
H = সমকোণ ত্রিভুজের হাইপোটেনাস
আমরা জানি সমকোণ ত্রিভুজের এরিয়া,
A = ( x * y ) / 2
অথবা
4 * A² = ( x * y )² … (১)
আরও জানি
x² + y² = H² … (২)
(১) ও (২) সমাধান করলে
4 * A² = x² ( H² - x² )
x²-এ দ্বিঘাত সমীকরণ সমাধান করলে এবং ডিসক্রিমিন্যান্ট D >= 0 (x থাকতে হলে) রাখলে পাই, H² >= 4 * A (সমকোণ ত্রিভুজ থাকার শর্ত)
উদাহরণ:
ইনপুট : array H[ ] = { 3, 6, 8 } : A[ ] = { 2, 31, 12 }
আউটপুট : 4
ব্যাখ্যা : হাইপোটেনাস এবং এরিয়ার সম্ভাব্য পেয়ার (H, A) হল (3, 2), (6, 2), (8, 2) এবং (8, 12)।
ইনপুট : array H[ ] = { 2, 5, 9 } : A[ ] = { 3, 11, 7 }
আউটপুট : 4
ব্যাখ্যা : সম্ভাব্য পেয়ার (H, A) হল (5, 3), (9, 3), (9, 11) এবং (9, 7)।
সমাধানের পদ্ধতি
এখন আমরা প্রদত্ত কাজ করার জন্য দুটি ভিন্ন পদ্ধতি ব্যবহার করব:
ব্রুট ফোর্স পদ্ধতি
এই সহজ পদ্ধতিতে আমরা হাইপোটেনাস এবং এরিয়ার (H, A) সকল সম্ভাব্য পেয়ার বের করি, চেক করি সেগুলো শর্ত H² >= 4 * A সন্তুষ্ট করে কিনা, এবং প্রতিটি সন্তুষ্ট পেয়ারের জন্য কাউন্ট বাড়াই।
উদাহরণ
#include <iostream> using namespace std; int main(){ int H[ ] = { 2,5,9}; // হাইপোটেনাস অ্যারে int s1 = sizeof(H)/sizeof(H[0]); int A[ ] = { 3, 11, 7};// এরিয়া অ্যারে int s2 = sizeof(A)/sizeof(A[0]); int count = 0;// কাউন্ট ০ দিয়ে ইনিশিয়ালাইজ // সকল সম্ভাব্য পেয়ার বের করা for (int i = 0; i < s1; i++) { for (int j = 0; j < s2; j++) { // বর্তমান পেয়ার শর্ত সন্তুষ্ট করে কিনা চেক if (H[i] * H[i] >= 4 * A[j]){ count++; } } } cout << "Number of possible pairs of ( H, A ): " << count ; return 0; }
আউটপুট
Number of possible pairs of ( H, A ): 4
ব্যাখ্যা
এই কোডে আমরা কাউন্ট ভেরিয়েবল ব্যবহার করি শর্ত সন্তুষ্ট করে পেয়ার সংখ্যা রাখতে এবং নেস্টেড লুপ ব্যবহার করি (H, A) পেয়ার জেনারেট করতে। এই কোডের সময় জটিলতা O(n²) যা একটি দক্ষ পদ্ধতি নয়। চলুন দ্বিতীয় পদ্ধতি বুঝি।
দক্ষ পদ্ধতি (Efficient approach)
এই পদ্ধতিতে আমরা প্রথমে দুটি অ্যারে সর্ট করি আসেন্ডিং অর্ডারে, তারপর যেকোনো হাইপোটেনাস দৈর্ঘ্যের জন্য H² > 4 * A চেক করে সর্বোচ্চ এরিয়া বের করি।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main (){ int H[] = { 2, 5, 9 }; int s1 = sizeof (H) / sizeof (H[0]); int A[] = { 3, 11, 7 }; int s2 = sizeof (A) / sizeof (A[0]); int count = 0; // দুটি অ্যারে সর্ট করা sort (H, H + s1); sort (A, A + s2); int temp = -1; for (int i = 0; i < s1; i++){ // প্রতিটি হাইপোটেনাস দৈর্ঘ্যের জন্য // বাইনারি সার্চ অ্যাপ্লাই int flag1 = 0; int flag2 = s2 - 1; while (flag1 <= flag2){ int mid = flag1 + (flag2 - flag1) / 2; if ((H[i] * H[i]) >= (4 * A[mid])){ temp = mid; flag1 = mid + 1; } else{ flag2 = mid - 1; } } if (temp != -1){// কোনো সম্ভাব্য এরিয়া পাওয়া গেলে count += temp + 1; } } cout << "Number of possible pairs of (H, A): " << count; return 0; }
আউটপুট
Number of possible pairs of ( H, A ): 4
উপরোক্ত কোডের ব্যাখ্যা
এই কোডে আমরা প্রথমে দুটি অ্যারে আসেন্ডিং অর্ডারে সর্ট করি, এবং তারপর প্রতিটি সম্ভাব্য দৈর্ঘ্যের জন্য বাইনারি সার্চ ব্যবহার করে সর্বোচ্চ এরিয়া বের করি।
মান লইয়া যাক সর্বোচ্চ এরিয়া A[ ] অ্যারেতে ইনডেক্স ৩-এ পাওয়া গেলে, তখন ইনডেক্স ৩-এর চেয়ে ছোট সকল এরিয়াও শর্ত সন্তুষ্ট করবে, তাই আমরা ৩টি সম্ভাব্য পেয়ার বানাতে পারব।
উপসংহার
এই আর্টিকেলে আমরা সমকোণ ত্রিভুজ বানানোর জন্য হাইপোটেনাস এবং এরিয়া পেয়ার সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা ব্রুট ফোর্স পদ্ধতি (সময় জটিলতা O(n²)) এবং দক্ষ পদ্ধতি (সময় জটিলতা O(s1 log(s2))) লাগিয়েছি। আশা করি এই আর্টিকেলটি সহায়ক হবে।
