华为的一道面试题，看了一些答案，发现看不懂啊？求大神解释啊

追忆lh

题目：
输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。
1 2 3 4 5 6 7 8 9 = X
比如：
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序，统计满足输入整数的所有整数个数。
输入：       正整数，等式右边的数字
输出：       使该等式成立的个数
样例输入：5
样例输出：21
以下是网上的答案，看不懂是怎么算出来的，是怎样的一个思路啊？求大神解读 啊

1. 
   
2. #include<iostream>  
   
3. #include<cstdio>  
   
4. using namespace std;  
   
5. 
   
6. int ops[21];  
   
7. const char sym[3] = {'+' , '-' , ' '};  
   
8. int result , num;  
   
9.   
   
10. void dfs(int layer, int currentResult, int lastOp, int lastSum)  
    
11. {  
    
12.   lastSum *= (layer > 9) ? 100 : 10;  
    
13.    lastSum += layer;  
    
14.    if(layer == 9)  
    
15.     {  
    
16.         currentResult += (lastOp) ? (-1 * lastSum) : lastSum;  
    
17.        if(currentResult == result)  
    
18.         {  
    
19.            ++num;  
    
20.             printf("1");  
    
21.             for(int i = 2 ; i <= 9 ; ++i)  
    
22.            {  
    
23.                 if(sym[ops[i-1]] != ' ')  
    
24.                     printf(" %c ", sym[ops[i-1]]);  
    
25.                printf("%d", i);  
    
26.             }  
    
27.            printf(" = %d\n" , result);  
    
28.         }  
    
29.         return;  
    
30.     }  
    
31.     ops[layer] = 2;  
    
32.     dfs(layer + 1 , currentResult , lastOp , lastSum);   //Continue  
    
33.    currentResult += (lastOp)? (-1 * lastSum) : lastSum;  
    
34.     ops[layer] = 0;  
    
35.     dfs(layer + 1 , currentResult , 0 , 0);  //Plus  
    
36.    ops[layer] = 1;  
    
37.     dfs(layer + 1 , currentResult , 1 , 0);  //Minus  
    
38. }  
    
39. 
    
40. int main(void)  
    
41. {  
    
42.    while(scanf("%d", &result) != EOF)  
    
43.     {  
    
44.         num = 0;  
    
45.         dfs(1 , 0 , 0 , 0);  
    
46.         printf("%d\n" , num);  
    
47.    }  
    
48.     return 0;  
    
49. }  
    

复制代码

溯月0503

同样没看懂

追忆lh

额，没有大神来指导指导俺们这些菜鸟啊:cry

You0

涉及到算法了，我正打算下学期好好研究算法。我现在试试能不能看得懂

You0

可以单步调试研究，，我明天再看看，晚上看不动

仰望天上的光

基本思想就是依次考察：
1 2 3 4 5 6 7 8 9数字间的8个空格，这些空格要么填+，要么填-，要么不填（和前一个数字合并起来作为一个新的数字）
dfs函数名就暗示是用深度优先遍历来做的，其中和递归相关的参数就是dfs的第一个参数int layer，这个参数表示递归深度（你也可以理解为它表示考察数字layer以及之前的数字的运算结果是否满足要求）。

递归函数dfs
的结构
if(layer == 9) 即已经考虑了1~9所有数字的运算情况，这是递归的结束条件

剩下的
ops[layer] = 2;  
    dfs(layer + 1 , currentResult , lastOp , lastSum);   //Continue  
   currentResult += (lastOp)? (-1 * lastSum) : lastSum;  
    ops[layer] = 0;  
    dfs(layer + 1 , currentResult , 0 , 0);  //Plus  
   ops[layer] = 1;  
    dfs(layer + 1 , currentResult , 1 , 0);  //Minus  
是在不满足结束条件时，暴力试探3种填法（即填+，-或不填）

追忆lh

仰望天上的光 发表于 2015-8-15 00:00
基本思想就是依次考察：
1 2 3 4 5 6 7 8 9数字间的8个空格，这些空格要么填+，要么填-，要么不填（和前一 ...

多谢大神救助啊，我得上万再查查资料，依然还是没有完全搞明白，算法这块儿根本一窍不通，得赶紧看了

追忆lh

甲鱼牙 发表于 2015-8-15 17:10
确实好难，看不懂，麻竹，慢慢练习

:handshake

仰望天上的光

追忆lh 发表于 2015-8-15 16:24
多谢大神救助啊，我得上万再查查资料，依然还是没有完全搞明白，算法这块儿根本一窍不通，得赶紧看了

如果只做常规性编程的话，没必要太在意这些的。这些要搞明白要花些时间研究下ACM之类的题目，关键在于很多概念很难明白，然而明白的人会用专业术语直接表达自己的观点（不然要说很多话），所以你很难看明白人家写的东西。最主要的问题在于，你要想清楚你学算法是为了干什么？如果立志于参加国际程序比赛。。。那么OK，上吧。。。如果只是想让自己的程序效率更高。。。那完全是扯蛋。。。稍微专业的领域都已经有非常成熟的算法函数库可以直接调用，你会调用就OK。

仰望天上的光

就像华为的这些面试。。。为什么要考算法？不是因为工作中需要算法，而是因为来应聘的人太多了，面试之前如何刷掉一批人呢？就考算法。如果你有自己比较成功的作品和项目经历。。。完全不会算法，只要你能找到项目主管，他就一定会收你。

迷雾少年

好难，看不懂 帮楼主顶下

damingdingdin

然而我也并没有看懂。。

追忆lh

仰望天上的光 发表于 2015-8-17 19:51
如果只做常规性编程的话，没必要太在意这些的。这些要搞明白要花些时间研究下ACM之类的题目，关键在于很 ...

嗯嗯嗯，谢谢亲啦

追忆lh

迷雾少年 发表于 2015-8-18 18:33
好难，看不懂 帮楼主顶下

:handshake:hug:

肥哥与竹竿

可以单步调试研究，，我明天再看看，晚上看不动

彼岸花316

不懂

漠水

如果是你自己先不看这个代码，先自己把思路写出来，自己能写出的思路与当前的程序进行类比，应该会清晰一些

najin

用matlab写了下，
结果是：    21

时间已过 0.021004 秒。
>>

等于6是    12

时间已过 0.024553 秒。
>>

等于24是   18

时间已过 0.022697 秒。
>>

jerryxjr1220

python代码:

1. def calc(x):
   
2.   import itertools as it
   
3.   c = 0
   
4.   num = [str(i) for i in range(1,10)]
   
5.   for each in it.product(('+','-',''),repeat=8):
   
6.     s = ''
   
7.     for i in range(8):
   
8.       s+=num[i]+each[i]
   
9.     s+=num[8]
   
10.     if eval(s)==x:
    
11.       c+=1
    
12.       print s
    
13.   return c
    
14. print(calc(5))

复制代码

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+34-56+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-45+67-8-9
1+23+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-56+78-9
1-2-34-56+7+89
1-23+4+5-6+7+8+9
1-23+45+6-7-8-9
1-23-4-56+78+9
12-34+5-67+89
21

#[QPython] Press enter to exit