有趣的演算法謎題之2016

計算2016

今天我們來計算一個有意思的演算法謎題，這樣長這樣的：

10 □ 9 □ 8 □ 7 □ 6 □ 5 □ 4 □ 3 □ 2 □ 1 = 2016

就是使用 + - * / 來填充空白，同時也可以使用括弧，也就是這樣的

(10 - 9) × (8 ...

或者

10 + (9 × 8) ...

任務1

只使用四則運算，完成2016

解決方案：

由於一共有9個運算符，每個運算符有4種可能性，於是一共有：

4**9 = 262144 種可能性n

因此我們可以這樣，使用Python自帶的eval函數進行計算

def evaluate(exp):n try:n return eval(exp)n except ArithmeticError:n return Nonenndef solve_no_brackets(ops=(+,-,*,/)):n exps = (10+a+9+b+8+c+7+d+6+e+5+f+4+g+3+h+2+i+1n for a in ops for b in ops for c in ops n for d in ops for e in ops for f in ops n for g in ops for h in ops for i in opsn )n return [exp for exp in exps if evaluate(exp)==2016]n

來運行下看看：

solve_no_brackets()n

可以發現，沒有結果？難道做錯了？那可以看看計算出了哪些數字？

def solve_no_brackets(targets, ops=(+,-,*,/)):n exps = (10+a+9+b+8+c+7+d+6+e+5+f+4+g+3+h+2+i+1n for a in ops for b in ops for c in ops n for d in ops for e in ops for f in ops n for g in ops for h in ops for i in opsn )n return {int(evaluate(exp)):expn for exp in exps if evaluate(exp) in targets}nsolve_no_brackets(range(1900,2100))n

得到的結果為：

{1979: 10*9*8+7*6*5*4*3/2-1,n 1980: 10*9*8+7*6*5*4*3/2/1,n 1981: 10*9*8+7*6*5*4*3/2+1,n 2013: 10*9*8*7/6/5*4*3-2-1,n 2014: 10*9*8*7/6/5*4*3-2/1,n 2015: 10*9*8*7/6/5*4*3-2+1,n 2017: 10*9*8*7/6/5*4*3+2-1,n 2018: 10*9*8*7/6/5*4*3+2/1,n 2019: 10*9*8*7/6/5*4*3+2+1}n

原來如此，僅僅通過四則運算，是得不到2016的。那麼，需要括弧的幫助。

任務2 使用括弧完成2016

明顯可以感覺到，使用了括弧以後，計算量遠遠增大，而且細心的同學可以發現，在進行有括弧的算術運算中，有很多子問題重複運算了，因此可以使用動態規劃來計算。那麼如何拆分成小問題呢？

(10 ... 8) + (7 ... 1)

可以這樣，（10 ... 8）表示以10開頭，8結束

因此可以這樣，先將序列拆分

c10 = (10,9,8,7,6,5,4,3,2,1)ndef splits(items):n return [(items[:i],items[i:])n for i in range(1,len(items))n ]nnsplits(c10)n[((10,), (9, 8, 7, 6, 5, 4, 3, 2, 1)),n ((10, 9), (8, 7, 6, 5, 4, 3, 2, 1)),n ((10, 9, 8), (7, 6, 5, 4, 3, 2, 1)),n ((10, 9, 8, 7), (6, 5, 4, 3, 2, 1)),n ((10, 9, 8, 7, 6), (5, 4, 3, 2, 1)),n ((10, 9, 8, 7, 6, 5), (4, 3, 2, 1)),n ((10, 9, 8, 7, 6, 5, 4), (3, 2, 1)),n ((10, 9, 8, 7, 6, 5, 4, 3), (2, 1)),n ((10, 9, 8, 7, 6, 5, 4, 3, 2), (1,))]n

因此，我們想 建立這樣的表格：

EXPS[(10, 9, 8)] = {n 27: ((10+9)+8),n 8: ((10-9)*8), n -7: (10-(9+8)), n ...}n

表格含義就是：一組列表為鍵，值也為鍵，列表生成值對應的表達式為鍵的值。比如，(10,9,8)生成27所對應的表達式是((10+9)+8)

from collections import defaultdict,Counternimport itertoolsnnEXPS = defaultdict(dict) # e.g., EXPS[(10, 9, 8)][27] == ((10+9)+8)nndef expr(numbers,values,exp):n EXPS[numbers][values] = expnndef expressions(numbers):n if numbers in EXPS:n passn elif len(numbers) == 1:n expr(numbers,numbers[0],str(numbers[0]))n else:n for (Lnums,Rnums) in split(numbers):n for (L,R) in itertools.product(expressions(Lnums),expressions(Rnums)):n Lexp,Rexp = ( + EXPS[Lnums][L],EXPS[Rnums][R]+)n if R != 0:n expr(numbers,L/R,Lexp+/+Rexp)n expr(numbers,L*R,Lexp+*+Rexp)n expr(numbers,L+R,Lexp+++Rexp)n expr(numbers,L-R,Lexp+-+Rexp)n return EXPS[numbers]n

來看看結果：

expressions((10, 9, 8))nn{-62: (10-(9*8)),n -7: ((10-9)-8),n -6.888888888888889: ((10/9)-8),n 0.125: ((10-9)/8),n 0.1388888888888889: ((10/9)/8),n 0.5882352941176471: (10/(9+8)),n 2.375: ((10+9)/8),n 8: ((10-9)*8),n 8.875: (10-(9/8)),n 8.88888888888889: ((10/9)*8),n 9: ((10-9)+8),n 9.11111111111111: ((10/9)+8),n 10.0: (10*(9-8)),n 11: ((10+9)-8),n 11.125: (10+(9/8)),n 11.25: ((10*9)/8),n 27: ((10+9)+8),n 82: ((10*9)-8),n 98: ((10*9)+8),n 152: ((10+9)*8),n 170: (10*(9+8)),n 720: ((10*9)*8)}n

貌似不錯，我們來計算2016，這時候可以喝杯coffe哦！

expressions(c10)[2016]nn(((((((10+((9*8)*7))-6)-5)*4)+3)+2)-1)n

大概耗時50s。