Programming 版 (精华区)

发信人: zjliu (fly), 信区: Programming
标  题: 关于算24(转载)
发信站: 哈工大紫丁香 (2001年12月21日08:09:26 星期五), 转信

【 以下文字转载自 Math 讨论区 】
【 原文由 jiaxuan 所发表 】


/* 2个数时的最多种算法：6 */
/* 3个数时的最多种算法： */
/* C(3, 2) * 6 * C(2, 2) * 6 = 108 */
/* 全是乘除或加减的算法算了C(3, 2) * 3 * C(2, 2) * 3 * 2 = 54
/* 实际只有108 - (54 - 2 ^ 3 * 2 - 2) = 68 */
/* 4个数时的最多种算法： */
/* 实际只有3888 - (972 - 2 ^ 4 * 2 - 2) = 2918
/* 全是加减运算，15种算法，-a-b-c-d不算 */

关于算24，以四个数为例，其余可以类推：
最全面的考虑：
1.  运算一次少一个数，共有三次运算
2.  共有算法：
C(4, 2) * 6 * C(3, 2) * 6 * C(2, 2) * 6 = 3888 种
其中C(4, 2)表示从四个数中取两个数的组合数。
但是
全是乘除或加减的算法算了
C(4, 2) * 3 * C(3, 2) * 3 * C(2, 2) * 3 * 2 = 972 次
实际上只有 (2 ^ 4 - 1) * 2 = 30 次，多算972 - 30 = 942 次
因此最多只有
3888 - 942 = 2918 次
罗列的考虑：
四个数运算，只有三个运算符，只有在乘除与加减之间才有运算优先级的问题。
设加减操作为“+”运算，乘除操作为“*”运算。分为三种情况：
1. 全部是加减，或乘除：a+b+c+d, a*b*c*d
2. 一次加运算，两次乘运算:
   a+b*c*d (a+b)*c*d (a+b*c)*d
   a*b+c*d (a*b+c)*d a*(b+c)*d a*(b+c*d)
   a*b*c+d a*b*(c+d) a*(b*c+d)
   整理后仅得：a*b+c+d a*(b+c)+d a*(b+c+d) (a+b)*(c+d)四种形式
3. 一次乘运算，两次加运算：
   a*b+c+d a*(b+c)+d a*(b+c+d)
   a+b*c+d (a+b)*c+d (a+b)*(c+d) a+b*(c+d)
   a+b+c*d (a+b+c)*d a+(b+c)*d
   整理后仅得：a+b*c*d (a+b)*c*d a*b+c*d a*(b+c*d)四种形式
共10种运算形式，共有算法种数计算如下：
a+b+c+d : N(4)
a*b+c+d : C(4,2) * N(2) * N(3)
(a+b+c)*d : C(4,3) * N(3) * N(2)
(a+b)*(c+d) : C(4,2) * N(2) * N(2) * N(2) / 2
(a+b)*c+d : C(4,2) * N(2) * C(2,1) * N(2) * N(2)
(a*b+c)*d : C(4,2) * N(2) * C(2,1) * N(2) * N(2)
a*b+c*d : C(4,2) * N(2) * N(2) * N(2) / 2
a*b*c+d : C(4,3) * N(3) * N(2)
(a+b)*c*d : C(4,2) * N(2) * N(3)
a*b*c*d : N(4)
说明：a + b表示连加
      a * b表示连乘
      N(x)表示x个数连算的组合数, N(x) = 2 ^ x - 1
      比如 a + b的可能性有：
       a + b, a - b, -a + b 共 3 = 2 ^ 2 - 1种
      a + b + c的可能性有：
      a+b+c, a+b-c, a-b+c, a-b-c, -a+b+c, -a+b-c, -a-b+c 共 7 = 2 ^ 3 - 1种。
      因为是加减乘除，所以约定不可能有-a-b-c或/a/b/c这样的连加或连乘运算。
共有算法
(15 + 6 * 3 * 7 + 4 * 7 * 3 + 3 * 3 * 3 * 3 + 6 * 3 * 2 * 3 * 3) * 2
=1260种，
      

/*--------------------------------------------------*/
/* 用"."表示加减乘除的6种形式，"+"号表示加减方 */
/* 法的三种形式，"*"号表示乘除的三种形式。 */
/* 按原始规则减化。 */
/*--------------------------------------------------*/
两个数
(a)(b) ((a).(b)) 6
三个数
(a)(b)(c)
((a).(b))(c)
(((a).(b)).(c)) 6*6
((a).(c))(b)
(((a).(c)).(b)) 6*6
((b).(c))(a)
(((a).(c)).(b)) 6*6
四个数
(a)(b)(c)(d)
((a).(b))(c)(d)
(((a).(b)).(c))(d)
((((a).(b)).(c)).(d))
(((a).(b)).(d))(c)
((((a).(b)).(d)).(c))
((c).(d))((a).(b))
(((c).(d)).((a).(b)))
((a).(c))(b)(d)
(((a).(c)).(b))(d)
((((a).(c)).(b)).(d))
(((a).(c)).(d))(b)
((((a).(c)).(d)).(b))
((a).(c))((b).(d))
(((a).(c)).((b).(d)))
((a).(d))(b)(c)
(((a).(d)).(b))(c)
((((a).(d)).(b)).(c))
(((a).(d)).(c))(b)
((((a).(d)).(c)).(b))
((a).(d))((b).(c))
(((a).(d)).((b).(c)))
((b).(c))(a)(d)
(((b).(c)).(a))(d)
((((b).(c)).(a)).(d))
(((b).(c)).(d))(a)
((((b).(c)).(d)).(a))
((b).(c))((a).(d))
(((b).(c)).((a).(d)))
((b).(d))(a)(c)
(((b).(d)).(a))(c)
((((b).(d)).(a)).(c))
(((b).(d)).(c))(a)
((((b).(d)).(c)).(a))
((b).(d))((a).(c))
(((b).(d)).((a).(c)))
((c).(d))(a)(b)
(((c).(d)).(a))(b)
((((c).(d)).(a)).(b))
(((c).(d)).(b))(a)
((((c).(d)).(b)).(a))
((c).(d))((a).(b))
(((c).(d)).((a).(b)))

/*----------------------------------------------*/
/* "."号两边满足交换律，将相同的剔除 */
/* 共减少6*6*6*3 = 648种算法 */
/*----------------------------------------------*/
(((a.b).c).d)
(((a.b).d).c)
((c.d).(a.b))
(((a.c).b).d)
(((a.c).d).b)
((a.c).(b.d))
(((a.d).b).c)
(((a.d).c).b)
((a.d).(b.c))
(((b.c).a).d)
(((b.c).d).a)
((b.c).(a.d))
(((b.d).a).c)
(((b.d).c).a)
((b.d).(a.c))
(((c.d).a).b)
(((c.d).b).a)
((c.d).(a.b))

/*----------------------------------------------*/
/* 将所有形如(((a.b).c).d)的式子展开两步后 */
/* 得(a+b)+c 与算a+b+c的结果等同，但算法减少 */
/* 9-7 = 2种，同样 */
/* (a*b)*c与算a*b*c的结果相同，所以共计减少 */
/* 2*2*12 = 48种算法 */
/*----------------------------------------------*/
(((a.b).c).d)
(((a+b)+c).d)
(((a+b)*c).d)
(((a*b)+c).d)
(((a*b)*c).d)
(((a.b).d).c)
(((a.c).b).d)
(((a.c).d).b)
(((a.d).b).c)
(((a.d).c).b)
(((b.c).a).d)
(((b.c).a).d)
(((b.d).a).c)
(((b.d).c).a)
(((c.d).a).b)
(((c.d).b).a)
((c.d).(a.b))
((a.c).(b.d))
((a.d).(b.c))

/*----------------------------------------------*/
/* 所有"连+"或"连*"的算法满足交换律，将相同的 */
/* 剔除，共减少 */
/* 7*6*16=672种算法 */
/*----------------------------------------------*/
((a+b+c).d)
(((a+b)*c).d)
(((a*b)+c).d)
((a*b*c).d)
((a+b+d).c)
(((a+b)*d).c)
(((a*b)+d).c)
((a*b*d).c)
((a+c+b).d)
(((a+c)*b).d)
(((a*c)+b).d)
((a*c*b).d)
((a+c+d).b)
(((a+c)*d).b)
(((a*c)+d).b)
((a*c*d).b)

((a+d+b).c)
(((a+d)*b).c)
(((a*d)+b).c)
((a*d*b).c)

((a+d+c).b)
(((a+d)*c).b)
(((a*d)+c).b)
((a*d*c).b)

((b+c+a).d)
(((b+c)*a).d)
(((b*c)+a).d)
((b*c*a).d)

((b+c+a).d)
(((b+c)*a).d)
(((b*c)+a).d)
((b*c*a).d)

((b+d+a).c)
(((b+d)*a).c)
(((b*d)+a).c)
((b*d*a).c)

((b+d+c).a)
(((b+d)*c).a)
(((b*d)+c).a)
((b*d*c).a)

((c+d+a).b)
(((c+d)*a).b)
(((c*d)+a).b)
((c*d*a).b)

((c+d+b).a)
(((c+d)*b).a)
(((c*d)+b).a)
((c*d*b).a)

((c.d).(a.b))
((a.c).(b.d))
((a.d).(b.c))
/*----------------------------------------------*/
/* 将所有形如(((a+b)*c).d)的式子展开，由于 */
/* (((a+b)*c)*d)与((a+b)*c*d)所得结果相同，但 */
/* 算法减少3*3*3 - 3*7 = 6种，同样将形如 */
/* (((a*b)+c).d)的式子展开，而 */
/* (((a*b)+d)+d)与(a*b+c+d)所得结果相同，算法 */
/* 也减少3*3*3 - 3*7 = 6种。它们是同类算式。 */
/* 该类算式共计减少算法 */
/* 6*24 = 144种 */
/* 该类式子已经完全展开，形式相同的算法个数相 */
/* 同，不再罗列，仅以倍乘标识。 */
/* 同时形如(a*b+c+d)的式子有重复，删除重复的 */
/* 3*7*24/2 = 252种 */
/*----------------------------------------------*/
((a+b+c).d)
((a*b*c).d)
((a+b+d).c)
((a*b*d).c)
((a+c+d).b)
((a*c*d).b)
((b+d+c).a)
((b*d*c).a)
(((a+b)*c).d)
(((a+b)*c)+d)
(((a+b)*c)*d)
(((a*b)+c).d)
(((a*b)+c)+d)
(((a*b)+c)*d)
(((a+b)*d).c)
(((a+b)*d)+c)
(((a+b)*d)*c)
(((a*b)+d).c)
(((a*b)+d)+c)
(((a*b)+d)+c)
(((a+c)*b).d)
(((a*c)+b).d)
(((a+c)*d).b)
(((a*c)+d).b)
(((a+d)*b).c)
(((a*d)+b).c)
(((a+d)*c).b)
(((a*d)+c).b)
(((b+c)*a).d)
(((b*c)+a).d)
(((b+c)*a).d)
(((b*c)+a).d)
(((b+d)*a).c)
(((b*d)+a).c)
(((b+d)*c).a)
(((b*d)+c).a)
(((c+d)*a).b)
(((c*d)+a).b)
(((c+d)*b).a)
(((c*d)+b).a)
((c.d).(a.b))
((a.c).(b.d))
((a.d).(b.c))
/*----------------------------------------------*/
/* 将所有形如(a+b+c).d的式子展开，与上类推， */
/* 共减少算法 */
/* (7*3-15)*8 = 48种算法 */
/* 再减去重复的a+b+c+d，计15*3*2 = 90种算法 */
/*----------------------------------------------*/
((a+b+c).d)
((a+b+c)+d)
((a+b+c)*d)
((a*b*c).d)
((a*b*c)+d)
((a*b*c)*d)
((a+b+d).c)
((a*b*d).c)
((a+c+d).b)
((a*c*d).b)
((b+d+c).a)
((b*d*c).a)

((a+b)*c+d) 12
(a*b+c+d) 12
(((a+b)*c*d) 12
((a*b+c)*d) 12

((c.d).(a.b))
((a.c).(b.d))
((a.d).(b.c))
/*----------------------------------------------*/
/* 将所有形如的式子((c.d).(a.b))展开，得 */
/* ((c+d)+(a+b))与(a+b+c+d)结果相同，同样 */
/* ((c*d)*(a*b))与(a*b*c*d)结果相同，剔除之， */
/* 算法减少 3*3*3*2*3 = 162种 */
/* (3*3*3-15)*2*3 = 60种算法 */
/* 另外((c+d)+(a*b))与(c+d+a*b)结果相同，剔除 */
/* 之，共减少算法 */
/* 3*3*3*4*3=324种算法 */
/*----------------------------------------------*/
(a+b+c+d)
(a*b*c*d)
((a+b+c)*d) 4
(a*b*c+d) 4
((a+b)*c+d) 12
(a*b+c+d) 12
(((a+b)*c*d) 12
((a*b+c)*d) 12

((c.d).(a.b))
((c+d)+(a+b))
((c+d)*(a+b))
((c+d)+(a*b))
((c+d)*(a*b))
((c*d)+(a+b))
((c*d)*(a+b))
((c*d)+(a*b))
((c*d)*(a*b))
((a.c).(b.d))
((a.d).(b.c))
/*----------------------------------------------*/
/* 最后共有算法 */
/* 15*2+7*3*8+3*3*3*24+3*7*12+3*3*3*6 */
/* = 1260种 */
/*----------------------------------------------*/
(a+b+c+d)
(a*b*c*d)
((a+b+c)*d) 4
(a*b*c+d) 4
((a+b)*c+d) 12
(a*b+c+d) 6
(((a+b)*c*d) 6
((a*b+c)*d) 12
((c+d)*(a+b)) 3
(c*d+a*b) 3
这是一致的。


--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 218.2.150.6]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.229.86]