पायथन में एन संतरे खाने के लिए न्यूनतम दिनों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक संख्या n है। तो विचार करें कि रसोई में संतरे नहीं हैं और हम इन नियमों को बनाए रखते हुए हर दिन इनमें से कुछ संतरे खाते हैं:1. एक संतरा खाएं। 2. अगर n सम है, तो n/2 संतरा खाएं। 3. यदि n, 3 से विभाज्य है तो 2*(n/3) संतरा खा सकते हैं। हम प्रत्येक दिन केवल एक विकल्प का चयन कर सकते हैं। हमें संतरे खाने के लिए न्यूनतम दिनों की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट n =10 जैसा है, तो आउटपुट 4 होगा क्योंकि

• पहले दिन 1 संतरा खाएं, 10 - 1 =9.

• दूसरे दिन 6 संतरा खाएं, 9 - 2*(9/3) =9 - 6 =3.

• तीसरे दिन 2 संतरा खाएं, 3 - 2*(3/3) =3 - 2 =1.

• चौथे दिन आखिरी संतरा 1 - 1 =0 खाएं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन fun() को परिभाषित करें। इसमें n

  . लगेगा

• अगर n मेमो में है, तो

  • वापसी ज्ञापन[n]

• अगर n<=2, तो

  • वापसी n

• मेमो [एन]:=1 + न्यूनतम (एन मॉड 2+ फन (एन/2 का भागफल)) और (एन मॉड 3 + फन (एन/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