पायथन में फिनिश लाइन तक पहुंचने के लिए चालों की संख्या का पता लगाने का कार्यक्रम

मान लीजिए, हमारे पास एक कार है और हम उसे एक-आयामी सड़क पर चला रहे हैं। वर्तमान में हम स्थिति =0 पर हैं और गति =1 के साथ। हम इन दोनों में से कोई भी ऑपरेशन कर सकते हैं।

• त्वरण:स्थिति:=स्थिति + गति और गति:=गति * 2 रिवर्स गियर:गति:=-1 जब गति> 0 अन्यथा गति:=1.

हमें कम से कम लक्ष्य तक पहुँचने के लिए आवश्यक चालों की संख्या ज्ञात करनी होगी।

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

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

• फ़ंक्शन को परिभाषित करें dfs() । यह अंक, लागत, स्थिति, नकारात्मक, लक्ष्य लेगा

  • कुल:=लागत + अधिकतम 2 *(स्थिति -1) और 2 * (नकारात्मक -1)

  • अगर टोट>=उत्तर, तो

    • वापसी

  • यदि लक्ष्य 0 के समान है, तो

    • उत्तर :=न्यूनतम उत्तर और योग

    • वापसी

  • चरण :=(2^अंक) - 1

  • यदि चरण * 2 <|लक्ष्य|, तो

    • वापसी

  • dfs(अंक -1, लागत, स्थिति, नकारात्मक, लक्ष्य)

  • dfs(अंक -1, लागत + अंक, स्थिति + 1, नकारात्मक, लक्ष्य - चरण)

  • dfs(अंक -1, लागत + अंक * 2, स्थिति + 2, नकारात्मक, लक्ष्य - चरण * 2)

  • dfs(अंक -1, लागत + अंक, स्थिति, नकारात्मक + 1, लक्ष्य + चरण)

  • dfs(अंक -1, लागत + अंक * 2, स्थिति, नकारात्मक + 2, लक्ष्य + चरण * 2)

• मुख्य कार्य से, निम्न कार्य करें -

• उत्तर:=अनंत

• नमस्ते :=1

• जबकि 2^हाय <लक्ष्य, करो

  • हाय :=हाय + 1

• dfs (हाय, 0, 0, 0, लक्ष्य)

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, target):
      self.ans = int(1e9)
      hi = 1
      while (1 << hi) < target:
         hi += 1
      self.dfs(hi, 0, 0, 0, target)
      return self.ans
   def dfs(self, digit, cost, pos, neg, target):
      tot = cost + max(2 * (pos − 1), 2 * neg − 1)
      if tot >= self.ans:
         return
      if target == 0:
         self.ans = min(self.ans, tot)
         return
      step = (1 << digit) − 1
      if step * 2 < abs(target):
         return
      self.dfs(digit − 1, cost, pos, neg, target)
      self.dfs(digit − 1, cost + digit, pos + 1, neg, target − step)
      self.dfs(digit − 1, cost + digit * 2, pos + 2, neg, target − step * 2)
      self.dfs(digit − 1, cost + digit, pos, neg + 1, target + step)
      self.dfs(digit − 1, cost + digit * 2, pos, neg + 2, target + step * 2)
ob = Solution()
print(ob.solve(10))

इनपुट

10

आउटपुट

7