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

ধরুন, আমাদের একটি গাড়ি আছে এবং আমরা এটিকে এক-মাত্রিক রাস্তায় চালাচ্ছি। বর্তমানে আমরা অবস্থান =0 এবং গতি =1 সহ। আমরা এই দুটি অপারেশনের যেকোনো একটি সম্পাদন করতে পারি।

ত্বরণ:অবস্থান :=অবস্থান + গতি এবং গতি :=গতি * 2 বিপরীত গিয়ার:গতি :=−1 যখন গতি> 0 অন্যথায় গতি :=1।

আমাদের লক্ষ্যে পৌঁছানোর জন্য কমপক্ষে কতগুলি চাল প্রয়োজন তা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট টার্গেট =10 এর মত হয়, তাহলে আউটপুট হবে 7।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি অঙ্ক, খরচ, pos, neg, লক্ষ্য
লাগবে
- মোট :=খরচ + সর্বাধিক 2 *(pos − 1) এবং 2 * (neg − 1)
- যদি tot>=ans, তাহলে
  - ফেরত
- যদি লক্ষ্য 0 এর মত হয়, তাহলে
  - উত্তর :=সর্বনিম্ন উত্তর এবং মোট
  - ফেরত
- ধাপ :=(2^ডিজিট) − 1
- যদি ধাপ * 2 <|টার্গেট|, তাহলে
  - ফেরত
- dfs(ডিজিট − 1, খরচ, pos, neg, টার্গেট)
- dfs(ডিজিট − 1, খরচ + ডিজিট, pos + 1, neg, টার্গেট − ধাপ)
- dfs(অঙ্ক − 1, খরচ + অঙ্ক * 2, pos + 2, neg, লক্ষ্য − ধাপ * 2)
- dfs(অঙ্ক − 1, খরচ + অঙ্ক, pos, neg + 1, লক্ষ্য + ধাপ)
- dfs(অঙ্ক − 1, খরচ + অঙ্ক * 2, pos, neg + 2, লক্ষ্য + ধাপ * 2)
প্রধান ফাংশন থেকে, নিম্নলিখিতগুলি করুন -
উত্তর :=অসীম
হাই :=1
যখন 2^hi
- হাই :=হাই + 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))