ইনপুট হিসাবে একটি ধনাত্মক সংখ্যা N দেওয়া হয়েছে। লক্ষ্য হল আমরা N কে শুধুমাত্র 1s, 3s এবং 4s এর যোগফল হিসাবে প্রকাশ করতে পারি এমন সংখ্যা খুঁজে বের করা। উদাহরণস্বরূপ, যদি N 4 হয় তবে এটিকে 1+1+1+1, 3+1, 1+3, 4 হিসাবে উপস্থাপন করা যেতে পারে তাই উপায়ের সংখ্যা 4 হবে।
আসুন উদাহরণ দিয়ে বোঝা যাক।
উদাহরণস্বরূপ
ইনপুট - N=5
আউটপুট - 1, 3 এবং 4 এর যোগফল হিসাবে N প্রকাশ করার বিভিন্ন উপায়ের সংখ্যা হল:6
ব্যাখ্যা - 5 হিসাবে উপস্থাপন করা যেতে পারে:
- 1+1+1+1+1
- 1+3+1
- 3+1+1
- 1+1+3
- 4+1
- 1+4
ইনপুট - N=6
আউটপুট - 1, 3 এবং 4 এর যোগফল হিসাবে N প্রকাশ করার বিভিন্ন উপায়ের সংখ্যা হল:9
ব্যাখ্যা - 9 হিসাবে উপস্থাপন করা যেতে পারে:
- 1+1+1+1+1+1
- 3+1+1+1
- 1+3+1+1
- 1+1+3+1
- 1+1+1+3
- 3+3
- 4+1+1
- 1+4+1
- 1+1+4
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা 1, 3 এবং 4 এর যোগফল হিসাবে N-এর সংখ্যা গণনা করার জন্য একটি গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করব। অ্যারে অ্যার[i] নিন যেখানে আমি সংখ্যাটি উপস্থাপন করে এবং arr[i] এটিকে উপস্থাপন করার উপায় হিসাবে। যোগফল হিসাবে।
বেস কেস
হবেarr[0]=0 (কোন উপায় নেই)
arr[1]=1 ( শুধুমাত্র একটি উপায় , 1 )
arr[2]=1 ( শুধুমাত্র একটি উপায়, 1+1 )
arr[3]=2 ( 1+1+1, 3 )
এখন অন্যান্য সংখ্যা 4, 5 … i ইত্যাদির উপায় থাকবে arr[i-1]+arr[i-3]+arr[i-4]।
- ইনপুট হিসাবে একটি ধনাত্মক সংখ্যা N নিন।
- ফাংশন Expres_sum(int N) N নেয় এবং N কে 1, 3 এবং 4 এর যোগফল হিসাবে প্রকাশ করার বিভিন্ন উপায়ের গণনা প্রদান করে।
- উপায়গুলির গণনা সংরক্ষণ করতে অ্যারে অ্যারে[N+1] নিন।
- বেস কেস শুরু করুন arr[0] =1, arr[1] =1, arr[2] =1 এবং arr[3] =2।
- i=4 থেকে i<=N. বাকি মানগুলির জন্য অতিক্রম করুন
- Arr[i - 1] + arr[i - 3] + arr[i - 4] এর যোগফল হিসাবে টেকওয়েস arr[i]।
- ফর লুপের শেষে ফিরে আসে 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
