ধরুন আমাদের একটি সংখ্যা n আছে। তাই বিবেচনা করুন রান্নাঘরে কমলা আছে এবং আমরা এই নিয়মগুলি বজায় রেখে প্রতিদিন কিছু কমলা খাই:1. একক কমলা খান। 2. যদি n জোড় হয়, তাহলে n/2 কমলা খান। 3. n 3 দ্বারা বিভাজ্য হলে 2*(n/3) কমলা খেতে পারেন। আমরা প্রতিদিন একটি মাত্র বিকল্প নির্বাচন করতে পারি। কমলা খাওয়ার জন্য আমাদের ন্যূনতম দিন খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট n =10 এর মত হয়, তাহলে আউটপুট হবে 4 কারণ
-
১ম দিনে ১টি কমলা খান, ১০ - ১ =৯।
-
২য় দিনে ৬টি কমলা খান, ৯ - ২*(৯/৩) =৯ - ৬ =৩৷
-
৩য় দিনে ২টি কমলা খান, ৩ - ২*(৩/৩) =৩ - ২ =১।
-
৪র্থ দিনে শেষ কমলা 1 - 1 =0.
খান
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন fun() সংজ্ঞায়িত করুন। এটি n
লাগবে৷ -
যদি n মেমোতে থাকে, তাহলে
-
রিটার্ন মেমো[এন]
-
-
যদি n<=2, তাহলে
-
ফেরত n
-
-
memo[n]:=1 + সর্বনিম্ন (n mod 2+ fun(n/2 এর ভাগফল) এবং (n mod 3 + fun(n/3 এর ভাগফল)
-
রিটার্ন মেমো[এন]
-
মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
-
মেমো:=একটি নতুন মানচিত্র
-
ফিরে মজা(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]
আউটপুট
4
