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

追忆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
以下是网上的答案，看不懂是怎么算出来的，是怎样的一个思路啊？求大神解读 啊

#include<iostream>  
#include<cstdio>  
using namespace std;  
 
int ops[21];  
const char sym[3] = {'+' , '-' , ' '};  
int result , num;  
  
void dfs(int layer, int currentResult, int lastOp, int lastSum)  
{  
  lastSum *= (layer > 9) ? 100 : 10;  
   lastSum += layer;  
   if(layer == 9)  
    {  
        currentResult += (lastOp) ? (-1 * lastSum) : lastSum;  
       if(currentResult == result)  
        {  
           ++num;  
            printf("1");  
            for(int i = 2 ; i <= 9 ; ++i)  
           {  
                if(sym[ops[i-1]] != ' ')  
                    printf(" %c ", sym[ops[i-1]]);  
               printf("%d", i);  
            }  
           printf(" = %d\n" , result);  
        }  
        return;  
    }  
    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  
}  
 
int main(void)  
{  
   while(scanf("%d", &result) != EOF)  
    {  
        num = 0;  
        dfs(1 , 0 , 0 , 0);  
        printf("%d\n" , num);  
   }  
    return 0;  
}  

溯月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代码:

def calc(x):
  import itertools as it
  c = 0
  num = [str(i) for i in range(1,10)]
  for each in it.product(('+','-',''),repeat=8):
    s = ''
    for i in range(8):
      s+=num[i]+each[i]
    s+=num[8]
    if eval(s)==x: 
      c+=1
      print s
  return c
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