24點演算法

• 2022 年 5 月 31 日
• 筆記
• 演算法

隨機取四個數字，用加、減、乘、除、括弧5種運算，計算結果等於二十四。

窮舉法

import itertools
 
# 括弧的組合只存在如下五種表達式結構 卡特蘭數
formats = ['(({0[0]}{1[0]}{0[1]}){1[1]}{0[2]}){1[2]}{0[3]}',
           '({0[0]}{1[0]}({0[1]}{1[1]}{0[2]})){1[2]}{0[3]}',
           '({0[0]}{1[0]}{0[1]}){1[1]}({0[2]}{1[2]}{0[3]})',
           '{0[0]}{1[0]}(({0[1]}{1[1]}{0[2]}){1[2]}{0[3]})',
           '{0[0]}{1[0]}({0[1]}{1[1]}({0[2]}{1[2]}{0[3]}))']

# 可選的操作序列 64種：4*4*4
def getOplist(ops):
    op_list = [ops[i]+ops[j]+ops[p] for i in range(4) for j in range(4) for p in range(4)]
    return op_list
    
opt_list = getOplist('+-/*')

    
def main_all():
    cnt = 0
    no_ans = 0
    # 可重複組合數 13C4 = 715
    for nums in itertools.combinations_with_replacement([1,2,3,4,5,6,7,8,9,10], 4):
        flag = False
        cnt += 1  
        ans = "no ans"
        
        for num in itertools.permutations(nums, 4): # 4個數的排列數4!=24
            for op in opt_list: # 操作序列 64種：4*4*4
                for f in formats: #括弧的組合 5種
                    try:
                        expr = f.format(num, op)
                        n = eval(expr)
                        # 這裡需要注意小數點的截斷
                        if 23.99 < n and n < 24.01:
                            flag = True
                            ans = expr
                            break
                    except ZeroDivisionError:
                        continue
                if flag:
                    break
            if flag:
                    break
          
        if not flag:
            no_ans += 1
        print((cnt,nums,ans))
    print(("all",cnt,"no ans",no_ans,"ans",cnt-no_ans))

main_all()                    

分析：窮舉一次的遍歷次數：\(4!*4^3*5=7680\)，每次都是計算整個表達式，成本高。

下面的程式碼，讀取輸入，輸出表達式

def main_input():
    while True:
        try:
            nums, flag = input().split(), False
            for num in itertools.permutations(nums, 4):
                for op in opt_list:
                    for f in formats:
                        try:
                            expr = f.format(num, op)
                            n = eval(expr)
                            if 23.99 < n and n < 24.01:
                                flag = True
                                print(expr)
                                break
                        except ZeroDivisionError:
                            continue
                    if flag:
                        break
                if flag:
                        break
            if flag:
                print('true')
            else:
                print('false')
        except:
            break

main_input()

二元計算

把多元運算轉化為兩元運算。

先從四個數中取出兩個數進行運算，然後再從運算結果和其它兩個數組成的三個數中取出兩個數進行運算，最終得到兩個數，再次進行運算，得到最終結果。

在求表達式的過程中，最難處理的就是對括弧的處理，而這種思路很好的避免了對括弧的處理。

import itertools

def is24(nums):
    if len(nums) == 1:
        return 23.99 < nums[0] and nums[0] < 24.01

    for i in itertools.permutations(nums, 2):
        arr = nums.copy()
        arr.remove(i[0])
        arr.remove(i[1])
                 
        if is24(arr + [i[0] + i[1]]) or is24(arr + [i[0] - i[1]]) or is24(arr + [i[0] * i[1]]) or (i[1] != 0 and is24(arr + [i[0] / i[1]])):
            return True

    return False
 
def main_all():
    cards = 4
    cnt = 0
    ans = 0
    for num in itertools.combinations_with_replacement([1,2,3,4,5,6,7,8,9,10], cards):
        nums = list(num)
        if cards>=5 and all(data==nums[0] for data in nums):
            continue
        cnt += 1  
        if is24(nums):
            ans += 1
        else:
            print((nums,"no ans"))

    print(("all",cnt,"no ans",cnt-ans,"ans",ans))

main_all()    

分析：窮舉一次的遍歷次數：\(C_4^2*4*C_3^2*4*C_2^2*4=1152\)，為窮舉法的15%。

缺陷是，需要額外的代價輸出計算表達式。

統計

選取4張牌，最大數字為10，組合數為715，其中149個組合無解；如果最大數字為13，組合數為1820，其中458個組合無解。

選取5張牌，最大數字為10，組合數為1992，其中37個組合無解；如果最大數字為13，組合數為6175，其中80個組合無解。

refer

24點遊戲里有哪些非常難算的題目？

//www.zhihu.com/question/264095014/answer/2503005870

24點遊戲演算法

//blog.csdn.net/hyblogs/article/details/106676393

所有1362個可解組合的所有獨立解

//www.4shu.net/solutions/allsolutions/