2014年七月華為校招機試題目--最難的一道，呵呵！ - acm1314－IT工程師數位筆記本

文章出處

今天百無聊賴之時，漫心看到14年的華為校招機試題目，一共三道，前兩道皆是平平，第三道卻柳暗花明，讓人眼前一亮。咋一看，饒有趣味，看似平淡無奇，然而卻玄機頗深（對我這種弱渣而言）。（不過對于ACMer，好像應該用基礎算法，就能解決！）

（然而我也只會基礎的算法！！懺愧的緊！！！）。如果有幸被大神看到，能指點我一兩招，不勝感激！下面是題目和我的詳細題解思路（可供巨巨一笑！嘿嘿！）。

2014年七月華為校招機試題目：

第三題：

輸入一個正整數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

看似好復雜的題目 ~~~

稍微冷靜的思考一下：

　　這道題看似復雜，但是作為校招題應該不會太難。所以，冷靜的思考一下，能否對這個問題進行建模？稍微了解一點算法的都應該知道： 一切的算法問題都不過是搜索問題。 所以只要建立一個正確的搜索模型就行了。而搜索模型的建立，主要是明確狀態是如何轉換的。

　　稍微用幾個腦細胞就會發現，在這道題中，狀態只有三種轉化方式， +， -，*10+。例如： 1 要轉化為下一個狀態，無非是 1+2； 1-2； 1*10+2=12 三種狀態而已。這樣解決方案就立刻明朗了，無非就是從狀態 1 依次搜索到狀態 9 而已，求方案數用DFS搜索一遍就行了啊。 但是，這個題還有一點小坑的地方： 例如DFS某條搜索路徑是： 12-34+5-67+89，你如果直接計算，得到的結果是這樣的： 1*10+2=12， 12-3=9，9*10+4 = 94（正確結果應該是 12-34 = -22 ,,,），，，，咿呀呀。所以是不能直接算的，解決方案是可以把搜索的路徑保存下來。問題很明確了： DFS求能到達某一點的所有路徑。

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 // 字符串式子求和： 例如 "12-34+5-67+89"  
 7 int getSum(const string& str)
 8 {
 9     int ans = 0, num = 0;
10     int i;  
11     while(str[i] >= '1' && str[i] <= '9')
12     {
13         ans = ans * 10 + str[i] - '0';
14         i++; 
15     }
16     while(i < str.size())
17     {
18             
19         char op = str[i]; 
20         i++; 
21         num = 0; 
22         while(str[i] >= '1' && str[i] <= '9')
23         {
24             num = num * 10 + str[i] - '0';
25             i++; 
26         }
27         if(op == '+')
28             ans += num; 
29         else if(op == '-')
30             ans -= num;    
31     }
32 
33     return ans; 
34 }
35 
36 // DFS 求方案數 
37 void dfs(const int target, int pos, string str, int &cnt)
38 {
39     if(pos == 10)
40     {
41         if(getSum(str)== target)
42             cnt++; 
43         return; 
44     }
45 
46     dfs(target, pos+1, (str + "+").append(1, pos+'0'), cnt); 
47     dfs(target, pos+1, (str + "-").append(1, pos+'0'), cnt); 
48     dfs(target, pos+1, str.append(1, pos + '0'), cnt); 
49 
50 }
51 
52 int main()
53 {
54     int n; 
55     while(scanf("%d", &n) != EOF)
56     {
57         int cnt = 0;
58         string str="1";  
59         dfs(n, 2, str, cnt); 
60         printf("%d\n", cnt); 
61     }
62     return 0; 
63 }