>

24点算法之笔者见,又进步推了少数

- 编辑:ca88手机会员 -

24点算法之笔者见,又进步推了少数

做为 N95 的后继机型,N96 当然要将规格再向上推到一个新的高度,才对得起广大民众的爱护,对吧?N96 不仅内置 16GB 的内存,而且还可以插 microSD 卡扩充,再加上 5mp 蔡司自动对焦镜头、两颗打光用的 LED、2.8" QVGA 屏幕、3.5" 耳机插孔、N-Gage 游戏支持、还有 DVB-H、A2DP、AGPS、WiFi、HSDPA 等一串令人垂涎三尺的英文缩写,N96 绝对是 Nokia 新一代的万能瑞士刀 -- 接下来只是看 €550 欧元的售价把你吓跑了没而已...[原文连接]

之前发了一篇博文“24点的所有组合的解法”,有人颇不以为然。我想说的是,发这篇文章是说明我可以用计算机求出24点的所有组合的解法。而在实际的运用中,如果要使用24点的算法有时还不见得利用查表法来得简单和快速。毕竟,要短时间内写出正确的算法并验证,也不是一件很容易的事。

 

24点游戏的规则:给定4个正整数(1到10),利用加减乘除运算,得出运算结果为24的运算式

例如:

1,2,3,4——(1 2 3)*4=24

1,5,5,5——(5-1/5)*5=24

 

网上比较常见的24点算法是动态规划算法(这个在博客园中也能搜索到)。

 

定义6个二元运算符:加、减、乘、除、反减、反除

然后从4个数中任选2个数,通过一种运算(6个运算中的1个)得到一个新数

问题就演化成3个数的24点

 

重复上面的步骤,直到剩下一个数,如果这个数是24,则之前的运算过程就是24点的解答之一。如果这个数不是24,说明之前的运算不正确,再重新计算。如果所有的数的组合和运算的组合都尝试后,仍然没有找到解答,说明这4个数没有解

 

算一算运算一组解需要多少种可能性

第一步,从4个数中,任选两个数,6个运算符,则一共有C(4,2)*6=6*6=36

第二步,从3个数中,任选两个数,6个运算符,则一共有C(3,2)*6=3*6=18,则前两步一共有36*18=648种

第三步,6个运算符,则一共有6,最终求一组解的要搜索的可能性有648*6=3888种

 

上面是求一组解,要搜索的可能性,一共3888种

 

如果要得出所有组合的解,先要算出一共有多少种组合

4个数都不相同,C(10,4)=210

只有2个数相同,C(10,3)*3=360

2组2个数相同,C(10,2)=45

只有3个数相同,C(10,2)*2=90

4个数都相同,C(10,1)=10

则一共有210 360 45 90 10=715组

 

则求出所有组合的解,则一共要搜索715*3888=2779920种可能性

 

说白了,24点的算法就是一种穷举法

 

换一种思路,介绍我的24点的穷举法

上面的算法是对数和运算符进行穷举和搜索

 

我的算法是对运算式进行穷举

无论给什么样的是4个数,运算式总是不变的,举例来说:

N N N N=24,这是一种运算式

N*N N*N=24,这是另一种运算式

N/(N-N/N)=24,这又是另一种运算式

 

下面这个例子:

N N-(N-N)=24

N N-N N=24

上面虽然是两种不同的运算式,但本质是同一种运算式(肯定同时成立或同时不成立),穷举的时候只要穷举其中一个就行了

 

再看下面这个例子

N/(N N N)=24

虽然是一个运算式,但是这个运算式是不可能成立的,也就是无解运算式,穷举的时候是不需要穷举该运算式的

下面这个表格是我整理的所有的运算式,其中有的运算式有等价运算式,有的运算式是无解运算式,按照上面的讲法,这两类运算式在穷举的时候都不需要穷举

 

24点运算式表

运算式

等价运算式

是否有解

 

 

N N N N=24

 

 

 

 

 

-

 

 

N N N-N=24

 

 

 

 

 

*

 

 

N N N*N=24

 

 

N (N N)*N=24

 

 

(N N N)*N=24

 

 

 

 

 

/

 

 

N N N/N=24

 

 

N (N N)/N=24

 

 

(N N N)/N=24

 

 

 

 

 

-

 

 

N N-N N=24

N N N-N=24

 

N N-(N N)=24

N N-N-N=24

无解

 

 

 

--

 

 

N N-N-N=24

 

无解

N N-(N-N)=24

N N-N N=24
N N N-N=24

 

 

 

 

-*

 

 

N N-N*N=24

 

无解

N (N-N)*N=24

 

 

(N N-N)*N=24

 

 

 

 

 

-/

 

 

N N-N/N=24

 

无解

N (N-N)/N=24

 

无解

(N N-N)/N=24

 

无解

 

 

 

*

 

 

N N*N N=24

 

 

(N N)*N N=24

 

 

N N*(N N)=24

(N N)*N N=24

 

(N N)*(N N)=24

 

 

 

 

 

*-

 

 

N N*N-N=24

 

 

(N N)*N-N=24

 

 

N N*(N-N)=24

N (N-N)*N

 

(N N)*(N-N)=24

 

 

 

 

 

**

 

 

N N*N*N=24

 

 

(N N)*N*N=24

 

 

(N N*N)*N=24

 

 

 

 

 

*/

 

 

N N*N/N=24

 

 

(N N)*N/N=24

 

 

(N N*N)/N=24

 

 

 

 

 

/

 

 

N N/N N=24

 

 

(N N)/N N=24

 

 

N N/(N N)=24

 

无解

(N N)/(N N)=24

 

无解

 

 

 

/-

 

 

N N/N-N=24

 

无解

(N N)/N-N=24

 

无解

N N/(N-N)=24

 

无解

(N N)/(N-N)=24

 

无解

 

 

 

/*

 

 

N N/N*N=24

N N*N/N=24

 

(N N)/N*N=24

(N N)*N/N=24

 

(N N/N)*N=24

 

 

N N/(N*N)=24

N N/N/N=24

无解

(N N)/(N*N)=24

(N N)/N/N=24

无解

 

 

 

//

 

 

N N/N/N=24

 

无解

(N N)/N/N=24

 

无解

(N N/N)/N=24

 

无解

N N/(N/N)=24

N N/N*N=24
N N*N/N=24

 

(N N)/(N/N)=24

(N N)/N*N=24
(N N)*N/N=24

 

 

 

 

-

 

 

N-N N N=24

N N N-N=24

 

N-(N N) N=24

N-N-N N=24
N N-N-N=24

无解

N-(N N N)=24

N-N-N-N=24

无解

 

 

 

- -

 

 

N-N N-N=24

N N-N-N=24

无解

N-(N N)-N=24

N-N-N-N=24

无解

N-(N N-N)=24

N-N-N N=24
N N-N-N=24

无解

 

 

 

- *

 

 

N-N N*N=24

N N*N-N=24

 

N-(N N)*N=24

 

无解

N-(N N*N)=24

 

无解

(N-N N)*N=24

(N N-N)*N=24

 

(N-(N N))*N=24

(N-N-N)*N=24

 

 

 

 

- /

 

 

N-N N/N=24

 

无解

N-(N N)/N=24

 

无解

N-(N N/N)=24

N-N-N/N=24

无解

(N-N N)/N=24

(N N-N)/N=24

无解

(N-(N N))/N=24

(N-N-N)/N=24

无解

 

 

 

--

 

 

N-N-N N=24

N N-N-N=24

无解

N-(N-N) N=24

N-N N N=24
N N N-N=24

 

N-(N-N N)=24

N-N N-N=24
N N-N-N=24

无解

N N-N-N=24

N-N N N=24
N N N-N=24

 

N-N-(N N)=24

N-N-N-N=24

无解

 

 

 


 

 

N-N-N-N=24

 

无解

N-N-(N-N)=24

N-N-N N =24
N N-N-N=24

无解

N-(N-N)-N=24

N-N N-N=24
N N-N-N=24

无解

N-(N-N-N)=24

N-N N N=24
N N N-N=24

 

N-(N-(N-N))=24

N-N N-N=24
N N-N-N=24

无解

 

 

 

--*

 

 

N-N-N*N=24

 

无解

N-(N-N)*N=24

N (N-N)*N=24

 

(N-N-N)*N=24

 

 

(N-(N-N))*N=24

(N-N N)*N=24
(N N-N)*N=24

 

 

 

 

--/

 

 

N-N-N/N=24

 

无解

N-(N-N)/N=24

N (N-N)/N=24

无解

(N-N-N)/N=24

 

无解

(N-(N-N))/N=24

(N-N N)/N=24
(N N-N)/N=24

无解

 

 

 

-*

 

 

N-N*N N=24

N N-N*N=24

无解

(N-N)*N N=24

N (N-N)*N=24

 

N-N*(N N)=24

N-(N N)*N=24

无解

(N-N)*(N N)=24

(N N)*(N-N)=24

 

N-(N*N N)=24

N-N*N-N=24
N-N-N*N=24

无解

 

 

 

-*-

 

 

N-N*N-N=24

N-N-N*N=24

无解

(N-N)*N-N=24

 

 

N-N*(N-N)=24

N N*(N-N)=24
N (N-N)*N=24

 

(N-N)*(N-N)=24

 

 

N-(N*N-N)=24

N-N*N N=24
N N-N*N=24

无解

 

 

 

-**

 

 

N-N*N*N=24

 

无解

(N-N)*N*N=24

 

 

(N-N*N)*N=24

 

 

 

 

 

-*/

 

 

N-N*N/N=24

 

无解

(N-N)*N/N=24

 

 

(N-N*N)/N=24

 

无解

 

 

 

-/

 

 

N-N/N N=24

N N-N/N=24

无解

(N-N)/N N=24

N (N-N)/N=24

无解

N-N/(N N)=24

 

无解

(N-N)/(N N)=24

 

无解

N-(N/N N)=24

N-N/N-N=24
N-N-N/N=24

无解

 

 

 

-/-

 

 

N-N/N-N=24

N-N-N/N=24

无解

(N-N)/N-N=24

 

无解

N-N/(N-N)=24

N N/(N-N)=24

无解

(N-N)/(N-N)=24

 

无解

N-(N/N-N)=24

N-N/N N=24
N N-N/N=24

无解

 

 

 

-/*

 

 

N-N/N*N=24

 

无解

(N-N)/N*N=24

(N-N)*N/N

 

(N-N/N)*N=24

 

 

N-N/(N*N)=24

N-N/N/N=24

无解

(N-N)/(N*N)=24

(N-N)/N/N=24

无解

 

 

 

-//

 

 

N-N/N/N=24

 

无解

(N-N)/N/N=24

 

无解

(N-N/N)/N=24

 

无解

N-N/(N/N)=24

N-N/N*N=24
N-N*N/N=24

无解

(N-N)/(N/N)=24

(N-N)/N*N=24
(N-N)*N/N=24

 

 

 

 

*

 

 

N*N N N=24

N N N*N=24

 

N*(N N) N=24

N (N N)*N=24

 

N*(N N N)=24

(N N N)*N=24

 

 

 

 

* -

 

 

N*N N-N=24

N-N N*N=24

 

N*(N N)-N=24

(N N)*N-N=24

 

N*(N N-N)=24

(N N-N)*N=24

 

 

 

 

* *

 

 

N*N N*N=24

 

 

N*(N N)*N=24

(N N)*N*N=24

 

(N*N N)*N=24

(N N*N)*N=24

 

N*(N N*N)=24

(N N*N)*N=24

 

 

 

 

* /

 

 

N*N N/N=24

 

 

N*(N N)/N=24

(N N)*N/N=24

 

(N*N N)/N=24

(N N*N)/N=24

 

N*(N N/N)=24

(N N/N)*N=24

 

 

 

 

*-

 

 

N*N-N N=24

N-N N*N=24

 

N*(N-N) N=24

N (N-N)*N=24

 

N*(N-N N)=24

(N N-N)*N=24

 

N*N-(N N)=24

N*N-N-N=24

 

N*(N-(N N))=24

N*(N-N-N)=24
(N-N-N)*N=24

 

 

 

 

*--

 

 

N*N-N-N=24

 

 

N*(N-N)-N=24

(N-N)*N-N=24

 

N*(N-N-N)=24

(N-N-N)*N=24

 

N*N-(N-N)=24

N*N-N N=24
N-N N*N=24

 

N*(N-(N-N))=24

N*(N-N N)=24
(N N-N)*N=24

 

 

 

 

*-*

 

 

N*N-N*N=24

 

 

N*(N-N)*N=24

(N-N)*N*N=24

 

(N*N-N)*N=24

 

 

N*(N-N*N)=24

(N-N*N)*N=24

 

 

 

 

*-/

 

 

N*N-N/N=24

 

 

N*(N-N)/N=24

(N-M2)*N/N=24

 

(N*N-N)/N=24

 

 

N*(N-N/N)=24

(N-N/N)*N=24

 

 

 

 

**

 

 

N*N*N N=24

N N*N*N=24

 

N*N*(N N)=24

(N N)*N*N=24

 

N*(N*N N)=24

(N N*N)*N=24

 

 

 

 

**-

 

 

N*N*N-N=24

 

 

N*N*(N-N)=24

(N-N)*N*N=24

 

N*(N*N-N)=24

(N*N-N)*N=24

 

 

 

 

***

 

 

N*N*N*N=24

 

 

 

 

 

**/

 

 

N*N*N/N=24

 

 

 

 

 

*/

 

 

N*N/N N=24

N N*N/N=24

 

N*N/(N N)=24

 

 

N*(N/N N)=24

(N N/N)*N=24

 

 

 

 

*/-

 

 

N*N/N-N=24

 

 

N*N/(N-N)=24

 

 

N*(N/N-N)=24

 

 

 

 

 

*/*

 

 

N*N/N*N=24

N*N*N/N=24

 

N*N/(N*N)=24

N*N/N/N=24

 

 

 

 

*//

 

 

N*N/N/N=24

 

 

N*N/(N/N)=24

N*N/N*N=24
N*N*N/N=24

 

 

 

 

/

 

 

N/N N N=24

N N N/N=24

 

N/(N N) N=24

N N/(N N)=24

无解

N/(N N N)=24

 

无解

 

 

 

/ -

 

 

N/N N-N=24

N-N N/N=24

无解

N/(N N)-N=24

 

无解

N/(N N-N)=24

 

无解

 

 

 

/ *

 

 

N/N N*N=24

N*N N/N=24

 

N/(N N)*N=24

N*N/(N N)=24

 

(N/N N)*N=24

(N N/N)*N=24

 

N/(N N*N)=24

 

无解

 

 

 

/ /

 

 

N/N N/N=24

 

无解

N/(N N)/N=24

 

无解

(N/N N)/N=24

(N N/N)/N=24

无解

N/(N N/N)=24

 

无解

N/((N N)/N)=24

N/(N N)*N=24
N*N/(N N)=24

 

 

 

 

/-

 

 

N/N-N N=24

N-N N/N=24

无解

N/N-(N N)=24

N/N-N-N=24

无解

N/(N-N) N=24

N N/(N-N)=24

无解

N/(N-N N)=24

N/(N N-N)=24

无解

N/(N-(N N))=24

N/(N-N-N)=24

无解

 

 

 

/--

 

 

N/N-N-N=24

 

无解

N/N-(N-N)=24

N/N-N N=24
N N/N-N=24

无解

N/(N-N)-N=24

 

无解

N/(N-N-N)=24

 

无解

N/(N-(N-N))=24

N/(N-N N)=24
N/(N N-N)=24

无解

 

 

 

/-*

 

 

N/N-N*N=24

 

无解

N/(N-N)*N=24

N*N/(N-N)=24

 

N/(N-N*N)=24

 

无解

(N/N-N)*N=24

 

 

 

 

 

/-/

 

 

N/N-N/N=24

 

无解

N/(N-N)/N=24

 

无解

(N/N-N)/N=24

 

无解

N/(N-N/N)=24

 

 

N/((N-N)/N)=24

N/(N-N)*N=24
N*N/(N-N)=24

 

 

 

 

/*

 

 

N/N*N N=24

N N*N/N=24

 

N/N*(N N)=24

(N N)*N/N=24

 

N/(N*N N)=24

N/(N N*N)=24

无解

N/(N*(N N))=24

N/N/(N N)=24
N/(N N)/N=24

无解

 

 

 

/*-

 

 

N/N*N-N=24

N*N/N-N=24

 

N/N*(N-N)=24

N*(N-N)/N=24

 

N/(N*N-N)=24

 

无解

N/(N*(N-N))=24

N/N/(N-N)=24
N/(N-N)/N=24

无解

N/(N*N)-N=24

N/N/N-N=24

无解

 

 

 

/**

 

 

N/N*N*N=24

N*N*N/N=24

 

N/(N*N)*N=24

N/N/N*N=24
N*N/N/N=24

 

N/(N*N*N)=24

N/N/N/N=24

无解

 

 

 

/*/

 

 

N/N*N/N=24

N*N/N/N=24

 

N/(N*N)/N=24

N/N/N/N=24

无解

N/(N*N/N)=24

N/N/N*N=24
N*N/N/N=24

 

 

 

 

//

 

 

N/N/N N=24

N N/N/N

无解

N/N/(N N)=24

 

无解

N/(N/N N)=24

N/(N N/N)=24

无解

N/(N/(N N))=24

N/N*(N N)=24
(N N)*N/N=24

 

 

 

 

//-

 

 

N/N/N-N=24

 

无解

N/N/(N-N)=24

 

无解

N/(N/N-N)=24

 

 

N/(N/(N-N))=24

N/N*(N-N)=24
(N-N)*N/N=24

 

 

 

 

//*

 

 

N/N/N*N=24

N*N/N/N=24

 

N/N/(N*N)=24

N/N/N/N=24

无解

N/(N/N)*N=24

N/N*N*N=24
N*N*N/N=24

 

N/(N/N*N)=24

N/N*N/N=24
N*N/N/N=24

 

 

 

 

///

 

 

N/N/N/N=24

 

无解

N/N/(N/N)=24

N/N/N*N=24
N*N/N/N=24

 

N/(N/N)/N=24

N/N*N/N=24
N*N/N/N=24

 

N/(N/N/N)=24

N/N*N/N=24
N*N/N/N=24

 

 

算一算,要求出所有组合的解,需要穷举多少种可能

需要穷举的运算式一共有50个

之前说一共有715组,这715组每个组一共有4!=24中排列方式,24钟排列方式代入到50个运算式,则一共需要穷举

715*24*50=858000

 

是不是远小于之前的2779920种

 

既然都是穷举,还不如把所有的结果都保存起来,这样穷举的可能性就只有200种不到了,秒杀所有的算法

 

我想说的是,有时查表计算并不是一种坏的算法。要知道很多语言中求三角函数都是利用查表来快速计算的

 

 

最后,说一句题外话,请教各位网友一个计算机的问题

我有一台电脑,WIN7系统。近阶段出现一个怪现象

在开机进入系统后,插入U盘,能正确识别使用U盘

在过了一段时间后(大约半小时后),再插入U盘,要么没有反应,要么能识别出盘符,但是不能识别U盘内的东西。

重启系统后,还是在进入系统后能识别U盘,但过了一段时间,问题照旧。

哪位网友能给出解决方案?

本文由网站首页发布,转载请注明来源:24点算法之笔者见,又进步推了少数