搜索之枚举

发表于 更新于 分类于 阅读次数：

搜索算法是最基础的算法，比较实用。枚举搜索是最简单的搜索算法，适用于问题规模比较小的情景。下面用一道题熟悉一下，搜索24点。

题目来源：http://hihocoder.com/contest/hiho98/problem/1

C实现的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<stdio.h>
#include<string.h>

int  used[4], nowNumber[4], number[4];

// ^'表示反减,'|'表示反除，
char ops[3], opType[6] = {'+','-','*','/','^','|'};

float operate(char op, float a, float b){
	float t;
	switch(op){
        case '+' : t = a+b; break;
    	case '-' : t = a-b; break;
    	case '*' : t = a*b; break;
    	case '/' : {
    		if(b<0 || b>0)
    		    t = a/b;
    		break;
    	}
    	case '^' : t = b-a; break;
    	case '|' :{
    		if(a<0 || a>0)
    		   t = b/a;
    		break;
    	}
	}
	return t;
}

//计算类型一表达式：((a@b)@c)@d
float calcType1(){
	int i;
	float tmp;
	tmp = nowNumber[0];
	for(i=0; i<3; ++i){
    	tmp = operate(ops[i], tmp, nowNumber[i+1]);
	}
	return tmp;
}

//计算类型二表达式：(a@b)@(c@d)
float calcType2(){
    float t,m,n;
    m = operate(ops[0], nowNumber[0], nowNumber[1]);
    n = operate(ops[2], nowNumber[2], nowNumber[3]);
    t = operate(ops[1], m, n);
	return t;
}

int makeOperation(int depth){
	int i;
	if(depth >= 3){
		//计算类型一
		if(calcType1()>=24 && calcType1()<=24)
			return 1;
		//计算类型二
		if(calcType2()>=24 && calcType2()<=24)
			return 1;
        return 0;
	}

	for(i=0; i<6; ++i){
		ops[depth] = opType[i];
		if(makeOperation(depth+1))
			return 1;
	}

	return 0;
}

int makeNumber(int depth){
    int i;
    if(depth >= 4)
    	return makeOperation(0);

    for(i=0; i<4; ++i){
    	if(used[i] == 0){
           nowNumber[ depth ] = number[i];

           used[i] = 1;
           if(makeNumber(depth+1)){
           	    return 1;
           }
           used[i] = 0;
    	}
    }
    return 0;
}

int main(){
	int i,t;

	while(scanf("%d", &t) != EOF){
       for(i=0; i<t; ++i){
          scanf("%d %d %d %d", &number[0], &number[1], &number[2], &number[3]);
          memset(used, 0, sizeof(used));
          if(makeNumber(0) == 1)
          	printf("Yes\n");
          else
          	printf("No\n");
       }
	}
	return 0;
}