动态规划法解数字加符号的运算结果

2014/09/03 Algorithm

背景

  今天看到有同学华为面试,而我痛苦去不了,在外实习赶不上啊。看到很多论坛讨论这样一道题:1,2,3,….9 n个数,每个数字前可以加’+’ ‘-‘ 或空,要求输出所有满足计算结果为某数的所有表达式
  我刚看到这个问题就觉得可以用动态规划做,经过一阵研究得出下面递推式:
F(n,m)=∩F(k-1,m±Interger(a[k,n]))
  遍历k∈[0,n-1], 如果不存在k则在数组[0-n]范围内无法找到结果为m的表达式,反之则在n=0时输出。欢迎大家一起测试。

代码

#include <iostream>
using namespace std;
#define arr(x,y) arr[(x)*size2+(y)]
const int num=9;
int arr[num]={1,2,3,4,5,6,7,8,9};//第一个数之前也可以有符号
char sig[num];
int getmax(int i,int j)
{
	int result=0;
	for(int k=i;k<=j;k++)
		result=result*10+arr[k];
	return result;
}
bool func(int n,int m)
{//F[n,m]用来求arr[0-n]内运算产生结果m的所有解
	int j;
	//结果
	if(m == 0 || n == 0)
	{
		if(m == 0)
		{
			for(int k=0;k<num;k++)
			{
				cout<<sig[k]<<arr[k];
			}
			cout<<endl;
		}
		if(n == 0)
		{
			if(arr[n] == m)
			{
				sig[0]='+';
				for(int k=0;k<num;k++)
				{
					cout<<sig[k]<<arr[k];
				}
				cout<<endl;
				return true;
			}
			else if(arr[n] == -m)
			{
				sig[0]='-';
				for(int k=0;k<num;k++)
				{
					cout<<sig[k]<<arr[k];
				}
				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,n]))   遍历k∈[0,n-1]
	bool ret=false;
	for(int k=0;k<=n;k++)
	{
		int max=getmax(k,n);
		sig[k]='+';
		for(j=k+1;j<=n;j++)
			sig[j]='\0';
		if(func(k-1,m-max))
		{
			ret=true;
		}
		
		sig[k]='-';
		for(j=k+1;j<=n;j++)
			sig[j]='\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-9  m: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

Show Disqus Comments

Search

    Table of Contents