首页 > 代码库 > nyoj 24 Point game

nyoj 24 Point game

2024-08-09 08:13:01   219人阅读

/*
题意：输入有t组 每组的n，m和n个数，问这n个数是否经过运算后是否和m相等，n个数的位置可调换
搜索大体思路：把n个数经过一次运算后话为n-1向下搜索
*/
#include<stdio.h>
const double E=1e-9;
int n;
double v,num[7];
double fac(double aa)
{
    if(aa>v)
        return aa-v;
    else
        return v-aa;
}
int dfs(int t)
{
    if(t==n)//实数判断相等看精度
    {
        if(fac(num[n])<E)
            return 1;
    }
    double right,left;
    for(int i=t;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            left=num[i];
            right=num[j];
            num[i]=num[t];//我们把num[i]和num[j]的值存到num[j]中num[i]就没有用了，当i和t不相等时把num[t]的值存到num[i]，因为这个时候num[t]这个数没有使用。这样经过一次运算就减少了一个数
            num[j]=left+right;//加
            if(dfs(t+1))
                return 1;
            num[j]=left-right;//减
            if(dfs(t+1))
                return 1;
            num[j]=right-left;//减
            if(dfs(t+1))
                return 1;
            num[j]=right*left;//乘
            if(dfs(t+1))
                return 1;
            if(right)//除
            {
                num[j]=left/right;
                if(dfs(t+1))
                    return 1;
            }
            if(left)//除
            {
                num[j]=right/left;
                if(dfs(t+1))
                    return 1;
            }
            num[i]=left;//还原
            num[j]=right;
        }
        return 0;
}
int main()
{
    int i,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lf",&n,&v);
        for(i=1;i<=n;i++)
            scanf("%lf",&num[i]);
        if(dfs(1))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

nyoj 24 Point game


联系
我们