| [这个贴子最后由bigblock在 2003/11/16 01:07pm 第 1 次编辑]
主体函数：
/*=========================================================================
函数功能：经典游戏24点经典算法
算法原理：一.首先想到的是用穷举表达式的方法，然后求值。
然而，由于括号的存在，使穷举表达式并非易事。
实际上，括号的作用仅仅是提高运算的优先级而已，
如果我们规定符号的优先级，一样可以达到要求。
具体来说，设四个数为a、b、c、d，运算符为①、②、③，
表达式为a ① b ② c ③ 。
如果强制规定①、②、③的优先顺序，就不必考虑括号问题了。
而这3个运算符的运算顺序有3！=6种，分别是：
1.①②③ 2.①③② 3.②①③
4.②③① 5.③①② 6.③②①
等价的表达式分别是：
1.((a＠b)＠c)＠d 2.(a＠b)＠(c＠d) 3.(a＠(b＠c))＠d
4.a＠((b＠c)＠d) 5.(a＠b)＠(c＠d) 6. a＠(b＠(c＠d))
显然，2和5是相同的，因此只考虑5种情况。这样，括号的问题就解决了。
二.接下来，就是生成a、b、c、d的全排列，注意去掉其中的相同排列
三.对这组排列进行以上方法的运算，就可以得到所有的结果了。
注意在运算过程中除法的特殊性--除数不能为零。因为可能会用到除法，
所以要考虑精度问题，这里通过结果减去24取绝对值与一个接近0（zero）
的小数比较，如小于它，即可判定结果是24。
四.有待解决的问题：
1、形式不同而实质相同的解的问题。有些解虽然形式不同，但其实质是完全相同的。
如3*((11+4)-7)和3*(11+(4-7))，实际上只是一种解。去掉这些相同解的问题情况较多，
其较为繁琐，有待解决。
2、多余括号问题。有些解的括号是多余的，应在输出前去掉。
五.优化改进方案：
经过对上面的5个算式的深入分析，重新优化为下面的5个算式：
1.(A+-B)X/(C+-X/D)
其中②为X，③为X/时，则这种情况和第2算式重复，忽略
2.(A+-X/B)X/C+-X/D
3.(A+-X/B+-X/C)+-X/D
其中①为X,②为X/时，则这种情况和第2算式重复，忽略
4.A-/(B+-X/C+-X/D)
5.AX/B+-CX/D
以此较好的解决了上面提出的两个待解决的问题。
程序中称前面的5个算式为原始方案，后面5个算式为优化改进方案。
函数参数：as_1 decimal value 第一个数；
as_2 decimal value 第二个数；
as_3 decimal value 第三个数；
as_4 decimal value 第四个数；
as_5 decimal value 需要求出的结果值
as_result_total integer value 需要求出的求解方案数(0=求出所有的求解方案)
as_return_result[] string reference 求得的算式字符串数组
调用详解:1.必须定义的变量 string as_return_result[]
2.as_return_result切勿赋值
3.把需要计算的数和结果值分别赋值给as_1、as_2、as_3、as_4、as_5
4.调用本函数f_calc_24(as_1,as_2,as_3,as_4,as_5,0,as_return_result)
5.as_return_result[]就是求得的算式字符串数组
返回代码：>=0 求得的解题方案数
<0 error
附：著名的题目
5 5 5 1 ＝24
8 8 3 3 ＝24
实际使用代码演示：
//计算：3,5,6,9＝24 的5种求解方案
string as_return_result
f_calc_24(3,5,6,9,24,5,as_return_result)
//接下去是对数组as_return_result[]进行处理，输出、打印........
//程序略
=========================================================================*/
string ls_st,operate,ls_bracket[7]
int ls_arrange[24,4],k,i,t,op1,op2,op3,total,n1,n2,n3,n4,fg1,fg2
dec answer1,answer2,answer3,zero
//初始化
//原始方案
fg1=1
fg2=5
//优化方案
fg1=6
fg2=10
zero = 0.00001
operate='＋－×／'
//初始化end
if as_4=-99999988009.0 then //内部函数，使两个函数并为一个函数
dec answer
choose Case as_3
Case 1
answer =as_1+as_2
Case 2
answer =as_1 -as_2
Case 3
answer =as_1*as_2
Case 4
If as_2= 0 Then
answer = -999888.89
Else
answer =as_1/as_2
End If
case else
answer = -999888.89
end choose
return answer
end if //内部函数结束
// 产生24种全排列
int card[4]
card={as_1,as_2,as_3,as_4}
For n1 = 1 To 4
For n2 = 1 To 4
If n2 = n1 Then continue
For n3 = 1 To 4
If n3 = n1 Or n3 = n2 Then continue
n4 = 10 - n1 - n2 - n3
t=0 //寻找重复的排列
for k=1 to 24
if string(ls_arrange[k,1])+string(ls_arrange[k,2])+string(ls_arrange[k,3])+string(ls_arrange[k,4])=string(card[n1])+string(card[n2])+string(card[n3])+string(card[n4]) then
t=1
exit
end if
next //寻找结束，t＝0不重复
if t=0 then
i = i + 1
ls_arrange[i, 1] = card[n1]
ls_arrange[i, 2] = card[n2]
ls_arrange[i, 3] = card[n3]
ls_arrange[i, 4] = card[n4]
end if
Next
Next
Next
//全排列 结束
k=i
for i=1 to k
For op1 = 1 To 4
For op2 = 1 To 4
For op3 = 1 To 4
for t= fg1 to fg2 //使用优化方案 6 to 10
//使用原始方案 1 to 5
choose case t
case 1//(( a ＠ b ) ＠ c ) ＠ d
answer1 = f_calc_24(ls_arrange[i,1], ls_arrange[i,2], op1,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(answer1, ls_arrange[i,3], op2,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer2, ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
ls_bracket={"((","",")","",")","",""}
case 2//( a ＠ b ) ＠ (c ＠ d)
answer1 = f_calc_24(ls_arrange[i,1], ls_arrange[i,2], op1,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(ls_arrange[i,3], ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer1, answer2, op2,-99999988009.0,0,0,as_return_result)
ls_bracket={"(","",")","(","","",")"}
case 3//( a ＠ ( b ＠ c ) ) ＠ d
answer1 = f_calc_24(ls_arrange[i,2], ls_arrange[i,3], op2,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(ls_arrange[i,1], answer1, op1,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer2, ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
ls_bracket={"(","(","","","))","",""}
case 4// a ＠ ( ( b ＠ c ) ＠ d )
answer1 = f_calc_24(ls_arrange[i,2], ls_arrange[i,3], op2,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(answer1, ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(ls_arrange[i,1], answer2, op1,-99999988009.0,0,0,as_return_result)
ls_bracket={"","((","","",")","",")"}
case 5 //a ＠ ( b ＠ ( c ＠ d ) )
answer1 = f_calc_24(ls_arrange[i,3], ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(ls_arrange[i,2], answer1, op2,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(ls_arrange[i,1], answer2, op1,-99999988009.0,0,0,as_return_result)
ls_bracket={"","(","","(","","","))"}
//下面为优化方案
case 6 //(A+-B)X/(C+-X/D)
if op2=1 or op2=2 or op1=3 or op1=4 then continue
if op2=3 and (op3=3 or op3=4) then continue //其中②为X，③为X/时，忽略
answer1 = f_calc_24(ls_arrange[i,1], ls_arrange[i,2], op1,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(ls_arrange[i,3], ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer1, answer2, op2,-99999988009.0,0,0,as_return_result)
ls_bracket={"(","",")","(","","",")"}
case 7 //(A+-X/B)X/C+-X/D
if op2=1 or op2=2 then continue
answer1 = f_calc_24(ls_arrange[i,1], ls_arrange[i,2], op1,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(answer1, ls_arrange[i,3], op2,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer2, ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
ls_bracket={"(","",")","","","",""}
case 8 //(A+-X/B+-X/C)+-X/D
if op1=3 and (op2=3 or op2=4) then continue //其中①为X,②为X/时，忽略
if op2=1 or op2=2 then
answer1 = f_calc_24(ls_arrange[i,1], ls_arrange[i,2], op1,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(answer1, ls_arrange[i,3], op2,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer2, ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
else
answer1 = f_calc_24(ls_arrange[i,2], ls_arrange[i,3], op2,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(ls_arrange[i,1],answer1, op1,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer2, ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
end if
ls_bracket={"(","","","",")","",""}
case 9 //A-/(B+-X/C+-X/D)
if op1=1 or op1=3 then continue
if op3=1 or op3=2 then
answer1 = f_calc_24(ls_arrange[i,2], ls_arrange[i,3], op2,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(answer1, ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(ls_arrange[i,1],answer2, op1,-99999988009.0,0,0,as_return_result)
else
answer1 = f_calc_24(ls_arrange[i,3], ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(ls_arrange[i,2], answer1, op2,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(ls_arrange[i,1], answer2, op1,-99999988009.0,0,0,as_return_result)
end if
ls_bracket={"","(","","","","",")"}
case 10 //AX/B+-CX/D
if op2=3 or op2=4 or op1=1 or op1=2 or op3=1 or op3=2 then continue
answer1 = f_calc_24(ls_arrange[i,1], ls_arrange[i,2], op1,-99999988009.0,0,0,as_return_result)
answer2 = f_calc_24(ls_arrange[i,3], ls_arrange[i,4], op3,-99999988009.0,0,0,as_return_result)
answer3 = f_calc_24(answer1, answer2, op2,-99999988009.0,0,0,as_return_result)
ls_bracket={"","","","","","",""}
end choose
If answer1 <> -999888.89 And answer2 <> -999888.89 And answer3 <> -999888.89 Then
If Abs(answer3 - as_5) < zero Then
total = total + 1
as_return_result[total] = ls_bracket[1] + string(ls_arrange[i,1]) + mid(operate,op1*2 -1,2) +ls_bracket[2]+ String(ls_arrange[i,2]) + ls_bracket[3] + mid(operate,op2*2 -1,2) +ls_bracket[4]+ String(ls_arrange[i,3]) + ls_bracket[5] + mid(operate,op3*2 -1,2) +ls_bracket[6]+ String(ls_arrange[i,4]) +ls_bracket[7]
if total>=as_result_total and as_result_total>0 then return total
End If
End If
next
next
next
next
next
return total
|
