算法与acm

24点算法

2009年5月30日 阅读(26)

24点,是指给定4个数,和一个值,如何将这4个数通过+-*/得到这个值。
一个算法是这样的:4个数字组成一个表达式还需要3个运算符,这样我们只要把这7个元素的所有排列求出来,然后求值就可以了。
但是这个算法有三个问题:
1.这样的表示出来的序列并非全部是合法的表达式,比如3344+-*
2.实际的表达式可以加括号,但是这个也无法体现出来,而且表达式计算起来还要考虑优先级,转化为后缀表达式,当然这个括号我们可以通过枚举+-*/的优先级别来代替加括号
3.数字是不能重复选择的,而运算符则可以重复

用一个改进后的算法:
我们枚举后缀表达式的所有可能,同时注意数字是不能重复选择的,而运算符则可以重复,对于不重复选择的枚举,通常的解决方式是通过定义一个bool数组,来表示当前选择的集合。对于后缀表达式,只要保证每个位置数字个数总是大于运算符个数,那它就是合法的,这样合法性很容易验证,同时不用考虑优先级的问题了。

这样的一个算法,仍然有优化空间:
1.数字仍然可能重复,因此它们的可能排列实际上并没有4!那么多
2.+和*具有交换性,这样1+4和4+1,(14+,41+)实际上结果相同,但如果枚举仍然可能把它们都枚举一遍。

针对1,可以采取这样的策略,首先假设所有的数字都是一样的,进行枚举,对于每个枚举出来的排列,再根据实际的数字,枚举这个数字的排列,实际上是个双阶段枚举
针对2,用后缀表达式比较难表示,可以考虑用表达式树来表示表达式,通过枚举可能的树及树中节点元素的分配,来完成,这样就比较容易排除重复的组合

还有一个方法,dp:
这个针对另一个问题比较好,8个8如何通过通过+-*/得到一个值n。
n个8的可能运算结果可以用(1,n-1)…个8的可能运算结果组合出来。

24点算法实现:

#include <cstdio>
using namespace std;
int n = 8;
//计算后缀表达式的值
double computer(int a[],int n){
    /*
    int num_n = 0;
    int char_n = 0;
    for(int i = 0 ; i < n-1 ; i++){
        if(a[i] < 10)num_n++;
        else char_n++;
        if(char_n>=num_n)return -1;
    }
    if(num_n < 4) return -1;
    */
    double stack[10];
    int index = 0;
    double res = 0;
    for(int i = 0 ; i < n-1 ; i++){
        switch(a[i]){
            case ‘+’:
            res = stack[index]+ stack[–index];
            stack[index] = res;          
            break;
            case ‘-‘:
            res = stack[index-1]- stack[index];
            –index;
            stack[index] = res;          
            break;
            case ‘*’:
            res = stack[index]* stack[–index];
            stack[index] = res;          
            break;
            case ‘/’:
            if(stack[index] == 0.0)return -1;
            res = stack[index-1]/ stack[index];
            –index;
            stack[index] = res;          
            break;
            default:
            res = (double)a[i];
            stack[++index] = (double)a[i];
            ;
        }
        //printf("%lf ",res);

    }
    return res;
   

}

/*
//最初那个算法的实现,但这个算法是有问题的。
int a[] = {3,3,8,8,’+’,’-‘,’*’,’/’};
void perm(int a[],int i){
    if(i == n-1){
        double res = computer(a,n);    
        //if(res-24.0 < 0.01 && res-24.0 > -0.01){
        if(res != -1 && a[0] == 8){
        for(int j = 0 ; j < n-1 ; j++){
                if(a[j] < 10)
                printf("%c",a[j]+’0′);
                else
                printf("%c",a[j]);
               
        }
        printf(" %lf",res);
        printf("\n");
        }
        return;
    }
    for(int j = i ; j < n ; j++){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        perm(a,i+1);
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}
*/
int suffix_a[10];
bool num_selected[]={false,false,false,false};
int num[4] ={1,2,3,4};
int op[4] ={‘+’,’-‘,’*’,’/’};
void perm2(int suffix_a[],int index,bool num_selected[],int num_n){
    if(index >0 && num_n <= (index -num_n)) return;
    if(num_n > 4) return;
    if(index == n-1){
        double res = computer(suffix_a,n);    
        if(res-24.0 < 0.01 && res-24.0 > -0.01){
        //(res != -1 && suffix_a[0] == 8){
        for(int j = 0 ; j < n-1 ; j++){
                if(suffix_a[j] < 10)
                printf("%c",suffix_a[j]+’0′);
                else
                printf("%c",suffix_a[j]);
               
        }
        printf(" %lf",res);
        printf("\n");
        }
        return;
    }
    for(int i = 0; i < 4 ; i++){
        suffix_a[index] = op[i];
        perm2(suffix_a,index+1,num_selected,num_n);
    }
    for(int i = 0 ; i < 4 ; i++){
        if(num_selected[i] == false){
            suffix_a[index] = num[i];   
            num_selected[i] = true;
            perm2(suffix_a,index+1,num_selected,num_n+1);
            num_selected[i] = false;           
        }

    }
   
}
int main(){
   perm2(suffix_a,0,num_selected,0);
   while(true);

}

You Might Also Like

No Comments

Leave a Reply