华为的一道面试题，看了一些答案，发现看不懂啊？求大神解释啊
题目：输入一个正整数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;
const char sym = {'+' , '-' , ' '};
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] != ' ')
printf(" %c ", sym]);
printf("%d", i);
}
printf(" = %d\n" , result);
}
return;
}
ops = 2;
dfs(layer + 1 , currentResult , lastOp , lastSum); //Continue
currentResult += (lastOp)? (-1 * lastSum) : lastSum;
ops = 0;
dfs(layer + 1 , currentResult , 0 , 0);//Plus
ops = 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;
}
同样没看懂 额，没有大神来指导指导俺们这些菜鸟啊:cry 涉及到算法了，我正打算下学期好好研究算法。我现在试试能不能看得懂 可以单步调试研究，，我明天再看看，晚上看不动 基本思想就是依次考察：
1 2 3 4 5 6 7 8 9数字间的8个空格，这些空格要么填+，要么填-，要么不填（和前一个数字合并起来作为一个新的数字）
dfs函数名就暗示是用深度优先遍历来做的，其中和递归相关的参数就是dfs的第一个参数int layer，这个参数表示递归深度（你也可以理解为它表示考察数字layer以及之前的数字的运算结果是否满足要求）。
递归函数dfs
的结构
if(layer == 9) 即已经考虑了1~9所有数字的运算情况，这是递归的结束条件
剩下的
ops = 2;
dfs(layer + 1 , currentResult , lastOp , lastSum); //Continue
currentResult += (lastOp)? (-1 * lastSum) : lastSum;
ops = 0;
dfs(layer + 1 , currentResult , 0 , 0);//Plus
ops = 1;
dfs(layer + 1 , currentResult , 1 , 0);//Minus
是在不满足结束条件时，暴力试探3种填法（即填+，-或不填） 仰望天上的光 发表于 2015-8-15 00:00
基本思想就是依次考察：
1 2 3 4 5 6 7 8 9数字间的8个空格，这些空格要么填+，要么填-，要么不填（和前一 ...
多谢大神救助啊，我得上万再查查资料，依然还是没有完全搞明白，算法这块儿根本一窍不通，得赶紧看了 甲鱼牙 发表于 2015-8-15 17:10
确实好难，看不懂，麻竹，慢慢练习
:handshake 追忆lh 发表于 2015-8-15 16:24
多谢大神救助啊，我得上万再查查资料，依然还是没有完全搞明白，算法这块儿根本一窍不通，得赶紧看了
如果只做常规性编程的话，没必要太在意这些的。这些要搞明白要花些时间研究下ACM之类的题目，关键在于很多概念很难明白，然而明白的人会用专业术语直接表达自己的观点（不然要说很多话），所以你很难看明白人家写的东西。最主要的问题在于，你要想清楚你学算法是为了干什么？如果立志于参加国际程序比赛。。。那么OK，上吧。。。如果只是想让自己的程序效率更高。。。那完全是扯蛋。。。稍微专业的领域都已经有非常成熟的算法函数库可以直接调用，你会调用就OK。 就像华为的这些面试。。。为什么要考算法？不是因为工作中需要算法，而是因为来应聘的人太多了，面试之前如何刷掉一批人呢？就考算法。如果你有自己比较成功的作品和项目经历。。。完全不会算法，只要你能找到项目主管，他就一定会收你。 好难，看不懂 帮楼主顶下{:5_100:} 然而我也并没有看懂。。 仰望天上的光 发表于 2015-8-17 19:51
如果只做常规性编程的话，没必要太在意这些的。这些要搞明白要花些时间研究下ACM之类的题目，关键在于很 ...
嗯嗯嗯，谢谢亲啦 迷雾少年 发表于 2015-8-18 18:33
好难，看不懂 帮楼主顶下
:handshake:hug:
可以单步调试研究，，我明天再看看，晚上看不动 不懂 如果是你自己先不看这个代码，先自己把思路写出来，自己能写出的思路与当前的程序进行类比，应该会清晰一些 用matlab写了下，
结果是： 21
时间已过 0.021004 秒。
>>
等于6是 12
时间已过 0.024553 秒。
>>
等于24是 18
时间已过 0.022697 秒。
>> python代码:
def calc(x):
import itertools as it
c = 0
num =
for each in it.product(('+','-',''),repeat=8):
s = ''
for i in range(8):
s+=num+each
s+=num
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
# Press enter to exit
页:
[1]