পাইথনে একটি সমীকরণ ঠিক করার জন্য করা সংশোধনের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে যা x+y=z ফর্মের একটি সমীকরণ উপস্থাপন করে। আমাদের ন্যূনতম সংখ্যার সংখ্যা খুঁজে বের করতে হবে যা আমাদের s যোগ করতে হবে যাতে সমীকরণটি সত্য হয়।

সুতরাং, ইনপুট যদি s ='2+6=7' এর মত হয়, তাহলে আউটপুট হবে 2।

আমরা "1" এবং "2" সন্নিবেশ করে সমীকরণটিকে "21+6=27" এ পরিণত করতে পারি। তাই মোট সংশোধনের প্রয়োজন 2।

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

• s কে "+" অক্ষরের উপর ভিত্তি করে ভাগে ভাগ করুন, বাম অংশকে A এ এবং ডান অংশটিকে বিশ্রামে রাখুন

• বিশ্রামকে "=" অক্ষরের উপর ভিত্তি করে ভাগে ভাগ করুন, বাম অংশকে B এবং ডান অংশকে C

  তে রাখুন

• রিটার্ন ডিপি(A - 1 এর আকার, B - 1 এর আকার, C - 1, 0 এর আকার)

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি i, j, k, বহন করবে

• যদি i <=-1 এবং j <=-1 এবং k <=-1, তাহলে

  • বহন 0 এর মত হলে 0 ফেরত দিন অন্যথায় 1

• last1 :=(A[i]) যদি i>=0 অন্যথায় 0

• last2 :=(B[j]) যদি j>=0 অন্যথায় 0

• last3 :=(C[k]) যদি k>=0 অন্যথায় 0

• উপসর্গ1 :=(A[সূচী 0 থেকে i + 1]) যদি i>=0 অন্যথায় 0

• prefix2 :=(B[সূচী ০ থেকে j + 1]) যদি j>=0 অন্যথায় 0

• উপসর্গ3 :=(C[সূচক 0 থেকে k + 1]) যদি k>=0 অন্যথায় 0

• যদি i <=-1 এবং j <=-1, তাহলে

  • rhs :=উপসর্গ3 - বহন

  • যদি rhs <=0, তাহলে

    • ফেরত |rhs|

  • যদি আমি -1 এর মত হয় বা j -1 এর মত হয়, তাহলে

    • স্ট্রিং rhs

      এর রিটার্ন সাইজ

  • অন্যথায়,

    • রিটার্ন ফলস

  • যদি k <=-1, তাহলে

    • str(prefix1 + prefix2 + বহন)

      এর রিটার্ন সাইজ

  • উত্তর :=অসীম

  • বহন 2, lhs :=ফেরত ভাগফল এবং অবশিষ্ট ভাগ ( বহন + শেষ 1 + শেষ 2 ) 10

  • যদি lhs শেষ3 এর মত হয়, তাহলে

    • উত্তর :=dp(i - 1, j - 1, k - 1, বহন2)

  • req :=last3 - বহন - last2

  • extra_zeros :=সর্বাধিক 0, -1 - i

  • বহন2 :=1 যদি req <0 অন্যথায় 0

  • উত্তর :=সর্বনিম্ন উত্তর, 1 + অতিরিক্ত_শূন্য + dp (সর্বোচ্চ -1, i, j - 1, k - 1, বহন2)

  • req :=last3 - বহন - last1

  • extra_zeros :=সর্বাধিক 0, -1 - j

  • বহন2 :=1 যদি req <0 অন্যথায় 0

  • ans =সর্বনিম্ন (উত্তর, 1 + অতিরিক্ত_শূন্য + dp(i - 1, সর্বোচ্চ(-1, j), k - 1, বহন2))

  • বহন2, lhs :=ফেরত ভাগফল এবং অবশিষ্ট ভাগ (শেষ 1 + শেষ2 + বহন) 10

  • উত্তর :=সর্বনিম্ন উত্তর, 1 + dp(i - 1, j - 1, k, বহন2)

  • উত্তর ফেরত দিন

• মূল পদ্ধতি থেকে রিটার্ন ডিপি (A – 1 এর আকার, B - 1 এর আকার, C - 1, 0 এর আকার)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, s):
      A, rest = s.split("+")
      B, C = rest.split("=")
      def dp(i, j, k, carry):
         if i <= -1 and j <= -1 and k <= -1:
            return 0 if carry == 0 else 1
         last1 = int(A[i]) if i >= 0 else 0
         last2 = int(B[j]) if j >= 0 else 0
         last3 = int(C[k]) if k >= 0 else 0
         prefix1 = int(A[: i + 1]) if i >= 0 else 0
         prefix2 = int(B[: j + 1]) if j >= 0 else 0
         prefix3 = int(C[: k + 1]) if k >= 0 else 0
         if i <= -1 and j <= -1:
            rhs = prefix3 - carry
            if rhs <= 0:
               return abs(rhs)
            if i == -1 or j == -1:
               return len(str(rhs))
            else:
               assert False
         if k <= -1:
            return len(str(prefix1 + prefix2 + carry))
         ans = float("inf")
         carry2, lhs = divmod(carry + last1 + last2, 10)
         if lhs == last3:
            ans = dp(i - 1, j - 1, k - 1, carry2)
         req = last3 - carry - last2
         extra_zeros = max(0, -1 - i)
         carry2 = 1 if req < 0 else 0
         ans = min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2))
         req = last3 - carry - last1
         extra_zeros = max(0, -1 - j)
         carry2 = 1 if req < 0 else 0
         ans = min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
         carry2, lhs = divmod(last1 + last2 + carry, 10)
         ans = min(ans, 1 + dp(i - 1, j - 1, k, carry2))
         return ans
      return dp(len(A) - 1, len(B) - 1, len(C) - 1, 0)

ob = Solution()
print (ob.solve('2+6=7'))

ইনপুট

'2+6=7'

আউটপুট

2