程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA - 817 According to Bartjens 暴力

UVA - 817 According to Bartjens 暴力

編輯：C++入門知識

UVA - 817 According to Bartjens 暴力

題目大意：給出一個字符串，要求你在這個字符串裡面加入符號，使得結果為2000

解題思路：直接暴力

#include
#include
#include
#define maxn 30
using namespace std;
char str[maxn];
bool flag;
int num[maxn], sign[maxn], len;
char s[5]= " *+-";

bool judge(int num_s, int num_n) {

    vector Num, Sign;

    for(int i = 0; i < num_s; i++)
        Sign.push_back(sign[i]);
    for(int i = 0; i < num_n; i++)
        Num.push_back(num[i]);
    for(int i = 0; i < Sign.size(); i++)
        if(Sign[i] == 1) {
            Num[i + 1] *= Num[i];
            Num.erase(Num.begin() + i);
            Sign.erase(Sign.begin() + i);
            i--;
        }

    int t = Num[0];
    for(int i = 0; i < Sign.size(); i++)
        if(Sign[i] == 2)
            t += Num[i + 1];
        else
            t -= Num[i + 1];
    return t == 2000;
}

void dfs(int cur, int cur_sign, int cur_num) {
    if(cur == len - 1) {
        if(judge(cur_sign, cur_num)) {
            flag = true;
            printf("  ");
            for(int i = 0; i < cur_num - 1; i++)
                printf("%d%c", num[i], s[sign[i]]);
            printf("%d=\n",num[cur_num - 1]);
        }
        return;
    }

    int t = 0;
    for(int i = cur ; i < len - 1; i++) {
        if(i == cur && str[i] == '0') {
            num[cur_num] = 0;
            if(i != len - 2) {
                for(int j = 1; j <= 3; j++) {
                    sign[cur_sign] = j;
                    dfs(i + 1, cur_sign+1, cur_num+1);
                }
            }
            else
                dfs(i + 1, cur_sign, cur_num + 1);
            break;
        }
        t = t * 10 + str[i] - '0';
        num[cur_num] = t;
        if(i != len - 2) {
            for(int j = 1; j <= 3; j++) {
                sign[cur_sign] = j;
                dfs(i + 1, cur_sign + 1, cur_num + 1);
            }
        }
        else {
            dfs(i + 1, cur_sign, cur_num + 1);
        }
    }
}

int main() {
    int cas = 1;
    while(scanf("%s", str) != EOF) {
        if(str[0] == '=')
            break;
        flag = false;
        len = strlen(str);
        printf("Problem %d\n", cas++);
        if(strcmp(str,"2000=") == 0) {
            printf("  IMPOSSIBLE\n");
            continue;
        }
        dfs(0,0,0);
        if(!flag)
            printf("  IMPOSSIBLE\n");
    }
    return 0;
}

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const string sign[] = {"*","+","-",""};
map Map;
set Set;
bool judge(string s) {
    vector num, sign;
    int cur = 0;
    while(1) {
        int t = 0;
        while(isdigit(s[cur]))
            t = t * 10 + s[cur++] - '0';
        num.push_back(t);
        if(s[cur] == '=')
            break;
        sign.push_back(Map[s[cur++]]);
    }

    for(int i = 0; i < sign.size(); i++) 
        if(sign[i] == 1) {
            num[i+1] *= num[i];
            sign.erase(sign.begin() + i);
            num.erase(num.begin() + i);
            i--;
        }
    int t = num[0];
    for(int i = 0; i < sign.size(); i++)
        if(sign[i] == 2)
            t += num[i + 1];
        else
            t -= num[i + 1];
    return t == 2000;
}

void dfs(string s, int pos, bool f) {
    if(pos == s.size() - 1) {
        if(judge(s))
            Set.insert(s);

        return;
    }

    for(int i = 0; i < 4; i++) {
        if(!f && i == 3)
            continue;
        string t = s;
        if(s[pos] != '0')
            dfs(t.insert(pos,sign[i]), i == 3? pos+1: pos+2, true);
        else
            dfs(t.insert(pos,sign[i]), i == 3? pos+1: pos+2, i == 3);
    }
}

int main() {
    int cas = 1;
    Map['*'] = 1, Map['+'] = 2, Map['-'] = 3;
    string str;
    while(cin >> str) {
        if(str[0] == '=')
            break;
        Set.clear();
        printf("Problem %d\n", cas++);
        dfs(str,1,str[0] != '0');
        if(!Set.size() || str == "2000=") {
            printf("  IMPOSSIBLE\n");
            continue;
        }

        for(set::iterator it = Set.begin(); it != Set.end(); it++)
            cout << "  " << *it << endl;
    }
    return 0;
}