পাইথনে n কে ফিবোনাচ্চি সংখ্যা গুলোর যোগফলে প্রকাশ করার ন্যূনতম সংখ্যা বের করা

সমস্যা বিবরণ

একটি সংখ্যা n দেওয়া আছে। n কে ফিবোনাচ্চি সংখ্যা গুলোর যোগফলে প্রকাশ করার জন্য ন্যূনতম কতগুলো ফিবোনাচ্চি সংখ্যা লাগবে তা বের করতে হবে। প্রতিটি ফিবোনাচ্চি সংখ্যা একবারের বেশি ব্যবহার করা যাবে না (Zeckendorf's Theorem)।

উদাহরণ

Input:  n = 20
Output: 3
ব্যাখ্যা: 20 = 13 + 5 + 2 (৩টি ফিবোনাচ্চি সংখ্যা)

গণিতগত পটভূমি: Zeckendorf's Theorem

প্রতিটি পজিটিভ ইন্টিজারকে নন-কনsekutিভ ফিবোনাচ্চি সংখ্যা গুলোর যোগফলে অনন্যভাবে প্রকাশ করা যায়। লালচী (Greedy) পদ্ধতিতে সবচেয়ে বড় ফিবোনাচ্চি সংখ্যা বেছে নিলে ন্যূনতম কাউন্ট মেলে।

অ্যালগরিদম

1. n এর চেয়ে ছোট বা সমান সব ফিবোনাচ্চি সংখ্যা জেনারেট করুন
2. সবচেয়ে বড় ফিবোনাচ্চি সংখ্যা থেকে শুরু করে:
   • যদি ফিবোনাচ্চি ≤ বর্তমান n, তবে বিয়োগ করুন এবং কাউন্ট বাড়ান
   • n = 0 হলে থামুন

পাইথন কোড

class Solution:
    def solve(self, n):
        res = 0
        fibo = [1, 1]
        
        # n পর্যন্ত ফিবোনাচ্চি জেনারেট
        while fibo[-1] <= n:
            fibo.append(fibo[-1] + fibo[-2])
        
        # লালচী পদ্ধতি: সবচেয়ে বড় থেকে বিয়োগ
        while n:
            while fibo[-1] > n:
                fibo.pop()
            n -= fibo[-1]
            res += 1
        
        return res

ob = Solution()
n = 20
print(ob.solve(n))  # 3

ড্রাই রান (n=20)

Fibonacci: [1, 1, 2, 3, 5, 8, 13, 21]
n=20: 13 বিয়োগ → n=7, count=1
n=7:  5 বিয়োগ  → n=2, count=2
n=2:  2 বিয়োগ  → n=0, count=3
Result: 3

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(log n) — ফিবোনাচ্চি সংখ্যা ~φ^k বড় হয়
• স্থান জটিলতা: O(log n) — ফিবোনাচ্চি লিস্ট

উপসংহার

• Zeckendorf's Theorem গ্যারান্টি দেয় লালচী পদ্ধতি অপ্টিমাল
• ফিবোনাচ্চি সংখ্যা এক্সপোনেনশিয়ালি বড় হয়, তাই লুপ কম.Iteration
• কয়েন চেঞ্জ মেকিং প্রোব্লেমের অনুরূপ কিন্তু কয়েন সেট = ফিবোনাচ্চি