动态规划法解数字加符号的运算结果
今天看到有同学华为面试，而我痛苦去不了，在外实习赶不上啊。看到很多论坛讨论这样一道题：
1,2,3,....9 n个数，每个数字前可以加'+' '-' 或空，要求输出所有满足计算结果为某数的所有表达式
我刚看到这个问题就觉得可以用动态规划做，经过一阵研究得出下面递推式：
F(n,m)=∩F(k-1,m±Interger(a)) 遍历k∈如果不存在k则在数组范围内无法找到结果为m的表达式
反之则在n=0时输出。
欢迎大家一起测试。
代码如下：
#include <iostream>
using namespace std;
#define arr(x,y) arr[(x)*size2+(y)]
const int num=9;
int arr={1,2,3,4,5,6,7,8,9};//第一个数之前也可以有符号
char sig;
int getmax(int i,int j)
{
int result=0;
for(int k=i;k<=j;k++)
result=result*10+arr;
return result;
}
bool func(int n,int m)
{//F用来求arr内运算产生结果m的所有解
int j;
//结果
if(m == 0 || n == 0)
{
if(m == 0)
{
for(int k=0;k<num;k++)
{
cout<<sig<<arr;
}
cout<<endl;
}
if(n == 0)
{
if(arr == m)
{
sig='+';
for(int k=0;k<num;k++)
{
cout<<sig<<arr;
}
cout<<endl;
return true;
}
else if(arr == -m)
{
sig='-';
for(int k=0;k<num;k++)
{
cout<<sig<<arr;
}
cout<<endl;
return true;
}
else
return false;
}
return true;
}
//限界
if(n < 0)
return false;
int curmax=getmax(0,n);
if(m > curmax || m < -curmax)
return false;
//动态规划F(n,m)=∩F(k-1,m±Interger(a)) 遍历k∈
bool ret=false;
for(int k=0;k<=n;k++)
{
int max=getmax(k,n);
sig='+';
for(j=k+1;j<=n;j++)
sig='\0';
if(func(k-1,m-max))
{
ret=true;
}
sig='-';
for(j=k+1;j<=n;j++)
sig='\0';
if(func(k-1,m+max))
{
ret=true;
}
}
return ret;
}
void main()
{
int i,j;
int object=123;
func(num-1,object);
}
对于n:1-9m:123，可以得到如下结果：
-1-2 3-4-5+6 7+8 9
-1-2 3+4 5+6+7+8 9
-1+2 3+4-5+6+7+8 9
+1+2 3+4+5-6+7+8 9
+1-2+3+4 5-6-7+8 9
-1-2 3+4+5 6+7 8+9
-1 2-3+4 5+6+7 8+9
-1+2+3 4-5+6+7 8+9
-1-2-3+4 5-6+7 8+9
+1+2+3 4+5-6+7 8+9
-1-2-3+4 5+6 7+8+9
-1-2+3 4+5+6 7+8+9
-1-2-3+4+5 6+7 8-9
+1-2+3-4+5 6+7 8-9
-1-2+3+4 5+6+7 8-9
+1 2+3+4 5-6+7 8-9
m=45时（我以为只有连加呢，，结果结果出了一大堆）
+1-2 3+4 5-6 7+8 9
-1+2 3-4+5-6 7+8 9
+1+2 3+4-5-6 7+8 9
-1-2+3+4-5 6+7+8 9
+1 2-3-4-5 6+7+8 9
-1-2-3-4 5-6+7+8 9
+1 2+3+4-5 6-7+8 9
-1+2 3-4-5 6-7+8 9
+1-2+3-4 5+6-7+8 9
-1-2-3 4+5-6-7+8 9
+1-2 3-4-5-6-7+8 9
-1+2 3+4 5+6 7-8 9
-1-2-3-4 5+6+7 8+9
+1 2-3-4 5-6+7 8+9
+1+2-3 4-5-6+7 8+9
+1+2+3-4 5+6 7+8+9
-1-2-3 4-5+6 7+8+9
+1-2-3 4+5 6+7+8+9
+1+2+3+4+5+6+7+8+9
+1+2 3-4-5+6+7+8+9
-1 2+3 4+5-6+7+8+9
-1-2+3 4-5-6+7+8+9
-1-2+3 4-5+6-7+8+9
+1-2-3+4 5-6-7+8+9
-1+2+3 4+5-6-7+8+9
+1 2+3 4-5-6-7+8+9
-1+2 3-4 5+6 7-8+9
-1-2 3-4+5+6 7-8+9
+1-2 3+4-5+6 7-8+9
-1-2 3+4+5 6+7-8+9
-1 2-3-4+5 6+7-8+9
-1+2 3+4+5+6+7-8+9
-1+2+3 4-5+6+7-8+9
-1+2-3+4 5-6+7-8+9
-1 2+3+4+5 6-7-8+9
-1+2-3-4+5 6-7-8+9
-1-2-3+4 5+6-7-8+9
-1-2+3 4-5 6+7 8-9
+1 2+3-4 5+6+7 8-9
+1-2-3 4+5+6+7 8-9
-1 2+3-4-5-6+7 8-9
+1+2 3-4 5+6 7+8-9
+1-2 3-4+5+6 7+8-9
+1+2 3+4+5+6+7+8-9
-1-2-3+4 5-6+7+8-9
-1-2+3-4+5 6-7+8-9
+1-2+3+4 5+6-7+8-9
-1-2-3-4+5+6 7-8-9
-1-2-3-4-5+6 7-8-9
-1-2-3+4+5 6+7-8-9
-1-2+3-4+5 6+7-8-9
-1+2+3+4 5+6+7-8-9
+1 2-3+4+5 6-7-8-9
页:
[1]