Hey! Hope you are having a great day so far!
今天想和大家討論的是一道我從這學期cs的期末考試得到靈感的題：Get 24 Poker Game，說到 Get 24 Poker Game，也就是我們通常說的湊24點，大家可能都比較熟悉，但是因為這個游戲有很多變種，我們還是來簡單說一下游戲的規則，老規矩，上Wikipedia：
The 24 Game is an arithmetical card game in which the objective is to find a way to manipulate four integers so that the end result is 24.
簡單來說，這個游戲需要玩家快速用隨機抽出的四張牌上的整數通過常見的加減乘除計算來湊出24點來取得勝利（一定要用全4張，不可以棄牌），不同于我們通常玩的斗地主，釣魚等等撲克游戲，湊24點更考驗玩家的數學反應能力（less fun but somewhat interesting:)），在這里稍稍跑一下題，因為可能會有人好奇，為什么恰恰選了24這個數字，其實答案很直白，因為這個數字最容易被湊出來：24是擁有八個除數的最小整數(1, 2, 3, 4, 6, 8, 12, and 24），使用這個數字不僅僅把游戲變得更加簡單（畢竟可能沒有人想花一個小時在用撲克牌湊數上），還把游戲作廢（目標數字湊不出來）的幾率降到最小，
好了，希望大家對這個卡牌游戲已經有一些基礎的認知了，但是在正式開始編這個游戲之前，我想先從這學期cs期末考試的一道題入手：
It is possible to combine the numbers 1, 5, 6, 7 with arithemtic operations to get 21 as follows: 6/(1-5/7).
Part I:
Write a function that takes in a list of three numbers and a target number, and returns a string that contains an expression that uses all the numbers in the list once, and results in the target. Assume that the task is possible without using parentheses.
For example, get_target_noparens([3, 1, 2], 7) can return "2*3+1" or "1+2*3" (either output would be fine).
Part II:
Now, write the function get_target which returns a string that contains an expression that uses all the numbers in the list once, and results in the target. The expression can contain parentheses. Assume that the task is possible.
For example, get_target([1, 5, 6, 7], 21) can return "6/(1-5/7)" , this will return all permutation of the list of number.
這道題有兩部分，第一部分的大意是寫出一個函式，讓其能夠以串列的形式接收三個數字并試圖用加減乘除的方法來湊出目標點數（注意，這里不包括括號操作），第二部分相對于前一部分難度更高一點，要求寫出函式，讓其能夠接受任意數量的數字，并可通過對其進行加減乘除（這里包括括號）的操作來湊出目標點數，另外，在做這道題的時候不需要考慮備選數字沒有辦法湊出目標點數的情況，
我們不難看出，第二題其實和我們想要做出的卡牌游戲的解法基本上是完全重合，甚至更加簡單，只需把函式的目標數字設為24，而且限制前面串列的數字數量為4，就能夠做出這個游戲的解法，但第一題給考生了一個基礎的思路，也就是說第一題給第二題做了很好的鋪墊，能夠讓人更快的找到正確的邏輯，完成解題程序，所以只要解決這兩道題，我們就可以很流暢的找出湊24點的最終解法（多做一道賺一道啊！），
話不多說，我們開始！（完整代碼在文末）
通過讀題，我們可以發現第一題和第二題最主要的差別在以下兩點上：
- 第一題只需要考慮三個數字，兩個符號的排列組合，也就是說在改變運算子號時，我們只需考慮4選1，或者4選2的情況，而第二題卻需要完全不同的思路，要在不確定總數字量的情況下，在每兩個數字間考慮到所有排列可能，
- 第二題需要考慮到一個，或者多個括號的演算法，在這種情況下，我們不能直接計算結果，因為沒有辦法確定括號的個數和位置，
記住以上兩點：）如果我們能在做第一小題時找到關于第二小題的啟發，會事半功倍的！
第一小題我們可以從運算式子的結構入手，正常寫出的話，一個有三個運算元字的式子會長這個樣子：
$1+2+3$
結構一目了然，三個數字，兩個運算子號，如果想生成所有排列組合的可能性的話，我們可以用嵌套for回圈很容易的用代碼實作如下：
1 def get_all_comb(num_list): 2 '''find all arithmatic combination using the given 3 numbers''' 3 4 for op_1 in ['+','-','*','/']: # 用第一個for loop來考慮所有第一個位置的運算子號的可能性 5 for op_2 in ['+','-','*','/']: # 用第二個for loop來考慮所有第二個位置的運算子號的可能性 6 comb = str(num_list[0])+op_1+str(num_list[1])+op_2+str(num_list[2]) # 組裝運算式 7 print(comb) # 列印運算式
這段代碼的輸出結果為 ‘1+2+3’，‘1+2-3’，‘1+2*3’...等等十六個不重復的運算式，但是我們還要考慮到所有數字的排列組合的情況，注意在以上的例子里，所有運算的數字是沒有變化的，但數字位置的變化在多數情況下會對運算結果造成影響，也就是說在我們改變運算子號的同時，我們也要考慮到所有數字的排列情況（這里指permutation），
同樣，我們也可以用以上相似的嵌套回圈邏輯來用代碼實作：
1 def get_num_comb(num_list): 2 '''find all combination possibilities of the given 3 numbers''' 3 4 all_comb = [] # 準備收集所有排列組合 5 for i in range(3): # 三個嵌套for回圈分別對應在num_list里的序數 6 for j in range(3): 7 for k in range(3): 8 if i != j and i != k and j != k: # 確定沒有重復元素 9 print([num_list[i], num_list[j], num_list[k]]) #列印最終結果
但是我們可以通過以上兩段代碼發現，在這里用for loop來分別實作符號和數字的排列組合雖然是可行的（同理我們也可以用類似的for loop結構來），但卻無法延伸到這道題的局限外，也就是說，這個思路僅限于這道題的Part 1，如果要做第二部分的話，我們需要重新寫這部分的函式（這也是這兩道題的第一個主要差別：數字數量的不確定性），
為了使第一部分的解法可以延伸到第二題，我們需要換個思路，很自然的，為了解決數字數量的不確定問題，我們不能夠再使用for loop這種需要定量條件的方法，而是使用遞回（recursion），
以上我們討論到的兩個問題，運算子號以及運算元字的排列組合，可以被分別寫作兩個遞回函式，比起普通回圈，遞回函式的結構更加復雜，為了減少碼代碼時出現不必要的概念不清的錯誤，我們可以針對每個遞回畫出樹形圖來作結構分析，
我們先來看運算子號的遞回規律，如果我們有三個需要考慮的運算位置的話，樹形圖便如下圖：
通過觀察，我們可以看到第一層有4個分支，第二層有16個，第三層有64個，不難看出，這個遞回規律的復雜度是隨著遞回的深度而以二次增長，所以可以用Big-Oh Notation表達成 O(4^n)，n為運算子號的個數，（關于運算復雜度和常見algorithm會有后續文章跟進，在這里不做過多解釋）
根據以上基礎結構，我們可以用代碼來寫出生成運算子號的遞回函式，如下：
1 def generate_comb_op(n): 2 '''find all combination of Arithmetic operators with n possible spaces for operators''' 3 # 建立base case 4 if n==0: 5 return [] # 當n為0時不回傳任何運算子號 6 elif n ==1: 7 return [['+'],['-'],['*'],['/']] # 當n為1時回傳基礎的四個符號，注意這里需要用到list of list 8 op_list = generate_comb_op(n-1) # 因為之后要加，所以我們這里用到遞回的邏輯，來找到最基本的operator_list 9 all_op_list = [] # 新建一個list來準備更新我們加了運算子號后的sublist 10 # 最后我們還是要用回圈的邏輯來給我們原來list里的元素加新的符號 11 for i in op_list: 12 for j in ['+','-','*','/']: 13 all_op_list.append(i+[j]) # 這里用了新的list，來確保每個sublist的長度是相等的 14 15 return all_op_list # 最后回傳最終結果
如果再次檢查運算復雜度，我們不難看出這個函式的復雜度符合我們的預測，為O(4^n)，
好了，我們再來看數字的排列方法，如果想要找到固定數量的數字的所有排列方式，我們需要用到permutation的邏輯：找到所有排列（長度為n）的第一個元素，然后根據每個元素找到剩余數字的第一個元素（剩余數字排列長度為n-1），以此類推，直到最后只剩余一個數字，我們來看一下這個遞回思路的樹狀圖（此樹狀圖用了長度為三的list為例）：
遞回的第一層有三個元素，第二層有3*2=6個元素，第三層有3*2*1=6個元素，我們可以看出這個邏輯的復雜度為 O(n!), n為需要排列組合數字的個數，
Permutation的邏輯比運算子號的排列稍稍復雜，但是我們可以用類似的遞回結構來解決不同的問題，代碼如下：
1 def generate_permutated_list(num_list): 2 '''find permuted lists of n given numbers''' 3 # 建立base case 4 if len(num_list) == 0: 5 return [] # 當n為0時不回傳任何數字 6 if len(num_list) == 1: 7 return [num_list] # 當n為1時回傳所有式子，作為之后首數字的基礎 8 list_of_comb = [] # 新建串列來存更新的排列 9 for i in range(len(num_list)): 10 first_num = num_list[i] # 生成首字母 11 for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，繼續遞回 12 list_of_comb.append([first_num] + j) #加入新的list 13 14 return list_of_comb # 最后回傳最終結果
分別生成數學運算子號以及所有數字的排列組合后，我們要把兩個組合整合起來，以此生成所有的排列可能性，因為這里我們不用考慮排列組合數列的不確定性的問題（每個排列的長度，以及每組數學運算子號的長度維持不變），我們可以用回圈的思維來生成所有數學運算式（所有數字和數學運算子號的組合），但是生成所有數學運算式還不能完整的解決這個問題，因為我們不僅僅要生成所有的數學運算式，還要把運算式估值并和最終的目標數字進行比較，所以在組合最終的函式之前，我們需要先寫一個估值函式來方便之后的使用，
估值函式的難點在于數學運算子號的處理，因為在數學運算式里這些運算子號都是以字串的形式表達，例如 ‘+’，‘-’，所以無法當作正常運算子號放到代碼中來操作，所以在這個情況，我們要重新賦予這些字串它們象征的含義，代碼如下：
1 def modify_op(equation, op): 2 '''this function modify the given equation by only computing the section with the given operators 3 parameters: 4 equation: a list that represents a given mathematical equation which may or may not contain the 5 given numerical operators. Ex, ['1','+','2'] represents the equation 1+2 6 op: a string that is the given numerical operators''' 7 8 # 這里我們把代表數學計算的字串和以上定義的操作函式的名字以字典的方式聯系并儲存起來 9 operators = {'/':division, '*':multiply, '+':add, '-':subtract} 10 11 while op in equation: # 用while回圈來確保沒有遺漏任何字符 12 i = equation.index(op) # 找到運算式內的第一處需要計算的字符位置 13 if op == '/' and equation[i+1] == '0': # 考慮除法操作的被除數為0的情況 14 return [''] 15 # 把運算式需要計算的部分替換成計算結果 16 equation[i-1:i+2] = [str(operators[op](float(equation[i-1]), float(equation[i+1])))] # 注意這里呼叫了前面字典里儲存的函式名 17 return equation # 回傳結果 18 19 def evaluate(equation): 20 '''return the evaluated result in float for the equation''' 21 22 for op in ['/','*','+','-']: # 這里需要注意標點順序，除在最先，因為需要考慮特殊情況，乘其次，然后才是加減 23 equation = modify_op(equation, op) # 使用helper function 24 return equation[0] # 最后回傳最終計算結果
這里我們需要注意，這個估值函式能夠接收運算式的形式為list，而list里的每項也必須要用字串的形式來表達，
最后，我們只要按照之前提到的思路，整合運算式，并用以上估值函式來計算運算式的值，就可以完成這道題，在給出完整代碼之前，我們再來最后復習一下這道題的解題思路：
- 找出所有加減乘除的排列組合
- 找出所有數字的排列組合
- 整合所有運算式可能
- 用估值函式計算運算式
- 對比運算式答案和目標數
- 回傳符合要求的運算式
好了，那我們來看一下完整代碼：
1 # Write a function that takes in a list of three numbers and a target number, and 2 # returns a string that contains an expression that uses all the numbers 3 # in the list once, and results in the target. Assume that the task is possible 4 # without using parentheses. 5 # 6 # For example, get_target_noparens([3, 1, 2], 7) can return "2*3+1" or "1+2*3" 7 # (either output would be fine). 8 9 ############################################# 數學運算式生成函式 ############################################# 10 11 def generate_comb_op(n): 12 '''find all combination of Arithmetic operators with n possible spaces for operators''' 13 # 建立base case 14 if n==0: 15 return [] # 當n為0時不回傳任何運算子號 16 elif n ==1: 17 return [['+'],['-'],['*'],['/']] # 當n為1時回傳基礎的四個符號，注意這里需要用到list of list 18 op_list = generate_comb_op(n-1) # 因為之后要加，所以我們這里用到遞回的邏輯，來找到最基本的operator_list 19 all_op_list = [] # 新建一個list來準備更新我們加了運算子號后的sublist 20 # 最后我們還是要用回圈的邏輯來給我們原來list里的元素加新的符號 21 for i in op_list: 22 for j in ['+','-','*','/']: 23 all_op_list.append(i+[j]) # 這里用了新的list，來確保每個sublist的長度是相等的 24 25 return all_op_list # 最后回傳最終結果 26 27 28 def generate_permutated_list(num_list): 29 '''find permuted lists of n given numbers''' 30 # 建立base case 31 if len(num_list) == 0: 32 return [] # 當n為0時不回傳任何數字 33 if len(num_list) == 1: 34 return [num_list] # 當n為1時回傳所有式子，作為之后首數字的基礎 35 list_of_comb = [] # 新建串列來存更新的排列 36 for i in range(len(num_list)): 37 first_num = num_list[i] # 生成首字母 38 for j in generate_permutated_list(num_list[:i] + num_list[i+1:]): # 去除首字母，繼續遞回 39 list_of_comb.append([first_num] + j) #加入新的list 40 41 return list_of_comb # 最后回傳最終結果 42 43 44 #################################### 定義所有可能出現的數學操作，包括加減乘除 #################################### 45 46 def division(a,b): # 除法比較特殊，在之后的代碼里會考慮到被除數為0的情況 47 return a/b 48 def multiply(a,b): 49 return a*b 50 def add(a,b): 51 return a+b 52 def subtract(a,b): 53 return a-b 54 55 ############################################ 數學運算式處理函式 ############################################## 56 57 def modify_op(equation, op): 58 '''this function modify the given equation by only computing the section with the given operators 59 parameters: 60 equation: a list that represents a given mathematical equation which may or may not contain the 61 given numerical operators. Ex, ['1','+','2'] represents the equation 1+2 62 op: a string that is the given numerical operators''' 63 64 # 這里我們把代表數學計算的字串和以上定義的操作函式的名字以字典的方式聯系并儲存起來 65 operators = {'/':division, '*':multiply, '+':add, '-':subtract} 66 67 while op in equation: # 用while回圈來確保沒有遺漏任何字符 68 i = equation.index(op) # 找到運算式內的第一處需要計算的字符位置 69 if op == '/' and equation[i+1] == '0': # 考慮除法操作的被除數為0的情況 70 return [''] 71 # 把運算式需要計算的部分替換成計算結果 72 equation[i-1:i+2] = [str(operators[op](float(equation[i-1]), float(equation[i+1])))] # 注意這里呼叫了前面字典里儲存的函式名 73 return equation # 回傳結果 74 75 def evaluate(equation): 76 '''return the evaluated result in float for the equation''' 77 78 for op in ['/','*','+','-']: # 這里需要注意標點順序，除在最先，因為需要考慮特殊情況，乘其次，然后才是加減 79 equation = modify_op(equation, op) # 使用helper function 80 return equation[0] # 最后回傳最終計算結果 81 82 ############################################# 最終使用函式 ############################################### 83 84 def get_target_noparens(num_list, target): 85 op_list = generate_comb_op(len(num_list)-1) # 找出所有加減乘除的排列組合 86 num_comb = generate_permutated_list(num_list) # 找出所有數字的排列組合 87 # 用for嵌套回圈來整合所有運算式可能 88 for each_op_list in op_list: 89 for each_num_list in num_comb: 90 equation = [] # 用list初始化運算式 91 equation_str = '' # 用string表達算式 92 for i in range(len(each_op_list)): 93 equation.extend([str(each_num_list[i]), each_op_list[i]]) 94 equation_str += str(each_num_list[i]) + each_op_list[i] 95 equation.append(str(each_num_list[-1])) 96 equation_str += str(each_num_list[-1]) 97 98 result = evaluate(equation) # 運算式估值，這里要用list的形式 99 if float(result) == float(target): 100 return equation_str # 用字串回傳算式
我們稍作測驗：
- get_target_noparens([1,2,3], 6)回傳 1+2+3
- get_target_noparens([1,2,3], 4.5)回傳 1+3/2
- get_target_noparens([23,1,3], 68)回傳 23*3-1
三個測驗都成功通過，那么我們的第一題就解完了，
我們這里對第一題的解法同樣能夠應用到第二題的基礎部分，因為篇幅原因，第二題的解題方式會放到下一篇講解，鏈接如下：
https://www.cnblogs.com/Lin-z/p/14219620.html
那我們今天就到這里，新年快樂！
參考資料：
- https://en.wikipedia.org/wiki/24_Game
- 例題選自 University of Toronto, ESC180 2020 Final, Question 4 & Question 5
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243474.html
標籤：Python
下一篇：Python筆記