求大神解决 c++ 编程题 Get Zero
Get Zero
描述
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.
输入
INPUT FORMAT For Each Test Data
A single line with the integer N (3 <= N <= 9).
输出
OUTPUT FORMAT For Each Test Data
In ASCII order, show each sequence that can create 0 sum with a `+', `-', or ` ' between each pair of numbers.
样例输入
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-7
1-2-3-4-5+6+7
[解决办法]
三叉树(深度为N)
1. 令根节点为值为1, 其与三个页节点的连接权重为'+', '-', '[blank]'
2. 分别计算页节点的值: 权重运算(页节点深度, 父节点)
例如 根节点的三个页节点值分别为:
+(2, 1) = 1+2 = 3
-(2, 1) = 1-2 = -1
blank(2, 1) = 1*10 + 2
则可由最下层的值为0的节点倒序遍历得到结果. 具体实现略
