এই সমস্যায়, আমাদের একটি সংখ্যা K দেওয়া হয়েছে। আমাদের কাজ হল K-এর সমান যোগফল সহ সর্বনিম্ন ফিবোনাচি পদগুলি খুঁজে বের করা .
ফিবোনাচি সিরিজ দুটি পূর্ববর্তী সংখ্যা যোগ করে পরবর্তী সংখ্যা তৈরি করে। ফিবোনাচি সিরিজ দুটি সংখ্যা থেকে শুরু হয় - F0 এবং F1। F0 এবং F1 এর প্রাথমিক মান যথাক্রমে 0, 1 বা 1, 1 নেওয়া যেতে পারে।
ফিবোনাচি সিরিজ হল 0 1 1 2 3 5 8 13
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
K = 5
আউটপুট
2
ব্যাখ্যা
The sum 5 can be made using 3 and 2.
সমাধান পদ্ধতি
ফিবোনাচি সংখ্যা ব্যবহার করে আমরা যেকোনো সংখ্যার যোগফল পেতে পারি কারণ 1 একটি ফিবোনাচি সংখ্যা। 1 n বার যোগ করলে যোগফল n হিসাবে পাওয়া যায়। আমাদের কাজ হল ফিবোনাচি সংখ্যার গণনা কম করা যা যোগফল দেয়। আমরা কয়েন পরিবর্তনের সমস্যা থেকে ভিত্তি নিয়ে সমাধান অর্জন করতে পারি যেখানে কয়েনের ফিবোনাচি সংখ্যার মান রয়েছে। প্রোগ্রামিং ভাষায়, এই সমস্যা সমাধানের কৌশলটিকে লোভনীয় পদ্ধতি বলা হয়।
প্রথমে, আমরা একটি যোগফল n এর থেকে কম বা সমান হওয়া পর্যন্ত ফিবোনাচি সংখ্যাগুলি যোগ করি। তারপর শেষ টার্ম থেকে শুরু করে আমরা n থেকে n>kth টার্ম পর্যন্ত বিয়োগ করি। এবং পাশাপাশি, পদ সংখ্যা গণনা বৃদ্ধি. বিন্দুতে যখন n
ফিবোনাচি পদ গণনা করার জন্য একটি ফাংশন তৈরি করুন।
সমস্ত ফিবোনাচি পদগুলি গণনা করুন যা n এর থেকে কম বা সমান।
পরবর্তী পদটি n-এর চেয়ে বড় হলে, এটিকে ভেক্টরে ঠেলে দেবেন না এবং ফিরে আসবেন।
ফিবোনাচি পদের ন্যূনতম সংখ্যা খুঁজে পেতে একটি ফাংশন তৈরি করুন যার সমষ্টি n এর সমান।
ফিবোনাচি পদ সংরক্ষণের জন্য একটি ভেক্টর শুরু করুন।
যোগফল n থেকে যোগফল>0 পর্যন্ত ফিবোনাচি পদ বিয়োগ করুন।
যোগফল n কে jth ফিবোনাচি পদ দ্বারা ভাগ করুন যা যোগফলকে অবদান রাখে এমন পদের সংখ্যা খুঁজে বের করুন।
আউটপুট হিসাবে প্রাপ্ত গণনা মুদ্রণ করুন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রামঅ্যালগরিদম
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void findFiboTerms(vector<int>& fiboVals, int K){
int i = 3, nextTerm;
fiboVals.push_back(0);
fiboVals.push_back(1);
fiboVals.push_back(1);
while (1) {
nextTerm = fiboVals[i - 1] + fiboVals[i - 2];
if (nextTerm > K)
return;
fiboVals.push_back(nextTerm);
i++;
}
}
int findTermForSum(int K){
vector<int> fiboVals;
findFiboTerms(fiboVals, K);
int termCount = 0, j = fiboVals.size() - 1;
while (K > 0) {
termCount += (K / fiboVals[j]);
K %= (fiboVals[j]);
j--;
}
return termCount;
}
int main(){
int K = 11;
cout<<"Minimum Fibonacci terms with sum equal to K is "<<findTermForSum(K);
return 0;
} আউটপুট
Minimum Fibonacci terms with sum equal to K is 2
