Chương trình tìm số phép toán cho trước để đạt Target trong Python

Giả sử chúng ta có hai giá trị start và end, chúng ta phải tìm số phép toán tối thiểu cần thiết để chuyển đổi start thành end bằng cách sử dụng các phép toán:

• Giảm 1
• Nhân 2

Ví dụ, nếu đầu vào là start = 2, end = 7, thì đầu ra sẽ là 3, vì chúng ta có thể nhân 2 để được 4, rồi nhân 2 để được 8 và sau đó trừ 1 để được 7.

Để giải quyết, chúng ta thực hiện các bước sau:

• ans := 0
• Lặp vô tận:
  • nếu end <= start, trả về ans + start - end
  • ngược lại nếu end là lẻ, end := end + 1, ans := ans + 1
  • ngược lại, end := end // 2, ans := ans + 1

Ví dụ

class Solution:
    def solve(self, start, end):
        ans = 0
        while True:
            if end <= start:
                return ans + start - end
            elif end % 2:
                end += 1
                ans += 1
            else:
                end //= 2
                ans += 1

ob1 = Solution()
start = 2
end = 7
print(ob1.solve(start, end))

Input

2, 7

Output

3