Chương trình tìm số phép toán tối thiểu để biến đổi số này thành số khác trong Python

Cho số start và end (start < end). Tìm số phép toán tối thiểu để biến start thành end bằng các phép: cộng 1 hoặc nhân 2.

Ví dụ, start = 5, end = 11, đầu ra 2 (nhân 2 -> 10, cộng 1 -> 11).

Các bước giải quyết (đi ngược từ end):

• ct := 0.
• Trong khi end/2 >= start:
  • Nếu end % 2 == 1: end -= 1, end //= 2, ct += 2.
  • Ngược lại: end //= 2, ct += 1.
• ct += (end - start).
• Trả về ct.

Ví dụ minh họa

class Solution:
    def solve(self, start, end):
        ct = 0
        while end / 2 >= start:
            if end % 2 == 1:
                end -= 1
                end //= 2
                ct += 2
            else:
                end //= 2
                ct += 1
        ct += (end - start)
        return ct

ob = Solution()
print(ob.solve(5, 11))

Đầu vào

5,11

Đầu ra

2