Chương trình kiểm tra có thể tạo ra 24 bằng cách chèn toán tử vào dãy số bằng Python

Cho danh sách 4 số (mỗi số 1-9) theo thứ tự cố định. Chèn các toán tử +, -, *, / (chia nguyên) và dấu ngoặc giữa các số. Kiểm tra có thể tạo ra giá trị 24 hay không.

Ví dụ: nums = [5, 3, 6, 8, 7] → True vì (5*3) - 6 + (8+7) = 24.

Giải thuật

• Đệ quy chia để trị: hàm recur(arr) trả về tập hợp tất cả giá trị có thể tạo ra từ dãy con arr.
• Với mỗi điểm cắt i, tính tập giá trị tiền tố pre và hậu tố suf, kết hợp chúng bằng 4 phép toán.
• Cơ sở: nếu arr chỉ có 1 phần tử, trả về chính phần tử đó.
• Kiểm tra xem 24 có trong tập kết quả của dãy đầy đủ hay không.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        def recur(arr):
            answer = []
            for i in range(len(arr) - 1):
                pre, suf = recur(arr[:i+1]), recur(arr[i+1:])
                for k in pre:
                    for j in suf:
                        answer.append(k + j)
                        answer.append(k - j)
                        answer.append(k * j)
                        if j != 0:
                            answer.append(k // j)
            if len(answer) == 0 and len(arr) == 1:
                answer.append(arr[0])
            return answer
        return 24 in recur(nums)

ob = Solution()
nums = [5, 3, 6, 8, 7]
print(ob.solve(nums))

Đầu vào

[5, 3, 6, 8, 7]

Đầu ra

True