POJ[산24]--귀속 연습
2653 단어 반복 연습
POJ: 계산 24
설명은 10개보다 작은 4개의 정수를 보여 줍니다. 4가지 연산과 괄호를 더하기 곱해서 이 4개의 수를 연결하여 표현식을 얻을 수 있습니다.현재의 문제는 표현식의 결과가 24와 같을 수 있는 방식이 존재하는지 여부다.
여기에 더하기 곱하기 및 괄호의 연산 결과와 연산의 우선순위는 우리의 일반적인 정의와 일치한다. (이곳의 제법 정의는 실수 제법이다.)
예를 들어 5, 5, 5, 5, 1에 대해 우리는 5*(5-1/5) = 24를 알고 있기 때문에 24를 얻을 수 있다.또 예를 들어 1, 1, 4, 2에 대해 우리는 어떻게 해도 24를 얻지 못한다.
입력 입력 데이터는 여러 줄을 포함하고, 줄마다 테스트 데이터를 한 조로 제공하며, 4개가 10개보다 작은 정수를 포함한다.마지막 테스트 데이터에는 4개의 0이 포함되어 있으며, 입력의 끝을 표시하며, 이 데이터는 처리할 필요가 없다.출력은 매 그룹의 테스트 데이터에 대해 한 줄을 출력하고 24를 얻을 수 있다면'YES'를 출력한다.그렇지 않으면 "NO"를 출력합니다.샘플 입력5 5 5 1
1 1 4 2
0 0 0 0
샘플 출력YES
NO
=========================================================================
이 문제를 받으면 주어진 산식의 모든 상황을 어떻게 궁리해야 할지 모르겠다.문제 풀이를 보았다.
길이가 4인 산식에 대해 우리는 먼저 2개의 수를 꺼내서 연산할 수 있다. 그 다음에 4개의 수는 3개의 수가 되고 그 다음에 3→2,2→1이 된다.1곳에서 판단하고 퇴소하다.그 다음으로 꺼낸 두 수에 대해 우리는'+-*/'4가지 연산이 있지만 실제로는 6가지,'-'는 2가지,'/'는 2가지가 있다. 그리고 우리는 이 6가지 연산을 각각 귀속시키면 된다.마지막으로 주의해야 할 것은 다음과 같다.
① 제법 연산을 할 때 우리는 분모가 0인지 아닌지를 판단해야 한다.
② 제목은 제법 연산을 실수 연산으로 요구하므로 최종 판단 결과가 24인지 아닌지는 <=1e-6로 판단해야 한다.
AC 코드:#include
using namespace std;
bool search(double a[],int x) // , , ;
{
if(x==1&&fabs(a[1]-24)<=1e-6)return 1; // ;
double b[6]; // ;
memset(b,0,sizeof(b));
for(int i=1;i<=x-1;++i)
for(int j=i+1;j<=x;++j)
{
int p=1;
for(int k=1;k<=x;++k)
{
if(k!=i&&k!=j)
{
b[p++]=a[k];
}
}
b[p]=a[i]+a[j]; if(search(b,x-1))return 1;// , ;
b[p]=a[i]*a[j]; if(search(b,x-1))return 1;// , :return search(b,x-1);
b[p]=a[i]-a[j]; if(search(b,x-1))return 1;
b[p]=a[j]-a[i]; if(search(b,x-1))return 1;
if(a[j]!=0)
{
b[p]=a[i]/a[j];
if(search(b,x-1))return 1;
}
if(a[i]!=0)
{
b[p]=a[j]/a[i];
if(search(b,x-1))return 1;
}
}
return 0;
}
int main()
{
while(1)
{
double a[6];
memset(a,0,sizeof(a));
int sum=0;
for(int i=1;i<=4;++i)
{
cin>>a[i];
sum+=a[i];
}
if(sum==0)break;
bool flag=search(a,4);
if(flag==1)cout<
5 5 5 1
1 1 4 2
0 0 0 0
YES
NO
#include
using namespace std;
bool search(double a[],int x) // , , ;
{
if(x==1&&fabs(a[1]-24)<=1e-6)return 1; // ;
double b[6]; // ;
memset(b,0,sizeof(b));
for(int i=1;i<=x-1;++i)
for(int j=i+1;j<=x;++j)
{
int p=1;
for(int k=1;k<=x;++k)
{
if(k!=i&&k!=j)
{
b[p++]=a[k];
}
}
b[p]=a[i]+a[j]; if(search(b,x-1))return 1;// , ;
b[p]=a[i]*a[j]; if(search(b,x-1))return 1;// , :return search(b,x-1);
b[p]=a[i]-a[j]; if(search(b,x-1))return 1;
b[p]=a[j]-a[i]; if(search(b,x-1))return 1;
if(a[j]!=0)
{
b[p]=a[i]/a[j];
if(search(b,x-1))return 1;
}
if(a[i]!=0)
{
b[p]=a[j]/a[i];
if(search(b,x-1))return 1;
}
}
return 0;
}
int main()
{
while(1)
{
double a[6];
memset(a,0,sizeof(a));
int sum=0;
for(int i=1;i<=4;++i)
{
cin>>a[i];
sum+=a[i];
}
if(sum==0)break;
bool flag=search(a,4);
if(flag==1)cout<