【NYOJ43】24点游戏 扩展版 同样利用昨天写的后缀法求值

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 08 日

http://acm.nyist.net/JudgeOnline/problem.php?pid=43
后缀法求值(http://blog.csdn.net/hzyhouzhiyuan/archive/2011/03/07/6229897.aspx),该方法不一定最适合这个题,但同样条例十分清晰简单,适合初学,该题还有另外一种高效的方法,简单说一下,比如有4个数,然后枚举出两个数再枚举一个运算符使4个数变成3个数,然后继续这样,最后变成1个数看是否为所有结果,该方法代码书写较繁琐,并且不容易得到所有种情况的

/* 
*该题还是应用表达式求值的后缀方法求解的,虽然该题用来不是那么方便, 
*但是能够很方便的给出所有种情况的后缀表达式,在这种题的变形中将得到很好的应用。 
*如果不太了解后缀法求解请看文档: 
*http://blog.csdn.net/hzyhouzhiyuan/archive/2011/03/07/6229897.aspx 
*/  
#include<iostream>  
#include<algorithm>  
#include<stack>  
#include<cstring>  
#include <iterator>  
using namespace std;  
//根据给的数值个数罗列的各种情况的地图  
int map[8][6]={  
    {2,0,1,1,1,1},  
    {3,0,0,2,1,1},  
    {4,0,0,1,2,1},  
    {4,0,0,0,3,1},  
    {5,0,0,1,1,2},  
    {5,0,0,0,2,2},  
    {5,0,0,0,1,3},  
    {5,0,0,0,0,4}  
};  
int res[10],nums[10];  
int n,sum,count_int,flag;  
stack<double> sta;  
//递归枚举所有位置的运算符号  
void calculation(int relational[],int n)  
{  
    //-1->+,-2->-,-3->*,-4->/  
    if(n == (count_int-1))  
    {  
        //得到一种后缀表达式求解  
        for (int i=0;i<=2*(count_int-1);i++)  
        {  
            if(res[i]>=0)  
                sta.push(nums[res[i]]);  
            else  
            {  
                double t1,t2;  
                t1=sta.top();  
                sta.pop();  
                t2=sta.top();  
                sta.pop();  
                switch(res[i])  
                {  
                    case -1:sta.push(t2+t1);break;  
                    case -2:sta.push(t2-t1);break;  
                    case -3:sta.push(t2*t1);break;  
                    case -4:sta.push(t2/t1);break;  
                }  
            }  
        }  
        if( (sta.top()-sum<1e-6 && sta.top()-sum>-1e-6) && flag==0)  
        {  
            cout<<"Yes"<<endl;  
            flag=1;  
            return;  
            /*copy(res,res+2*count_int-1,ostream_iterator<int>(cout," ")); 
            cout<<endl;*/  
        }  
        return;  
    }  
    //枚举运算符得到一种后缀表达式  
    for (int j=1;j<=4;j++)  
    {  
        int x=2*n;  
        for (;x<=count_int*2-1;x++)  
        {  
            if(res[x]==-5)  
            {  
                res[x]=-j;  
                break;  
            }  
        }  
        calculation(relational,n+1);  
        res[x]=-5;  
    }  
}  
int main()  
{  
    、、freopen("1.txt","r",stdin);  
    int relational[10]={0,1,2,3,4,5,6,7,8,9};  
    cin>>n;  
    while(n--)  
    {  
        flag=0;  
        cin>>count_int>>sum;  
        for (int i=0;i<count_int;i++)  
            cin>>nums[i];  
        if(count_int==1)  
        {  
            if(nums[0]==sum)  
            cout<<"Yes"<<endl;  
            else cout<<"No"<<endl;  
            continue;  
        }  
        //枚举全排列  
        do   
        {     
            for (int i=0;i<=7;i++)  
            {  
                memset(res,0,sizeof(res));  
                if(map[i][0]>count_int) break;  
                int tem=0;  
                for (int j=1;j<=count_int;j++)  
                {  
                    res[tem++]=relational[j-1];  
                    switch(map[i][j])  
                    {  
                        case 4:res[tem++]=-5;  
                        case 3:res[tem++]=-5;  
                        case 2:res[tem++]=-5;  
                        case 1:res[tem++]=-5;  
                        default:break;  
                    }     
                }  
                calculation(relational,0);  
            }  
        }while(next_permutation(relational,relational+count_int));  
        if(flag!=1) cout<<"No"<<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日