এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা n দেওয়া আছে। আমাদের কাজ হল এটি কত পদ্ধতিতে দুটি বা অধিক ধনাত্মক পূর্ণসংখ্যার যোগফল হিসেবে প্রকাশ করা যায় তা খুঁজে বের করা।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝি,
ইনপুট
N = 4
আউটপুট
5
ব্যাখ্যা
৪ নিম্নলিখিত পদ্ধতিতে যোগফল হিসেবে লেখা যায়, 4, 3+1, 2+2, 2+1+1, 1+1+1+1
এই সমস্যাটি সমাধান করতে, আমরা অয়লারের রিকারেন্স সূত্র ব্যবহার করব। একটি সংখ্যা n-এর জন্য মোট পদ্ধতির সংখ্যা p(n) которой দ্বারা,
Σ^∞n=0 p(n)x^n = Π^∞k=1 (1/(1-x^k ))
এই সূত্র ব্যবহার করে, আমরা p(n)-এর জন্য সূত্র উদ্ভাবন করব, p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + … + (-1)^(k-1)((k(3k-1))/2)
আমাদের সমাধানের বাস্তবায়ন চিত্রিত করার প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h> using namespace std; long long postiveSum(int n){ vector<long long> p(n + 1, 0); p[0] = 1; for (int i = 1; i <= n; ++i) { int k = 1; while ((k * (3 * k - 1)) / 2 <= i) { p[i] += (k % 2 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2]; if (k > 0) k *= -1; else k = 1 - k; } } return p[n]; } int main(){ int N = 12; cout<<"যে পদ্ধতিতে "<<N<<" দুটি বা অধিক ধনাত্মক সংখ্যার যোগফল হিসেবে লেখা যায় "<<postiveSum(N); return 0; }
আউটপুট
যে পদ্ধতিতে ১২ দুটি বা অধিক ধনাত্মক সংখ্যার যোগফল হিসেবে লেখা যায় 77
