特性:数字数量、目标答案不限,当然数据大了会很慢...
基本可以去除所有本质相同的表达式...至少能等出结果的数据规模可以。。
安卓:http://yun.baidu.com/s/1slCGILn
程序用法:
输入n,tar,lim;分别表示n个数,目标答案,最多计算lim个解(0表示输出所有解)
然后输入n个数字
例: 4 24 3
1 2 3 4
表示4个数字1,2,3,4要算出24的前三个解
一般6个数找所有答案开O2需要一分半吧。。
思路(当然是爆枚咯。。。):
由于中缀表达式枚举括号比较麻烦,所以用后缀表达式枚举运算符,最后再把后缀转成中缀输出即可。
但这样还枚举不全,需要枚举数字的全排列再把运算符填进去。
这样虽然可以枚举所有情况,但是因为交换律的存在大量重复出现(比如234 324...)所以要去重。。
由于本人能力有限,,所以用了奇怪的方法,,不过效果还不错,方法如下。
随机生成若干个(程序里是4个)数组,和原数组匹配,然后用同样的运算符计算各个数组,把答案打包存进map有重复不输出即可
例:
比如当前枚举的运算方法是(a+b)/c*d
原数组:
wxy z ==>(w+x)/y*z
随机数组:
a[0][0] a[0][1] a[0][2] a[0][3] ==>(a[0][0]+a[0][1])/a[0][2]*a[0][3]=A
a[1][0] a[1][1] a[1][2] a[1][3] ==>(a[1][0]+a[1][1])/a[1][2]*a[1][3]=B
a[2][0] a[2][1] a[2][2] a[2][3] ==>(a[2][0]+a[2][1])/a[2][2]*a[2][3]=C
......
把{A,B,C,....}放到map里
当枚举到(b+a)/c*d的时候发现
xwy z ==>(x+w)/y*z
a[0][1] a[0][0] a[0][2] a[0][3] ==>(a[0][1]+a[0][0])/a[0][2]*a[0][3]=D
a[1][1] a[1][0] a[1][2] a[1][3] ==>(a[1][1]+a[1][0])/a[1][2]*a[1][3]=E
a[2][1] a[2][0] a[2][2] a[2][3] ==>(a[2][1]+a[2][0])/a[2][2]*a[2][3]=F
此时{A,B,C,...}=={D,E,F,...}说明(a+b)/cd和(b+a)/cd是同样的表达式,那么不输出即可。
代码如下
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int base=10;
6
7 int n,a[100],vec[100],tar,trw=1,Cnt;
8 int test[100][2],testb[100][2];
9 bool visited[100];
10
11 const char op_list[4]={'+','-','*','/'};
12
13 struct T
14 {
15 double aa,bb;
16 bool operator<(const T temp)const
17 {
18 if(fabs(aa-temp.aa)>1e-3) return aa<temp.aa;
19 if(fabs(bb-temp.bb)>1e-3) return bb<temp.bb;
20 return false;
21 }
22 };
23
24 struct Expr
25 {
26 string str;
27 char op;
28 Expr(){op=' ';}
29 };
30
31
32 vector<int> op[100];
33 map<T,bool> Map;
34
35 void Init_random_list()
36 {
37 srand(time(0));
38 for(int j=0;j<2;++j) for(int i=0;i<n;++i) test[i][j]=rand()%(base*10);
39 for(int i=0;i<n;++i) for(int j=i+1;j<n;++j)
40 if(a[i]==a[j]) for(int k=0;k<2;++k) test[j][k]=test[i][k];
41 return ;
42 }
43 double C()
44 {
45 stack<double> S;
46 stack<double> r[2];
47 for(int i=0;i<n;++i)
48 {
49 S.push(vec[i]);
50 for(int j=0;j<(int)op[i].size();++j)
51 {
52 double t1=S.top(); S.pop();
53 double t2=S.top(); S.pop();
54 if(op[i][j]==0) S.push(t2+t1);
55 if(op[i][j]==1) S.push(t2-t1);
56 if(op[i][j]==2) S.push(t2*t1);
57 if(op[i][j]==3) S.push(t2/t1);
58 }
59 }
60 if(fabs(S.top()-(double)tar)<1e-8)
61 {
62 for(int i=0;i<n;++i)
63 {
64 for(int k=0;k<2;++k)
65 {
66 r[k].push(testb[i][k]);
67 for(int j=0;j<(int)op[i].size();++j)
68 {
69 double t1=r[k].top(); r[k].pop();
70 double t2=r[k].top(); r[k].pop();
71 if(op[i][j]==0) r[k].push(t2+t1);
72 if(op[i][j]==1) r[k].push(t2-t1);
73 if(op[i][j]==2) r[k].push(t2*t1);
74 if(op[i][j]==3) r[k].push(t2/t1);
75 }
76 }
77 }
78 T temp=(T){r[0].top(),r[1].top()};
79 if(Map[temp])return -1e100;
80 Map[temp]=true;
81 }
82 return S.top();
83 }
84
85 void Pr()
86 {
87 Cnt++;
88
89 Expr temp;
90 stack<Expr> S;
91
92 for(int i=0;i<n;++i)
93 {
94 char temp_str[110];
95 sprintf(temp_str,"%d",vec[i]);
96 temp.str=temp_str;
97 temp.op=' ';
98
99 S.push(temp);
100 for(int j=0;j<(int)op[i].size();++j)
101 {
102 Expr t1,t2;
103 t2=S.top(); S.pop();
104 t1=S.top(); S.pop();
105 if(op[i][j]>1 && (t1.op=='+' || t1.op=='-' || t2.op=='+' || t2.op=='-'))
106 {
107 if(t1.op=='+' || t1.op=='-') t1.str=" ( "+t1.str+" ) ";
108 if(t2.op=='+' || t2.op=='-') t2.str=" ( "+t2.str+" ) ";
109 temp.str=t1.str+' '+op_list[op[i][j]]+' '+t2.str;
110 temp.op=op_list[op[i][j]];
111 }
112 else temp.str=t1.str+' '+op_list[op[i][j]]+' '+t2.str,
113 temp.op=op_list[op[i][j]];
114 S.push(temp);
115 }
116 }
117 printf("%s\n",S.top().str.c_str());
118 return ;
119 }
120
121 /* Violent enumeration operator */
122 void Calc(const int step,const int pos,const int lim)
123 {
124 if(step==n-1)
125 {
126 if(fabs(C()-(double)tar)<1e-8)
127 {
128 Pr();
129 if(Cnt==trw)throw 0;
130 }
131 return ;
132 }
133 for(int i=max(pos,step+1);i<n;++i)
134 {
135 for(int j=0;j<=lim;++j)
136 {
137 op[i].push_back(j);
138 if(step+1<=i) Calc(step+1,i,lim);
139 op[i].pop_back();
140 }
141 }
142 return ;
143 }
144
145 /* Violent enumeration Permutations */
146 void Dfs(const int step,const int lim)
147 {
148 if(step==n)
149 {
150 try{Calc(0,0,lim);}
151 catch(...){throw 0;}
152 return ;
153 }
154 for(int i=0;i<n;++i)
155 {
156 if(!visited[i])
157 {
158 visited[i]=true;
159 vec[step]=a[i];
160 for(int j=0;j<2;++j)
161 testb[step][j]=test[i][j];
162 Dfs(step+1,lim);
163 visited[i]=false;
164 }
165 }
166 return ;
167 }
168
169 int main()
170 {
171 printf("Size of Input:\t"); scanf("%d",&n);
172 printf("Target Result:\t"); scanf("%d",&tar);
173 printf("Result limits(0 for no limits): "); scanf("%d",&trw);
174
175 printf("Input(32bits integers):\n");
176 for(int i=0;i<n;++i) scanf("%d",&a[i]);
177
178 clock_t start_time=clock();
179 Init_random_list();
180
181 printf("========================\n");
182 //这里会优先选择没有乘除的方案
183 //try{Dfs(0,0);}catch(...){}
184 //try{Dfs(0,1);}catch(...){}
185 //try{Dfs(0,2);}catch(...){}
186 try{Dfs(0,3);}catch(...){}
187 printf("========================\n");
188
189 printf("%d Results Found!\n",Cnt);
190 printf("%ldms Cost!\n",clock()-start_time);
191 return 0;
192 }
原文链接: https://www.cnblogs.com/Gster/p/5600551.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/235512
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!