消除类游戏算法相关内容

求,宝石方阵(宝石迷阵,蒙特祖玛的宝藏)这种游戏的核心算法!

4724

零用钱大作战的分数怎么计算?

11552

三消游戏如天天爱消除 的 算法 初学者 要详解

18403

7777随便怎么算等于24

各种算法如下:

(7³-7)÷(7+7)=24

(lg(7÷7%)+lg(7÷7%))!=24

(77÷7-7)!=24(“!”为阶乘  4的阶乘=1×2×3×4=24(N的阶乘定义为:N!=1×2×3.....×N)

∑ 7/7=1 ∑n(1≤n≤7)=28 28/7=4 4!=24(求和函数)

【(7')!+(7')!+(7')!+(7')!】!=【0!+0!+0!+0!】!=(1+1+1+1)!=4!=24

24点游戏及其算法

1.问题描述

24点是类益智游戏,要求结果等于二十四,一起来玩玩吧!这个游戏用扑克牌更容易来开展。拿一副牌,抽去大小王后(初练也可以把J/Q/K也拿去),剩下1~10这40张牌(以下用1代替A)。任意抽取4张牌(称为牌组),用加、减、乘、除(可加括号)把牌面上的数算成24。每张牌必须且只能用一次。如抽出的牌是3、8、8、9,那么算式为(9-8)×8×3=24

这里对问题进行扩展,可以输入的牌数为4~52张,其均属于一副牌,那么需要计算一串输入卡牌能否计算出24点,并且输入运算公式。

2.算法分析

其实有一个很简单的方式,深度优先搜索DFS,但是这个是很无脑的。这里就不作介绍了。没啥意思

(1)、首先我们要对这个问题进行数学抽象。

定义1:对于有理数组成的多重集合S ,f(S) 定义如下:

如果 S 是空集或只包含一个元素,则 f(S)=S ;否则 f(S)=∪ f( ( S-{r1, r2}) ∪ {r} ) ,对于每一个 r=r1+r2 , r1-r2 , r1×r2,r1÷r2(r2≠0),且r1, r2取遍 S 中所有元素的组成的二元组。

定义1说明:要计算集合S中的元素通过四则混合运算所能得到的所有值,我们只需要任取 S 中的两个元素 r1 , r2 ,分别计算 r1 , r2 的加减乘除运算,然后用所得的结果与 S 中剩下的其他数字进行四则混合运算。

只要取遍所有的 r1 ,r2 ,最后得到的所有结果的并集就是 S 中的元素通过四则混合运算所能得到的所有值的集合。根据上述定义,在本问题中,集合 S 就是由输入中给定的卡牌进行四则运算组成的集合

(2)、定义2:给定两个多重集合 S1 , S2,定义

comb( S1, S2 ) = ∪ { r1+r2 , r1-r2, r1×r2, r1÷r2(r2≠0) } 公式(1.1)

其中 ( r1 , r2 ) ∈ S1 × S2。

定义2实际上定义了两个集合中的元素两两进行加减乘除运算所能得到的结果集合。

(3)、那么其实就有一个定理:

对于有理数组成的多重集合 S ,如果 S 至少有两个元素,则

f(S)=∪ comb( f(S1), f(S - S1) )   定理(1.2)

其中 S1 取遍 S 的所有非空真子集。

利用上面的定义和定理,例如对于S={1,2,3,4},

f(S) = comb( f({ 1 }), f({ 2,3,4}) )∪ comb( f({ 2 }), f({ 1,3,4}) )… ∪ comb( f({ 1,2 }), f({3,4 }) ) ∪ …;

在这里的计算中,你会发现计算f({ 2,3,4})时需要计算一次f({ 3,4}),计算f({ 1,3,4})也需要计算一次f({ 3,4}),这样就产生了计算冗余。为了消除冗余,简单的方式就是记录已经计算过的,如果该集合之前已经计算过,直接使用即可。

为了表述方便,这里采用位域表示,这样就可以快速表示集合中有哪些数。譬如还是以上面的例子来说,n(S)=4,那么就需要用到四位,f[0001]=f[1]代表f({1}),f[0101]=f[5]=f({1,3})这样。那么f[2^ n - 1 ] (这里n=4)=f[15]=f[1111]=f({1,2,3,4})

那么防止重复计算,到这里也许就稍微清晰一点了,即存储中间结果,如果这个已经算过了,那么直接使用之前已经计算的结果来计算即可,不需再迭代计算。

(4)、循环方式:

定义计算集合计算符号X,即前面的comb(S1,S2)= f[S1]Xf[S2]

a. 先初始化f[xx1xxx]这种类型的集合,因为可以直接得到其结果 

b. 例如f[0011],即f[0001]Xf[0010]计算而来,并且将这个中间结果存储,同理可以算出f[0101]=f[0100]Xf[0001],和f[0110]

c. 那么f[0111]就可以通过f[0011]/f[0101]/f[0110]等集合算出

d. 以此类推算出f[1111]集合的数值

e. 判断全集是否有24的结果……

a-e中,已经大部分阐述了这个计算方式的思维,但是有一个细节没有说清楚,那就是,如何计算一个f[ m ] (m<2^n-1)

(5)、计算f[m] (m<2^n-1)

因为采用位域表示,那么设i从0开始,到m,

如果m&i=i(这里就说明i位域的元素是均属于m集合,那么就可以进行集合运算comb(或者说是X))

即计算f[i]Xf[m-i]

一直计算到i=m为止,到这里你会发现当m-i’ = i时,会有一次重复计算,所以这里只需要计算i < m-i的场景即可。

...

3055

数学24点游戏技巧是什么?

1、利用3×8=24、4×6=24、2×12=24求解。把牌面上的四个数想办法凑成3和8、4和6、2和12,再相乘求解。实践证明,这种方法是利用率最大、命中率最高的一种方法。

2、利用0、1的运算特性求解。如3、4、4、8可组成3×8×(4÷4)=24。又如4、7、1、1可组成4×1(7-1)×1=24。

3、若数中有2、12、4、6;3、8中的一个数,可用其他数凑成另一个数相乘。如3、6、7、7,可以用3×(7-6+7)或6×(3+7÷7)。

4、在计算过程中有较大数(30以上)出现。相对较难,但有时也只有该解法。比如(6,9,9,10)为9×10÷6+9。

5、若数中无这些数,可以两两结合得到这些数相乘。如5、1、7、1,可以用(5-1)×(7-1)或(5+7)×(1+1)。

6、在计算过程中有分数出现。有一个规律,设4个数为a,b,c,d。必有ab+c=24或ab-c=24 d=a或b。若d=a有a(b+c/a)=24或a(b-c/a)=24。只能用此法的只有17种。


...

9951

24点游戏技巧

16871