আমাদেরকে একটি গাছ দেওয়া হয়েছে যার অন্তহীন স্তর থাকতে পারে, একটি পরিবর্তনশীল শিশু যা একটি নোডে থাকা শিশুদের সংখ্যা সংরক্ষণ করবে, একটি পরিবর্তনশীল ওজন যা পাথের সাথে সম্পর্কিত ওজন সংরক্ষণ করবে এবং একটি পরিবর্তনশীল পাথ যা পথ এবং কাজ সংরক্ষণ করবে। পাথের সংখ্যা গণনা করতে যার ওজন X এর সমান এবং প্রদত্ত ওজনের সাথে কমপক্ষে একটি প্রান্ত থাকতে হবে।
উদাহরণস্বরূপ
ইনপুট - int চাইল্ড =4, ওজন =4, পথ =4;
আউটপুট - পাথের সংখ্যার সংখ্যা যার ওজন ঠিক X এবং ওজন M এর অন্তত এক প্রান্ত রয়েছে:1
ব্যাখ্যা - যেমন আমাদের নোডের সাথে দেওয়া হয়েছে 4টি পথের সাথে সংযুক্ত 4টি শিশু রয়েছে এবং পাথের সাথে 4টি ওজন যুক্ত রয়েছে। সুতরাং, আমরা দেখতে পাচ্ছি যে 4 হিসাবে ওজন সহ শুধুমাত্র একটি পথ হতে পারে অর্থাৎ 1 - 4 তাই গণনা হল 1৷
ইনপুট - int চাইল্ড =3, ওজন =2, পথ =4;
আউটপুট - পাথের সংখ্যার সংখ্যা যার ওজন ঠিক X এবং ওজন M এর অন্তত এক প্রান্ত রয়েছে:4
ব্যাখ্যা - যেমন আমাদের নোডের সাথে দেওয়া হয়েছে 4টি পথের সাথে 3টি শিশু যুক্ত এবং পাথের সাথে 2টির ওজন যুক্ত রয়েছে। সুতরাং, আমরা দেখতে পাচ্ছি যে ওজন সহ 2 হিসাবে চারটি পথ থাকতে পারে যেমন 1-1, 1 - 2, 2-1 এবং 2-1 তাই, গণনা হল 4৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
- ভেরিয়েবলের চাইল্ড, ওজন এবং পাথে যথাক্রমে প্রতিটি পাথের সাথে যুক্ত শিশুদের মোট সংখ্যা, পথ এবং ওজন ইনপুট করুন।
- প্রদত্ত আকারের একটি অ্যারে ঘোষণা করুন।
- একটি অ্যারের আকার পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে, j থেকে 0 থেকে 2 কম j পর্যন্ত FOR আর একটি লুপ শুরু করুন এবং তারপর arr[i][j] কে -1 হিসাবে সেট করুন।
- এখন ফাংশনের আর্গুমেন্ট হিসাবে পাথ, 0, ওজন, চাইল্ড এবং আরআর পাস করে ফাংশনটিকে total_weight() বলুন।
- ফাংশনের ভিতরে,
- ফলাফল সংরক্ষণ করার জন্য একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন।
- IF পাথ 0 এর কম চেক করুন তারপর 0 ফেরত দিন
- IF পাথ সমান 0 চেক করুন তারপর i ফেরত দিন
- চেক করুন যদি arr[path][i] 1 এর সমান না হয় তারপর arr[path][i] ফেরত দিন
- স্টার্ট লুপ ফর j থেকে 1 পর্যন্ত বাচ্চা পর্যন্ত। লুপের ভিতরে, একটি আর্গুমেন্ট হিসাবে ফাংশনে path-j, 1, ওজন, চাইল্ড এবং arr পাস করে ফাংশন total_weight() ফাংশনে রিকার্সিভ কল হিসাবে সেট গণনার তুলনায় IF j সমান ওজন পরীক্ষা করুন।
- অন্যথায়, একটি আর্গুমেন্ট হিসাবে ফাংশনে path-j, i, weight, child এবং arr পাস করে ফাংশন total_weight() ফাংশনে রিকার্সিভ কল হিসাবে গণনা সেট করুন।
- গণনা হিসাবে arr[path][i] সেট করুন এবং
- রিটার্ন arr[পথ][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);
} যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেআউটপুট
Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1
