首页 > ACM题库 > 九度OJ > 九度-1498-寻找表达式[解题代码]
2013
12-13

九度-1498-寻找表达式[解题代码]

题目来源:微策略2013年校园招聘笔试题

题目描述:

现在有一个序列123……N,其中N介于3和15之间,要求在序列之间加入+、-或者空格,使得该序列组成的数学表达式的运算结果为0。

输入:

输入可能包含多个测试样例。
对于每个测试案例,输入整数N(3<=N<=15),代表这个序列的长度。

输出:

对应每个测试案例,输出所有使得表达式结果为0的组合,当有多个组合时,按字典序进行排序输出。

样例输入:
3
6
样例输出:
1+2-3
1 2+3-4-5-6
提示:

 1_2+3-4-5-6相当于12+3-4-5-6(‘_’代表空格)


cpp 代码如下:
#include <stdio.h>
char str[100];
int n,j;
void f(int i,int sum,int last){
	if(i == n+1){
		if(sum == 0){
			printf("1");
			for(j=0; j<n-1; j++){
				printf("%c%d",str[j],j+2);
			}
			puts("");
		}
		return;
	}
	int tmp = last > 0 ? i : -i;
	str[i-2] = ' ';
	if(i < 10)
		f(i+1,sum+last*10+tmp-last, last*10+tmp);
	else
		f(i+1,sum+last*100+tmp-last, last*100+tmp);
	str[i-2] = '+';
	f(i+1,sum+i, i);
	str[i-2] = '-';
	f(i+1,sum - i, -i);
}

int main() {
	while(scanf("%d",&n) != EOF)
	{
		str[0] = '1';
		f(2,1,1);
	}
	return 0;
}
/**************************************************************
	Problem: 1498
	User: coder
	Language: C
	Result: Accepted
	Time:90 ms
	Memory:912 kb
****************************************************************/


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。