=== 4月12日更新 ===

=== 先給結(jié)論吧 ===

花了近一周時(shí)間用JavaScript完成了24點(diǎn)去重算法，源碼提交到了github上：auntyellow/24 ，可以在線試：gives you all dissimilar solutions.

在1到13范圍內(nèi)的四數(shù)組合中，不重復(fù)解最多的組合是2、4、8、10：

10 + 8 + 4 + 2 = 24

(10 - 4) × 8 ÷ 2 = 24

(10 × 4 + 8) ÷ 2 = 24

((10 + 2) × 8 ÷ 4 = 24

10 × 2 + 8 - 4 = 24

(10 - 2) × 4 - 8 = 24

8 × 4 - 10 + 2 = 24

(8 ÷ 4 + 10) × 2 = 24

(8 × 2 - 10) × 4 = 24

(10 - 8 ÷ 2)) × 4 = 24

10 × 4 - 8 × 2 = 24

只能用分?jǐn)?shù)來解的(16個(gè)，這里不給答案了，有興趣可以自己練練)：

1, 3, 4, 6

1, 4, 5, 6 (這題居然有兩解，都必須用分?jǐn)?shù)的)

1, 5, 5, 5

1, 6, 6, 8

1, 8, 12, 12

2, 2, 11, 11

2, 2, 13, 13

2, 3, 5, 12

2, 4, 10, 10

2, 5, 5, 10

2, 7, 7, 10

3, 3, 7, 7

3, 3, 8, 8

4, 4, 7, 7

5, 5, 7, 11

5, 7, 7, 11

其他有難度的，就是中間過程必須有大數(shù)的(大于36就很難一下子想到了)(像a × b - a × c = 24這種形式，比如10、12、12、12，其實(shí)并沒有太大難度，就沒有列進(jìn)去)：

1, 7, 13, 13

6, 12, 12, 13

1, 6, 11, 13

6, 11, 12, 12

5, 10, 10, 13

1, 5, 11, 11

5, 10, 10, 11

4, 8, 8, 13

4, 4, 10, 10

4, 8, 8, 11

6, 9, 9, 10

3, 8, 8, 10

3, 5, 7, 13

3, 6, 6, 11

1, 2, 7, 7

5, 8, 9, 13

5, 9, 10, 11

4, 7, 11, 13

4, 9, 11, 11

4, 10, 10, 11

6, 7, 7, 11

3, 5, 8, 13

5, 5, 8, 11

2, 3, 13, 13

還找到一個(gè)難的：3、7、9、13，它有兩種解法，一種用到了分?jǐn)?shù)，一種有大數(shù)。

為了驗(yàn)證這些結(jié)論，還是查到了 @常成 那邊，包括 理論 - 24理論 解決二十四點(diǎn) (我的算法跟這里相當(dāng)接近了)、所有獨(dú)立解 － 24理論 解決二十四點(diǎn) (解法最多的牌型確實(shí)有11個(gè)解)，需要分?jǐn)?shù)的解 － 24理論 解決二十四點(diǎn) (確實(shí)有16個(gè)牌型)，看來程序是沒太大問題了。

=== 然后說說算法 ===

參考了本題 小于0 的回答，還有 24點(diǎn)算法，如何給出所有不同的答案 - 蘿卜的回答 - SegmentFault ，總之就是列出所有不等價(jià)表達(dá)式，例如 (( a + b ) * c) / d 和 (( b + a) * c ) / d 是等價(jià)的，需要去重。

雖然是重復(fù)在做很多人以前做過的工作，但還是有些自認(rèn)為別出心裁的思路，因?yàn)椴]從代數(shù)形式上做分析，而是通過試數(shù)的辦法做的，試的是π、e、lnπ和arctan e這四個(gè)超越數(shù)，對近似值做比較(浮點(diǎn)數(shù)運(yùn)算總是有誤差的)來判斷兩個(gè)表達(dá)式是否等價(jià)。(我把近似度設(shè)定在1e-6其實(shí)算是碰巧蒙對了，SegmentFault的蘿卜指出lnπ/(e + π/arctan(e))和π/e - lnπ/arctan(e)只相差7.9e-6，如果把近似度再提高1個(gè)數(shù)量級(jí)，結(jié)果可能就不對了。)

5種括號(hào)型(((oxo)xo)xo、(ox(oxo))xo、(oxo)x(oxo)、ox((oxo)xo)、ox(ox(oxo))，其中o代表數(shù)字，x代表運(yùn)算符)，4個(gè)數(shù)一共有24種排列，3個(gè)符號(hào)一共有64種排列，總共需要“試數(shù)”的表達(dá)式總共有7680個(gè)，在這些表達(dá)式中找出了1170種不等價(jià)的，也和網(wǎng)上能找到的資料相吻合，例如 小于0 給我推薦的 A140606 - OEIS 。

后來發(fā)現(xiàn)，僅僅用這1170個(gè)表達(dá)式是不夠的，還要考慮以下14種牌型：

a, a, b, c // 兩個(gè)相同的數(shù)可以交換，也可以抵消

a, a, b, b

a, a, a, b

a, a, a, a

1, a, b, c // 1可以舍去

1, a, a, b

1, a, a, a

1, 1, a, b

1, 1, a, a

1, 1, 1, a

2, 2, a, b // 2 + 2 = 2 × 2，這個(gè)算重復(fù)解應(yīng)該說得過去

2, 2, a, a

1, 2, 2, a

2, a, a, b // 2 × a - a = (a + a) ÷ 2，這個(gè)居然被我算成重復(fù)解了！

另外還有，a、a'(=a+1)、b、c這種牌型，需要把(a'-a)參與乘除運(yùn)算的解法排除掉，然后單獨(dú)算b+c、b*c有沒有可能等于24。

所以程序里絕大部分邏輯都是在判斷：牌型到底屬于上面列出來的15種當(dāng)中的哪一種，寫得相當(dāng)啰嗦。

另外還有一些小問題，比如：1、1、5、5，只給出了一種解，因?yàn)閷ε菩?、1、a、a組成的表達(dá)式來說， (a+1)(a-1)和a*a-1*1是等價(jià)的；

沒有考慮4/2和4-2等價(jià)的問題，例如2、4、6、6，(6-(4-2))*6和(6-4/2)*6被認(rèn)為是兩個(gè)不等價(jià)的解(憑什么2+2和2*2等價(jià)，但4-2和4/2不等價(jià)？)

當(dāng)2作為中間步驟時(shí)，沒考慮2+2和2*2的等價(jià)，還拿2、4、6、6說事，(6-4+2)*6和(6-4)*2*6是不等價(jià)的解(寫到這里我真后悔把2+2和2*2算做等價(jià)了)

仔細(xì)想想，還真不能輕易認(rèn)為2+2=2*2、4-2=4/2是等價(jià)解法，要是真這么算的話，那么我們可以寫出：

(6-4/2)*6 = (6-(4-2))*6 = (6-4+2)*6 = (6-4)*2*6

顯然每個(gè)等號(hào)左右兩邊都是等價(jià)的。但要說最左邊的和最右邊的是重復(fù)的解法，那又說不過去了。

看似很簡單的問題，本以為可以花半天時(shí)間搞定的，結(jié)果編碼、測試、驗(yàn)證、優(yōu)化一系列過程居然花了1周的時(shí)間，再次印證了我的盲目樂觀 :-(

=== 更早的回答 ===

我在SegmentFault上提了一個(gè)相似的問題，問完才發(fā)現(xiàn)知乎上已經(jīng)有了。很快就有人給出漂亮的解答了：24點(diǎn)算法，如何給出所有不同的答案 - 蘿卜的回答 - SegmentFault ，起初答題者思路跟 小于0 的回答類似，后來發(fā)現(xiàn)窮舉太麻煩，就改用符號(hào)代數(shù)，在Mathimatica里用10余行代碼搞定了，真讓我吃驚。

另外，對于重復(fù)解的定義，還是有挺大爭論的，比如我認(rèn)為2x2和2+2應(yīng)該算是雷同的，但很多人并不認(rèn)同。

轉(zhuǎn)載一下：

Clear[game24]game24[input_List,result_:24]:=Block[{add,sub,mul,div},With[{oprules={add->Plus,sub->Subtract,mul->Times,div->Divide},specifics={div[x_,1]:>x,mul[x_,1]:>x,mul[1,x_]:>x,add[2,2]->mul[2,2]}},Map[RightComposition[Hold,ReplaceAll[oprules],ToString[#,InputForm]&,StringDelete[{"Hold[","]"}],StringReplace[{"*"->"\[Times]","/"->"\[Divide]"}]],Union[Select[result==(#/.oprules)&]@Groupings[Permutations@input,{add,sub,mul,div}->2],SameTest->(0===Simplify[sub[#1,#2]//.specifics/.Prepend[oprules,k_Integer:>ToString[k]]]&)]]]]用符號(hào)add、sub、mul、div分別對應(yīng)加減乘除四則運(yùn)算，構(gòu)建二叉樹代表算式。Groupings函數(shù)生成了所有可能的表達(dá)式二叉樹。

Select篩選出計(jì)算結(jié)果符合要求的。

Union負(fù)責(zé)除去雷同的算式。它的SameTest選項(xiàng)計(jì)算兩個(gè)代數(shù)式的差化簡后是否為0。注意這里通過把數(shù)字轉(zhuǎn)為字符進(jìn)行“符號(hào)化”了，而且對數(shù)字1、2進(jìn)行了特殊處理(specifics)。

最后Map負(fù)責(zé)把每個(gè)算式轉(zhuǎn)成字符串輸出。

測試：

總結(jié)

以上是生活随笔為你收集整理的python算24点穷举法_关于24点去重的算法?的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。