পাইথনে N সংখ্যক কমলা খাওয়ার ন্যূনতম দিন বের করার প্রোগ্রাম

মনে করুন একটি সংখ্যা n আছে। রান্নাঘরে nটি কমলা আছে এবং আমরা প্রতিদিন কিছু কমলা খাই এই নিয়ম মেনে: ১. একট কমলা খাও। ২. যদি n জোড় হয়, তবে n/2 টি কমলা খাও। ৩. যদি n ৩ দিয়ে বিভাজ্য হয়, তবে 2*(n/3) টি কমলা খাও। প্রতিদিন শুধু একটি অপশন বেছে নিতে পারি। nটি কমলা খাওয়ার ন্যূনতম দিন বের করতে হবে।

যেমন, ইনপুট n = 10 হলে, আউটপুট হবে ৪ কারণ:

দিন ১: ১টি কমলা খাই, ১০ - ১ = ৯।
দিন ২: ৬টি কমলা খাই, ৯ - 2*(9/3) = ৯ - ৬ = ৩।
দিন ৩: ২টি কমলা খাই, ৩ - 2*(3/3) = ৩ - ২ = ১।
দিন ৪: শেষ ১টি কমলা খাই, ১ - ১ = ০।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

fun() ফাংশন ডিফাইন করুন। এটি n প্যারামিটার নেবে
- যদি n memo-এ থাকে, তবে memo[n] রিটার্ন করুন
- যদি n <= 2 হয়, তবে n রিটার্ন করুন
- memo[n] := 1 + min(n%2 + fun(n//2), n%3 + fun(n//3))
- memo[n] রিটার্ন করুন
মেইন মেথড থেকে:
memo := একটি খালি ম্যাপ
fun(n) রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

def solve(n):    def fun(n):       if n in memo:          return memo[n]       if n<=2:          return n       memo[n]=1+min(n%2+fun(n//2),n%3+fun(n//3))       return memo[n]    memo={}    return fun(n) n = 12 print(solve(n))

ইনপুট

7, [5,1,4,3]