একটি পজিটিভ নম্বর N ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হল N-কে কতভাবে ১, ৩ এবং ৪ এর যোগফল হিসেবে প্রকাশ করা যায়, সেটি বের করা। উদাহরণস্বরূপ, N=4 হলে: ১+১+১+১, ৩+১, ১+৩, ৪ — মোট ৪ ভাবে।
উদাহরণ দিয়ে বোঝা যাক
উদাহরণ ১
ইনপুট - N=5
আউটপুট - N কে ১, ৩, ৪ এর যোগফল হিসেবে প্রকাশ করার পদ্ধতি: ৬
ব্যাখ্যা - ৫ কে নিচেরভাবে প্রকাশ করা যায়:
- ১+১+১+১+১
- ১+৩+১
- ৩+১+১
- ১+১+৩
- ৪+১
- ১+৪
উদাহরণ ২
ইনপুট - N=6
আউটপুট - N কে ১, ৩, ৪ এর যোগফল হিসেবে প্রকাশ করার পদ্ধতি: ৯
ব্যাখ্যা - ৬ কে নিচেরভাবে প্রকাশ করা যায়:
- ১+১+১+১+১+১
- ৩+১+১+১
- ১+৩+১+১
- ১+১+৩+১
- ১+১+১+৩
- ৩+৩
- ৪+১+১
- ১+৪+১
- ১+১+৪
প্রোগ্রামে ব্যবহৃত পদ্ধতি
ডাইনামিক প্রোগ্রামিং ব্যবহার করে সমস্যাটি সমাধান করা হয়। অ্যারে arr[i] যেখানে i হলো নম্বর এবং arr[i] হলো সেটি ১, ৩, ৪ দিয়ে যোগফল হিসেবে প্রকাশ করার পদ্ধতির সংখ্যা।
বেস কেস:
arr[0]=1(খালি যোগফল)arr[1]=1(শুধু ১)arr[2]=1(শুধু ১+১)arr[3]=2(১+১+১, ৩)
অন্যান্য নম্বর ৪, ৫... i ইত্যাদির পদ্ধতি: arr[i] = arr[i-1] + arr[i-3] + arr[i-4]।
- পজিটিভ নম্বর N ইনপুট নিন।
- ফাংশন
Expres_sum(int N)N নিয়ে ফলাফল রিটার্ন করে। - অ্যারে
arr[N+1]পদ্ধতির সংখ্যা সংরক্ষণের জন্য। - বেস কেস ইনিশিয়ালাইজ করুন:
arr[0]=1, arr[1]=1, arr[2]=1, arr[3]=2। - i=4 থেকে i<=N পর্যন্ত লুপ:
arr[i] = arr[i-1] + arr[i-3] + arr[i-4]। - লুপ শেষে
arr[N]রিটার্ন করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int Expres_sum(int N) {
int arr[N + 1];
arr[0] = 1;
arr[1] = 1;
arr[2] = 1;
arr[3] = 2;
for (int i = 4; i <= N; i++) {
arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4];
}
return arr[N];
}
int main() {
int N = 5;
cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N);
return 0;
}
উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:
আউটপুট
Count of different ways to express N as the sum of 1, 3 and 4 are: 6
