โปรแกรมหาจำนวนการแก้ไขที่ต้องทำเพื่อแก้ไขสมการใน Python

สมมติว่าเรามีสตริง s ซึ่งแทนสมการของรูปแบบ x+y=z เราต้องหาจำนวนหลักขั้นต่ำที่เราต้องบวกเข้าไปใน s เพื่อให้สมการเป็นจริง

ดังนั้น หากอินพุตเป็น s ='2+6=7' ผลลัพธ์จะเป็น 2

เราเปลี่ยนสมการเป็น "21+6=27" ได้โดยใส่ "1" กับ "2" ดังนั้นจำนวนการแก้ไขทั้งหมดที่ต้องการคือ 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• แบ่ง s ออกเป็นส่วนๆ ตามอักขระ "+" วางส่วนซ้ายเป็นส่วน A และส่วนขวาพัก

• แบ่งส่วนที่เหลือออกเป็นส่วน ๆ ตามอักขระ "=" ใส่ส่วนซ้ายเป็น B และส่วนขวาเป็น C

• return dp(ขนาด A - 1, ขนาด B - 1, ขนาด C - 1, 0)

• กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j, k, พกพา

• ถ้าฉัน <=-1 และ j <=-1 และ k <=-1 แล้ว

  • คืนค่า 0 หากการพกพาเหมือนกับ 0 มิฉะนั้น 1

• สุดท้าย1 :=(A[i]) ถ้า i>=0 มิฉะนั้น 0

• สุดท้าย2 :=(B[j]) ถ้า j>=0 มิฉะนั้น 0

• สุดท้าย3 :=(C[k]) ถ้า k>=0 มิฉะนั้น 0

• prefix1 :=(A[จากดัชนี 0 ถึง i + 1]) ถ้า i>=0 มิฉะนั้น 0

• prefix2 :=(B[จากดัชนี 0 ถึง j + 1]) ถ้า j>=0 มิฉะนั้น 0

• คำนำหน้า3 :=(C[จากดัชนี 0 ถึง k + 1]) ถ้า k>=0 มิฉะนั้น 0

• ถ้าฉัน <=-1 และ j <=-1 แล้ว

  • rhs :=prefix3 - พกพา

  • ถ้า rhs <=0 แล้ว

    • กลับ |rhs|

  • ถ้าฉันเหมือนกับ -1 หรือ j เหมือนกับ -1 แล้ว

    • ส่งคืนขนาดของสตริง rhs

  • มิฉะนั้น

    • คืนค่าเท็จ

  • ถ้า k <=-1 แล้ว

    • ขนาดส่งคืนของ str(prefix1 + prefix2 + carry)

  • ตอบ :=อนันต์

  • carry2, lhs :=return quotient และ หารเศษที่เหลือ (carry + last1 + last2) ด้วย 10

  • ถ้า lhs เหมือนกับ 3 สุดท้ายแล้ว

    • ตอบ :=dp(i - 1, j - 1, k - 1, carry2)

  • req :=last3 - carry - last2

  • extra_zeros :=สูงสุด 0, -1 - i

  • carry2 :=1 if req <0 มิฉะนั้น 0

  • ans :=ขั้นต่ำของ ans, 1 + extra_zeros + dp(สูงสุด -1, i, j - 1, k - 1, carry2)

  • req :=last3 - carry - last1

  • extra_zeros :=สูงสุด 0, -1 - j

  • carry2 :=1 if req <0 มิฉะนั้น 0

  • ans =ค่าต่ำสุดของ (ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))

  • carry2, lhs :=ส่งคืนผลหารและเศษที่เหลือหาร (last1 + last2 + carry) ด้วย 10

  • ans :=ขั้นต่ำของ ans, 1 + dp(i - 1, j - 1, k, carry2)

  • กลับมาอีกครั้ง

• จากวิธีหลัก ส่งคืน dp(ขนาด 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