C++ ব্যবহার করে যোগফল হিসেবে N প্রকাশ করতে ন্যূনতম সংখ্যক প্যালিনড্রোম প্রয়োজন।

সমস্যা বিবৃতি

একটি সংখ্যা দেওয়া হলে, আমাদেরকে তাদের যোগফল হিসাবে N প্রকাশ করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক প্যালিনড্রোম খুঁজে বের করতে হবে

যদি N =15 হয় তাহলে 2টি প্যালিন্ড্রোম প্রয়োজন যেমন 8 এবং 7৷

অ্যালগরিদম

<পূর্ব>1. একটি সাজানো ফ্যাশন2-এ N পর্যন্ত সমস্ত প্যালিনড্রোম তৈরি করুন। ক্ষুদ্রতম উপসেটের আকার খুঁজুন যেমন তার যোগফল N

উদাহরণ

#include #include #include #include Namespace std;vector> table;int createPalindrome(int input, bool isOdd){ int n =ইনপুট; int palindrome =ইনপুট; if (isOdd) n /=10; যখন (n> 0) { palindrome =palindrome * 10 + (n % 10); n /=10; } রিটার্ন প্যালিনড্রোম;} ভেক্টরজেনারেট প্যালিনড্রোম(int n){ ভেক্টর প্যালিনড্রোম; int সংখ্যা; জন্য (int j =0; j <2; j++) { int i =1; যখন ((সংখ্যা =createPalindrome(i++, j)) <=n) palindromes.push_back(সংখ্যা); } রিটার্ন প্যালিনড্রোমস;} লং লং মিন সাবসেট সাইজ(ভেক্টর&vec, int i, int j, int n){ if (n ==0) রিটার্ন 0; যদি (i> j || vec[i]> n) INT_MAX ফেরত দেয়; যদি (টেবিল[i][n]) টেবিল [i][n] ফেরত দেয়; টেবিল[i][n] =min(1 + minSubsetSize(vec, i + 1, j, n - vec[i]), minSubsetSize(vec, i + 1, j, n)); রিটার্ন টেবিল[i][n];}int প্রয়োজনীয়Palindromes(int n){ vector palindromes =GeneratePalindromes(n); sort(palindromes.begin(), palindromes.end()); টেবিল =ভেক্টর<ভেক্টর<লং লং>>(palindromes.size(), ভেক্টর(n + 1, 0)); রিটার্ন minSubsetSize(palindromes, 0, palindromes.size() - 1, n);}int main(){ int n =15; cout <<"সর্বনিম্ন প্রয়োজনীয় প্যালিনড্রোমস =" <<প্রয়োজনীয় প্যালিনড্রোমস(n) < আউটপুট
 
 আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
 তৈরি করে সর্বনিম্ন প্রয়োজনীয় প্যালিনড্রোম =2