সারাসরি এলিমেন্টগুলো আলাদা হলে অ্যারে তৈরির সংখ্যা গণনা (C++)

তিনটি ভেরিয়েবল size, max_val, last_element ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হল কতগুলো ভিন্ন অ্যারে তৈরি করা যায় যাতে:

• অ্যারেটির সাইজ = size।
• এলিমেন্টগুলো ১ থেকে max_val পর্যন্ত।
• প্রথম এলিমেন্ট সবসময় ১।
• শেষ এলিমেন্ট সবসময় last_element।
• কোনো দুটি সারাসরি এলিমেন্ট একই নয়।

উদাহরণ দিয়ে বোঝা যাক

উদাহরণ ১

ইনপুট - size = 5, max_val = 3, last_element = 3

আউটপুট - সারাসরি এলিমেন্টগুলো আলাদা হলে অ্যারে তৈরির সংখ্যা: 5

ব্যাখ্যা - অ্যারেগুলো হবে:

[1, 2, 3, 1, 3], [1, 2, 3, 2, 3], [1, 2, 1, 2, 3], [1, 3, 1, 2, 3], [1, 3, 2, 1, 3]

উদাহরণ ২

ইনপুট - size = 3, max_val = 2, last_element = 2

আউটপুট - সারাসরি এলিমেন্টগুলো আলাদা হলে অ্যারে তৈরির সংখ্যা: 0

ব্যাখ্যা - ৩ এলিমেন্ট দিয়ে [1, _, 2] বানানো সম্ভব নয় কারণ মাঝপথে শুধু ১ বা ২ রাখা যায় যা সারাসরি ভিন্ন শর্ত লঙ্ঘন করবে।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

• ডাইনামিক প্রোগ্রামিং এবং কম্বিনেটরিক্স ব্যবহার করে এমন অ্যারে গণনা করা হয়।
• প্রথম এবং শেষ এলিমেন্ট ফিক্সড (১ এবং last_element)। যেকোনো সাইজের অ্যারে জন্য শুধু size-2 জন্যভর পূরণ করতে হয়।
• [1 থেকে max_val] এলিমেন্টগুলো size-2 খালি জায়গায় বসানো হবে। পথের সংখ্যা = ways(size) / (max_val - 1)।
• প্রতিটি রেঞ্জ 1 থেকে i পর্যন্ত ways হবে ways(i) = ways(size) / (max_val - 1)।
• যদি last_element = 1 হয় তবে ways = ways(size-1)।
• দ্বিতীয় শেষ এলিমেন্ট সবসময় ১ থেকে max_val-এর মধ্যে।
• যদি দ্বিতীয় শেষ এলিমেন্ট ১ না হয় তবে ways = (max_val-2)*ways(i-1)।
• যদি দ্বিতীয় শেষ এলিমেন্ট ১ হয় তবে ways = (max_val-1)*ways(i-1)।
• Ways(i) = (max_val - 2)*ways(i-2) + (max_val-2)*ways(i-1)।
• size, max_val, last_element ইনপুট নিন।
• ফাংশন diff_val(int size, int max_val, int last_element) ইনপুট নিতে এবং অ্যারে সংখ্যা রিটার্ন করে।
• প্রাথমিক কাউন্ট ০।
• অ্যারে arr[Max_N] = {0} ডিক্লেয়ার করুন। arr[0]=0, arr[1]=1।
• i=2 থেকে i
• temp_1 = (max_val - 2) * arr[i-1] এবং temp_2 = (max_val - 1) * arr[i-2]।
• arr[i] = temp_1 + temp_2।
• যদি last_element == 1 হয় তবে count = (max_val - 1) * arr[size-2]।
• অন্যথায় arr[size-1] রিটার্ন করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;
#define Max_N 109

int diff_val(int size, int max_val, int last_element) {
    int count = 0;
    int arr[Max_N] = {0};
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i < size; i++) {
        int temp_1 = (max_val - 2) * arr[i - 1];
        int temp_2 = (max_val - 1) * arr[i - 2];
        arr[i] = temp_1 + temp_2;
    }
    if (last_element == 1) {
        count = (max_val - 1) * arr[size - 2];
    } else {
        return arr[size - 1];
    }
    return count;
}

int main() {
    int size = 5;
    int max_val = 3;
    int last_element = 3;
    cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
    return 0;
}

উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:

আউটপুট

Count of arrays having consecutive element with different values are: 5