এই সমস্যাতে, আমাদের একটি সংখ্যা K দেওয়া আছে। আমাদের কাজ হল K-র সমান যোগফল দিতে পারা ন্যূনতম ফিবোনাচি টার্মের সংখ্যা বের করা।
ফিবোনাচি সিরিজ দুটি পূর্ববর্তী সংখ্যা যোগ করে পরবর্তী সংখ্যা তৈরি করে। ফিবোনাচি সিরিজ দুটি সংখ্যা F0 এবং F1 থেকে শুরু হয়। F0 এবং F1-এর প্রাথমিক মান ০, ১ বা ১, ১ নেওয়া যেতে পারে।
ফিবোনাচি সিরিজ: ০ ১ ১ ২ ৩ ৫ ৮ ১৩
উদাহরণ দেখি:
ইনপুট
K = 5
আউটপুট
2
ব্যাখ্যা
যোগফল ৫, ৩ এবং ২ দিয়ে তৈরি করা যায়।
সমাধানের পদ্ধতি
ফিবোনাচি সংখ্যা ব্যবহার করে যেকোনো সংখ্যার যোগফল পাওয়া যায়, কারণ ১ একটি ফিবোনাচি সংখ্যা। ১ কে n বার যোগ করলে যোগফল n হয়। আমাদের কাজ হল যোগফল দিতে পারা ফিবোনাচি সংখ্যার সংখ্যা ন্যূনতম করা। আমরা কয়েন চেঞ্জ সমস্যা থেকে প্রেরণা নিয়ে গ্রিডি (Greedy) পদ্ধতিতে এটা সমাধান করতে পারি, যেখানে কয়েনগুলো ফিবোনাচি সংখ্যা।
প্রথমে n-এর চেয়ে ছোট বা সমান ফিবোনাচি সংখ্যা যোগ করি। তারপর শেষ টার্ম থেকে শুরু করে সেটি n থেকে বিয়োগ করি যতক্ষণ না n, kth টার্ম থেকে বড় হয়। পাশাপাশি টার্মের সংখ্যা কাউন্ট বেড়াতে থাকি। যখন n, kth টার্ম থেকে ছোট হয়, তখন তার পাশের ছোট বা সমান ফিবোনাচি টার্মে যাওয়া এবং কাউন্ট প্রিন্ট করা।
অ্যালগরিদম
ফিবোনাচি টার্ম ক্যালকুলেট করার একটি ফাংশন তৈরি করুন।
n-এর চেয়ে ছোট বা সমান সকল ফিবোনাচি টার্ম ক্যালকুলেট করুন।
যদি পরবর্তী টার্ম n থেকে বড় হয়, তবে সেটি ভেক্টরে পুশ করবেন না এবং রিটার্ন করুন।
n-এর সমান যোগফল দিতে পারা ন্যূনতম ফিবোনাচি টার্ম বের করার একটি ফাংশন তৈরি করুন।
ফিবোনাচি টার্ম স্টোর করার একটি ভেক্টর ইনিশিয়ালাইজ করুন।
যোগফল n ০ হওয়া পর্যন্ত ফিবোনাচি টার্ম বিয়োগ করুন।
যোগফল 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
