নির্দিষ্ট ওজন X এবং কমপক্ষে একটি M ওজনের এজ থাকা পথের সংখ্যা গণনা (C++)

আমাদের কাছে একটি ট্রি আছে যেনান্তহীন লেভেল 가질 수 있습니다। একটি ভেরিয়েবল child একটি নোডের চাইল্ড সংখ্যা সংরক্ষণ করে, weight পথের সাথে যুক্ত ওজন সংরক্ষণ করে এবং path পথ সংরক্ষণ করে। কাজ হল এমন পথের সংখ্যা গণনা করা যাদের মোট ওজন ঠিক X এবং সেট중에 কমপক্ষে একটি এজের ওজন M।

উদাহরণ

ইনপুট - int child = 4, weight = 4, path = 4;

আউটপুট - নির্দিষ্ট ওজন X এবং কমপক্ষে একটি M ওজনের এজ থাকা পথের সংখ্যা: 1

ব্যাখ্যা - নোডটির ৪টি চাইল্ড আছে যারা ৪টি পথ দিয়ে সংযুক্ত এবং প্রতিটি পথের ওজন ৪। সুতরাং শুধু একটি পথই ওজন ৪ দিয়ে তৈরি হতে পারে (১-৪), তাই কাউন্ট ১।

ইনপুট - int child = 3, weight = 2, path = 4;

আউটপুট - নির্দিষ্ট ওজন X এবং কমপক্ষে একটি M ওজনের এজ থাকা পথের সংখ্যা: 4

ব্যাখ্যা - নোডটির ৩টি চাইল্ড আছে যারা ৪টি পথ দিয়ে সংযুক্ত এবং প্রতিটি পথের ওজন ২। সম্ভব পথগুলো: ১-১, ১-২, ২-১, ২-১ (মোট ৪টি)।

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

মোট চাইল্ড, পথ এবং প্রতিটি পথের ওजन ইনপুট নিন (child, weight, path)।
নির্দিষ্ট সাইজের একটি অ্যারে ডিক্লেয়ার করুন।
লুপ চালিয়ে অ্যারের সব এলিমেন্ট -1 দিয়ে ইনিশিয়ালাইজ করুন।
total_weight() ফাংশন কল করুন আর্গুমেন্ট হিসেবে path, 0, weight, child এবং arr পাস করে।
ফাংশনের ভিতরে:
- একটি টেম্পোরারি ভেরিয়েবল count ডিক্লেয়ার করুন ফলাফল সংরক্ষণের জন্য।
- যদি path < 0 হয় তবে 0 রিটার্ন করুন।
- যদি path == 0 হয় তবে i রিটার্ন করুন।
- যদি arr[path][i] != -1 হয় তবে arr[path][i] রিটার্ন করুন।
- j=1 থেকে child পর্যন্ত লুপ চালান।
- যদি j == weight হয় তবে count += total_weight(path - j, 1, weight, child, arr)।
- অন্যথায় count += total_weight(path - j, i, weight, child, arr)।
- arr[path][i] = count সেট করুন।
arr[path][i] রিটার্ন করুন।
ফলাফল প্রিন্ট করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;
#define size 4
#define col 4

int total_weight(int path, int i, int weight, int child, int arr[size + 1][col]) {
    int count = 0;
    if (path < 0) {
        return 0;
    }
    if (path == 0) {
        return i;
    }
    if (arr[path][i] != -1) {
        return arr[path][i];
    }
    for (int j = 1; j <= child; j++) {
        if (j == weight) {
            count += total_weight(path - j, 1, weight, child, arr);
        } else {
            count += total_weight(path - j, i, weight, child, arr);
        }
    }
    arr[path][i] = count;
    return arr[path][i];
}

int main() {
    int child = 4, weight = 4, path = 4;
    int arr[size + 1][col];
    for (int i = 0; i <= size; i++) {
        for (int j = 0; j < 2; j++) {
            arr[i][j] = -1;
        }
    }
    cout << "Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: " << total_weight(path, 0, weight, child, arr);
    return 0;
}

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

আউটপুট

Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1