poj1950 Dessert（DFS）

题目链接

http://poj.org/problem?id=1950

题意

输入一个整数n（3<=n<=15），将1,2,..n顺序排列，在数字中间插入'+'，'-'，'.'，这样会产生一个算数表达式，如果表达式的值为0，则输出该表达式。如果表达式为0的个数大于20，则只输出前20个。

思路

采用DFS搜索解决。由于数字的位置是固定的，所以在符号的位置上不断地尝试三种符号即可，若最终的表达式结果为0且是前20个表达式，则输出该表达式。

代码

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 20;
 7 char str[N];
 8 int n;
 9 int nums;
10 int k;
11 
12 /*
13  * sum : 已求得的表达式的值
14  * pre : 当前位置pos的前一位置的值
15  * pos ： 当前处理的数字，pos-1为符号插入的位置
16 */
17 void dfs(int sum, int pre, int pos)
18 {
19     if(pos==n+1)
20     {
21         if(sum==0)
22         {
23             nums++;
24             if(nums<=20)
25             {
26                 for(int i=1; i<n; i++)
27                     printf("%d %c ",i, str[i]);
28                 printf("%d
", n);
29             }
30         }
31         return;
32     }
33 
34     str[pos-1] = '+';
35     dfs(sum+pos, pos, pos+1);
36 
37     str[pos-1] = '-';
38     dfs(sum-pos, -pos, pos+1);
39 
40     str[pos-1] = '.';
41     if(pos>=10)     //10.11=1011
42         k = 100;
43     else k = 10;    //1.2=12
44 
45     if(pre<0)
46         dfs(sum-pre+pre*k-pos, pre*k-pos, pos+1);
47     else if(pre>0)
48         dfs(sum-pre+pre*k+pos, pre*k+pos, pos+1);
49 }
50 
51 int main()
52 {
53     cin>>n;
54     nums = 0;
55     dfs(1, 1, 2);
56     cout<<nums<<endl;
57     return 0;
58 }