কম্পিউটার টিউটোরিয়াল

C++ দিয়ে তিনটি রেখার পয়েন্ট থেকে বने ত্রিভুজের সংখ্যা বের করা

আমাদের তিনটি রেখায় কিছু পয়েন্ট দেওয়া আছে। এখন আমাদের বের করতে হবে এই পয়েন্টগুলো থেকে কতগুলো ত্রিভুজ তৈরি করা সম্ভব। উদাহরণ −

ইনপুট: m = 3, n = 4, k = 5 আউটপুট: 205
ইনপুট: m = 2, n = 2, k = 1 আউটপুট: 10

এই সমস্যাটি সমাধানের জন্য কৌম্বিনেট্রিক্স (Combinatorics) প্রয়োগ করে একটি সূত্র তৈরি করব।

সমাধানের পদ্ধতি

এই পদ্ধতিতে, আমরা বর্তমান পরিস্থিতিতে কৌম্বিনেট্রিক্স প্রয়োগ করে একটি সূত্র তৈরি করব যা আমাদের ফলাফল দেবে।

উপরোক্ত পদ্ধতির C++ কোড

নিচে দিয়ে गयी C++ সিনট্যাক্স ব্যবহার করে এই সমস্যা সমাধান করা যায় −

উদাহরণ
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; long long fact(long long n) {     if(n <= 1) return 1;     return ((n % MOD) * (fact(n-1) % MOD)) % MOD; } long long comb(int n, int r) {     return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD); } int main() {     int n = 3;     int m = 4;     int r = 5;     long long linen = comb(n, 3); // n-র ৩ দিয়ে কম্বিনেশন     long long linem = comb(m, 3); // m-র ৩ দিয়ে কম্বিনেশন     long long liner = comb(r, 3); // r-র ৩ দিয়ে কম্বিনেশন     long long answer = comb(n + m + r, 3); // সব পয়েন্টের ৩ দিয়ে কম্বিনেশন     answer -= (linen + linem + liner);     cout << answer << "\n";     return 0; }
আউটপুট
205
কোডের ব্যাখ্যা

এই পদ্ধতিতে, আমরা সব পয়েন্ট (n+m+r) নিয়ে ৩-টির কম্বিনেশন বের করি, অর্থাৎ comb(n+m+r, ৩)। যেহেতু তিনটি পয়েন্ট ত্রিভুজ বানাবে না যদি তারা কলিনিয়ার (collinear) হয়, তাই আমরা প্রতিটি রেখার পয়েন্টগুলোর মধ্যে ৩-টির কম্বিনেশন বের করি (linen, linem, liner) এবং সেগুলোর যোগফল মোট কম্বিনেশন থেকে বিয়োগ করি। বাকি ফলাফলটিই আমাদের উত্তর।

উপসংহার

এই আর্টিকেলে আলোচনা করা হয়েছে তিনটি রেখার পয়েন্ট থেকে কতগুলো ত্রিভুজ তৈরি করা যায়, কৌম্বিনেট্রিক্স প্রয়োগ করে। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।

  1. C++ দিয়ে একটি স্ট্রিংয়ের সাবস্ট্রিং-এর সংখ্যা বের করা

  2. C++-এ ট্রেন স্টপেজ স্টেশন সংখ্যা বের করুন

  3. C++-এ সেটে রিফ্লেক্সিভ রিলেশন সংখ্যা বের করুন

  4. C++-এ দিয়ে गये পয়েন্ট থেকে সম্ভাব্য কোয়াড্রিল্যাটারেল সংখ্যা বের করুন