添加+/-以在0中計算數字字符串

給定一個由數字組成的字符串，使用+或 - 符號使表達式值爲0.返回表達式。添加+/-以在0中計算數字字符串

例如，

123 => 1 + 2 -3 = 0

173956 => 17 + 39 - 56 = 0

我沒有線索，以解決比其他這個問題蠻力的方式。

有什麼建議嗎？

來源

2012-10-18 StarPinkER

也許http://math.stackexchange.com會是一個更好的地方問這個問題。 – Uooo

你看動態規劃解決它嗎？ – stackoverflowery

我嘗試過動態編程，但獲得最佳子結構有點困難。 – StarPinkER

這是一個搜索問題。搜索必須在解決方案空間中執行。假設我們從'123'字符串開始，在這一點上，我們可以在'1'之後加上+或 - 符號，因爲我們得到'1 + 23'或'1 - 23'。每個變體可以通過在下一個字符後添加一個符號來進一步拆分。因此，所有可能的符號添加都將形成樹狀結構 - 解決方案空間。您的算法必須在此結構中搜索解決方案。我認爲A *可以用來做到這一點。

Anders K繪製好解決方案空間的ASCII圖，你只需要搜索它的解決方案。簡單的廣度優先搜索或深度優先搜索可以完成這項工作，但如果解決方案空間很大，我認爲它會很慢。

此外，我認爲可以找到更多的優化解決方案，例如利用解決方案空間的屬性 - 它是樹狀結構。

來源

2012-10-18 06:22:27 Lazin

謝謝，但我認爲Anders K錯過了一個分支，（+ | - | concat），對吧？ – StarPinkER

是的，如果是這樣的話，解決方案空間將會是一個圖表。 – Lazin

，你可以使用它變得很明顯遞歸方法例如很多方法解決這個問題，如果你構建它作爲一棵樹

例如123

，因爲可以有一個數字位數(+|-)後兩個不同的標誌：

 1 
    /\ 
     + - 
    / \ 
    2  2 
/\ /\ 
    + - + - 
    | | | | 
    3 3 3 3

來源

2012-10-18 06:21:51

添加+/-以在0中計算數字字符串

回答

相關問題