首页 > 代码库 > UVA 23 Out of 5（DFS+回溯）

UVA 23 Out of 5（DFS+回溯）

2024-11-17 14:27:02   202人阅读

Problem I

23 Out of 5

Input: standard input

Output: standard output

Time Limit: 1 second

Memory Limit: 32 MB

Your task is to write a program that can decide whether you can find an arithmetic expression consisting of five given numbers 技术分享(1<=i<=5) that will yield the value 23.
For this problem we will only consider arithmetic expressions of the following from:

技术分享
            
where 技术分享: {1,2,3,4,5} -> {1,2,3,4,5} is a bijective function 
and 技术分享 {+,-,*} (1<=i<=4)

Input

The Input consists of 5-Tupels of positive Integers, each between 1 and 50.
Input is terminated by a line containing five zero‘s. This line should not be processed.

Output

For each 5-Tupel print "Possible" (without quotes) if their exists an arithmetic expression (as described above) that yields 23. Otherwise print "Impossible".

Sample Input

1 1 1 1 1 
1 2 3 4 5 
2 3 5 7 11 
0 0 0 0 0

Sample Output

Impossible 
Possible 
Possible

Thomas Strohmann



     题意：给出5个数，进行加，减，乘的运算使得最后的结果为23（会有括号的存在，因为这个原因WA了好几次）

     两种方法可以求做，可以用DFS+回溯或者全排列+DFS，

DFS+回溯：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

using namespace std;

int a[10];
int flag;
int v[10];

void DFS(int sum,int p)
{
    if(flag == 1)
    {
        return ;
    }
    if(p == 5)
    {
        if(sum == 23)
        {
            flag = 1;
        }
        return ;
    }
    for(int i=0;i<5;i++)
    {
        if(v[i] == 0)
        {
            v[i] = 1;
            DFS(sum+a[i],p+1);
            DFS(sum-a[i],p+1);
            DFS(sum*a[i],p+1);
            v[i] = 0;
        }
    }
}

int main()
{
    while(scanf("%d",&a[0])!=EOF)
    {
        for(int i=1;i<5;i++)
        {
            scanf("%d",&a[i]);
        }
        int t = 0;
        for(int i=0;i<5;i++)
        {
            if(a[i] == 0)
            {
                t++;
            }
        }
        if(t == 5)
        {
            break;
        }

        flag = 0;
        for(int i = 0;i<5;i++)
        {
            if(flag == 1)
            {
                break;
            }
            memset(v,0,sizeof(v));
            v[i] = 1;
            DFS(a[i],1);
        }

        if(flag == 1)
        {
            printf("Possible\n");
        }
        else
        {
            printf("Impossible\n");
        }
    }
    return 0;
}



DFS+全排列

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

using namespace std;

int a[10];
int flag;

void DFS(int sum,int p)
{
    if(p == 5)
    {
        if(sum == 23)
        {
            flag = 1;
        }
        return ;
    }
    for(int i=0; i<3; i++)
    {
        if(i == 0)
        {
            DFS(sum + a[p],p+1);
        }
        else if(i == 1)
        {
            DFS(sum - a[p],p+1);
        }
        else if(i == 2)
        {
            DFS(sum * a[p],p+1);
        }
    }
}

int main()
{
    while(scanf("%d",&a[0])!=EOF)
    {
        for(int i=1; i<5; i++)
        {
            scanf("%d",&a[i]);
        }
        int t = 0;
        for(int i=0;i<5;i++)
        {
            if(a[i] == 0)
            {
                t++;
            }
        }
        if(t == 5)
        {
            break;
        }
        flag = 0;
        sort(a,a+5);
        do
        {
            DFS(a[0],1);
        }
        while (next_permutation(a,a+5)&&!flag);
        if(flag == 1)
        {
            printf("Possible\n");
        }
        else
        {
            printf("Impossible\n");
        }
    }
    return 0;
}

UVA 23 Out of 5（DFS+回溯）


联系
我们