|
1.2.2 24点游戏算法（2） paper51.com 24点游戏的算法各种各样，各有千秋，现在让我们来讨论另一种24点游戏算法。此算法是在dos下实现的，但其思想明确，语句简短。其主要思想是简化算法，他将24点的算法排序分成如下几种，如下我们用a，b来代替变量。他将其分成如下6种情况，分别是a+b，a-b，b-a，a*b，a/b，b/a这6种情况，我们知道a+b和b+a是一样的，a*b和b*a是一样的。这样就可以省去2种算法。提高系统的使用效率，内存占用量小。还有其第2个思想是在判别24点正确与否的时候，采用了与24点相减绝对直在1E-6之外则判别其为正确，这就给运算带来了精确度，就如5 5 5 1等的数字也可以轻松算出，不会略过了。如下我们通过一段程序来看看其主程序段。 paper51.com bool Search(int n) 内容来自www.paper51.com { copyright paper51.com
if (n == 1) { http://www.paper51.com if (fabs(number[0] - NUMBER_TO_CAL) < PRECISION ) { 内容来自论文无忧网 www.paper51.com
cout << expression[0] << endl; copyright paper51.com return true; http://www.paper51.com
}else { 内容来自www.paper51.com
return false; 内容来自www.paper51.com } paper51.com } http://www.paper51.com for (int i =0; i < n; i++) { http://www.paper51.com
for(int j = i + 1; j < n; j++) { copyright paper51.com
double a, b; paper51.com string expa, expb; 内容来自论文无忧网 www.paper51.com a = number[i]; paper51.com
b = number[j]; copyright paper51.com number[j] = number[n - 1]; http://www.paper51.com expa = expression[i]; 内容来自www.paper51.com
expb = expression[j]; 内容来自www.paper51.com expression[j] = expression[n - 1]; 内容来自www.paper51.com expression[i] = '(' + expa + '+' + expb + ')'; 内容来自论文无忧网 www.paper51.com
number[i] = a + b; copyright paper51.com if ( Search(n - 1) ) return true; 内容来自www.paper51.com expression[i] = '(' + expa + '-' + expb + ')'; copyright paper51.com number[i] = a - b; paper51.com if ( Search(n - 1) ) return true; 内容来自www.paper51.com expression[i] = '(' + expb + '-' + expa + ')'; 内容来自论文无忧网 www.paper51.com number[i] = b - a; paper51.com if ( Search(n - 1) ) return true; 内容来自www.paper51.com
内容来自www.paper51.com expression[i] = '(' + expa + '*' + expb + ')'; copyright paper51.com number[i]= a * b; 内容来自论文无忧网 www.paper51.com if ( Search(n - 1) ) return true; 内容来自www.paper51.com if (b != 0) { 内容来自www.paper51.com
expression[i] = '(' + expa + '/' + expb + ')'; paper51.com number[i] = a / b; 内容来自www.paper51.com if ( Search(n - 1) ) return true; 内容来自论文无忧网 www.paper51.com } http://www.paper51.com if (a != 0) { 内容来自论文无忧网 www.paper51.com expression[i] = '(' + expb + '/' + expa + ')'; 内容来自www.paper51.com number[i] = b / a; 内容来自www.paper51.com if ( Search(n - 1) ) return true; 内容来自www.paper51.com } 内容来自论文无忧网 www.paper51.com number[i] = a; copyright paper51.com number[j] = b; paper51.com expression[i] = expa; http://www.paper51.com expression[j] = expb; 内容来自论文无忧网 www.paper51.com } paper51.com
} 内容来自www.paper51.com return false; copyright paper51.com } http://www.paper51.com 我们简单分析下以上的程序，我们可以清楚看到，SEARCH函数一个递归函数，其返回的是bool类型的值，其中number[0]为计算结果，假若其值和24相减为1E-6，则说明算法正确。其主要思想如下：首先我们取前面的两个数a,b对其进行相加，接着将两个相加的数结果存放于number[i]中，于是第2次循环的运算的时候，令其a= number[i]；则a成了原先的a和b之和，接着再将其存放于number[i]中，接着我们看到了程序中的递归函数SEARCH（n-1）。当调用递归函数的时候，我们可以看到其实现了所有数的相加，其中的n从原来的最大值4，经过递归达到2，最后生成4个数之和。接着就是递归函数的调用，假如number[i]其中i=0时，如果number[i]与24相减为零，则可以算出24点。如果，其返回直为否，则说明不能算出24点。则程序往下继续执行，接着是判断其他运算。同样的道理可以得出其返回值的正假，由此判断出24点的生成算法。注意假如我们只是简单的用计算结果和24相减为0则大错特错了，因为其中牵涉了到小数的问题。假如在运算中遇到了小数的式子不算，则此种判别是正确的，但24点游戏是允许中间过程存在有限小数，甚至是无限循环小数。因此要判断结果是否为24只能采用模糊的判别，即相减为1E-6之外，则说明其结果为24。 paper51.com 我们可以举个例子如5 5 5 1 ，其中的运算就牵涉到了小数，其算法为（5-1/5）*5。只要我们的判别是如以上程序的，则此算式将轻易的解出。还有一点就是，简化式子的算法。形如a+b和b+a是一样的，可以省略其中的一种。 内容来自论文无忧网 www.paper51.com
24点游戏的算法有多种多样，以上我只是简单对2种不同思想的算法做了简短的介绍，当然还有些算法也是大同小异，我们也不逐一列出了。介绍了24点算法后，接下来我们来探讨一下，一个有着纸牌图形界面的24点游戏将怎样完成。 paper51.com |