zerosum - codetrick
Consider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 ... N.
Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero.
Write a program that will find all sequences of length N that produce a zero sum.
请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。现在请在数列中插入“+”表示加，或者“-”表示减，抑或是“ ”表示空白，来将每一对数字组合在一起（请不在第一个数字前插入符号）。计算该表达式的结果并注意你是否得到了和为零。请你写一个程序找出所有产生和为零的长度为N的数列。
X. DFS
http://jackneus.com/programming-archives/zero-sum/
http://sdjl.me/index.php/archives/93
Extended:
微策略2013年校园招聘笔试题-寻找表达式
Read full article from zerosum - codetrick
Consider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 ... N.
Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero.
Write a program that will find all sequences of length N that produce a zero sum.
PROGRAM NAME: zerosum
INPUT FORMAT
A single line with the integer N (3 <= N <= 9).SAMPLE INPUT (file zerosum.in)
7
OUTPUT FORMAT
In ASCII order, show each sequence that can create 0 sum with a `+', `-', or ` ' between each pair of numbers.SAMPLE OUTPUT (file zerosum.out)
1+2-3+4-5-6+7 1+2-3-4+5+6-7 1-2 3+4+5+6+7 1-2 3-4 5+6 7 1-2+3+4-5+6-7 1-2-3-4-5+6+7http://zqynux.iteye.com/blog/620397
请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。现在请在数列中插入“+”表示加，或者“-”表示减，抑或是“ ”表示空白，来将每一对数字组合在一起（请不在第一个数字前插入符号）。计算该表达式的结果并注意你是否得到了和为零。请你写一个程序找出所有产生和为零的长度为N的数列。
X. DFS
- void zero(int sum, int t, int now, char s)
- {
- if(now == n){
- if(s == '+'){
- sum += t;
- }else{
- sum -= t;
- }
- if(sum == 0 && str[0] == '+'){
- out();
- }
- return;
- }
- str[now] = ' ';
- zero(sum, t * 10 + now + 1, now + 1, s);
- if(s == '+'){
- sum += t;
- }else{
- sum -= t;
- }
- str[now] = '+';
- zero(sum, now + 1, now + 1, '+');
- str[now] = '-';
- zero(sum, now + 1, now + 1, '-');
- }
int n,e[10]={1,2,3,4,5,6,7,8,9};void dfs(int s,int sum,int num,int sign,string str){ if(s==n) { if(sum+sign*num==0) cout << str << endl; return; } dfs(s+1,sum,num*10+e[s],sign,str+" "+char(e[s]+'0')); dfs(s+1,sum+sign*num,e[s],1,str+"+"+char(e[s]+'0')); dfs(s+1,sum+sign*num,e[s],-1,str+"-"+char(e[s]+'0')); }http://sdjl.me/index.php/archives/93
Extended:
微策略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(‘_’代表空格)
在递归的时候分布遍历这3中情况：合并上一个，加，减。
传入参数last，代表上一个数，因为当前数 可以选择和上一个数合并。
比如1_2+3-4-5-6
1就是上一个数，2就是当前数，形成12。
05 | //搜索到第i个数;总和为sum;last表示上一个数的值 |
06 | void f(int i,int sum,int last){ |
07 | if(i == n+1){ |
08 | if(sum == 0){ //遍历结束的时候判断是否符合情况 |
09 | printf("1"); |
10 | for(j=0; j<n-1; j++){ |
11 | printf("%c%d",str[j],j+2); |
12 | } |
13 | puts(""); |
14 | } |
15 | return; |
16 | } |
17 | //合并时需要考虑上一个数的正负号 |
18 | int tmp = last > 0 ? i : -i; |
19 | str[i-2] = ' ';//str记录所有的操作 |
20 | if(i < 10) |
21 | f(i+1,sum+last*10+tmp-last, last*10+tmp);//合并上一个数 |
22 | else |
23 | f(i+1,sum+last*100+tmp-last, last*100+tmp);//合并上一个数 |
24 | str[i-2] = '+'; |
25 | f(i+1,sum+i, i);//加当前数 |
26 | str[i-2] = '-'; |
27 | f(i+1,sum - i, -i);//减当前数 |
28 | } |
29 |
30 | int main() { |
31 | while(scanf("%d",&n) != EOF) |
32 | { |
33 | str[0] = '1';//第一个为1已经确定 |
34 | f(2,1,1);//从第2个数开始，当前和为1，上一个数也为1 |
35 | } |
36 | return 0; |
37 | } |
