算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;
}