算23 [EOlymp – 1540]题解

算23 [EOlymp – 1540]题解

给5个数字,判断这5人数通过加减乘法运算后能否算出23

解法很多,数据量不是特别大,所以直接搜索解空间(生成数组的全排列,然后遍历所有的运算)也能正确解答。
使用递归解决:给出了5个数,假设它的某个排列是[x1,x2,x3,x4,x5],要判断用这5个数计算23,只需要判断用[x1,x2,x3,x4]能否计算出23-x5,或能否算出23+x5,或者在23被x5整除的情况下能否算出23/x5(这分别代表[..]+5=23,[..]-5=23与[..]×5=23),这样问题的规模就减小到4个数。
再递归的做下去:用[x1,x2,x3]能否算出(23-x5)-x1,或者能否算出(23-x5)+x1,或是(23-x5)被x1整除的情况下能否算出(23-x5)/x1…最后当数组规模只剩1的时候,直接判断要计算的目标是不是数组里的这个数字即可,并且对初始的5个数的所有排列形式都分别递归。只要有任何一个递归函数最终达到了[x1]==计算目标,就返回true,将所有递归结果用“逻辑或”相连接。 

#include <cstdio>

void swap(int *x,int *y)
{
    if(*x!=*y)
    {
        *x^=*y;
        *y^=*x;
        *x^=*y;
    }
}

int f(int target,int *a,int N)
{
    int i,j;
   
    if(N==1)
        return a[0]==target;
    int *b;
    bool pr,mr,tr=false;
    b=new int [N];
    for(i=0;i<N;i++)
    {
        for(j=0;j<i;j++)
            b[j]=a[j];
        for(j=i+1;j<N;j++)
            b[j-1]=a[j];
        pr=f(target-a[i],b,N-1);
        mr=f(target+a[i],b,N-1);
        if(target%a[i]==0)
            tr=f(target/a[i],b,N-1);
        if(pr||mr||tr)
            break;
    }
    
    delete [] b;
    return pr||mr||tr;
}

int main(void)
{
    int i,a[5];
    bool bf;
    while(1)
    {
        bf=true;
        for(i=0;i<5;i++)
        {
            scanf("%d",a+i);
            if(a[i]>0)
                bf=false;
        }
        if(bf)
            break;

        if(f(23,a,5)==true)
            printf("Possible\n");
        else
            printf("Impossible\n");
    }

    return 0;
}

发表评论

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