實現挑戰的理論24求解器

作爲Java和Android開發的入門，我決定編寫一個挑戰24（爲了創建產品24，給定4個數字，必須加，乘，除或減）求解應用程序實施一種徹底的技術來解決任何和所有可能的解決方案。目前它的工作原理是這樣（A，B，C，D爲4個輸入數字）實現挑戰的理論24求解器

((a+b)+c)+d 
((a+b)+c)-d 
((a+b)+c)*d 
((a+b)+c)/d 
((a+b)-c)+d 
... 
... 
((a/b)/c)/d 
((a+b)+d)+c 
((a+b)+d)-c

等等...

我發現這個工作在絕大多數情況下，然而案件如8,3,8,3出現在沒有找到解決方案的測試中，但解決方案8 /（3-8/3）= 24是正確的。所以我想最終的問題是相當含糊的，但是如何解決這個問題，以解決括號對找到解決方案至關重要的情況？

來源

2011-08-16 enraged cacti

我編輯了標籤，因爲這與Android沒有任何關係。 – DeeV

是'a /（b-c/d）'測試用例？ – corsiKa

我很好奇你玩什麼版本的24，允許中間結果分數。 – Simon

考慮變量a，b，C d作爲輸入，+， - ，*，/爲運營商

你將永遠有三家運營商

a op b op c op d

現在考慮括號

的組合現在

1 group of 2 
(a op b) op c op d 
a op (b op c) op d 
a op b op (c op d) 

1 group of 3 
(a op b op c) op d 
a op (b op c op d) 

each 3 can be comprised 
(x op y op z) as above example 
(x op (y op z)) 
((x op y) op z) 

Also, 2 groups of 2 
(a op b) op (c op d)

，必須測試以上各組操作的每個組合：

Haha silly code parser, you think these are comments in here... tsk tsk 
+++, ++-, ++*, ++/, +-+, +--, +-*, +-/, 
+*+, +*-, +**, +*/, +/+, +/-, +/*, +//, 
-++, -+-, -+*, -+/, --+, ---, --*, --/, 
-*+, -*-, -**, -*/, -/+, -/-, -/*, -//, 
*++, *+-, *+*, *+/, *-+, *--, *-*, *-/, 
**+, **-, ***, **/, */+, */-, */*, *//, 
/++, /+-, /+*, /+/, /-+, /--, /-*, /-/, 
/*+, /*-, /**, /*/, //+, //-, //*, ///

因此，用這些操作，每組三個（包括簡單版本和嵌套版本），以及兩組兩個一組來測試每個組。

據我估計，這是640測試。

這可以在邏輯上減少，例如如果op1 == op2 == op3那麼括號無關緊要。還有其他減少你可以做。

編輯：那麼您將需要在A，B，C的每個置換，d這將帶來總量達15,360運行（更少，如果有重複，當然）

來源

2011-08-16 20:46:47 corsiKa

您還必須通過這些括號/運算符集運行a，b，c，d的每個排列。 – Simon

@Simon謝謝你。添加它，以及其他信息。 – corsiKa

我並不知道「挑戰24」是一個明確的難題。你有鏈接嗎？谷歌給了我一堆噪音。我一直在遵循這些規則：http://www.24game.com/t-about-howtoplay.aspx – Simon

如果您想繼續詳盡，請爲每個可能的括號組合創建條件。

來源

2011-08-16 19:43:32

我會處理這通過枚舉前綴或後綴表示法中可能的操作符/操作數組合，或構建表達式樹。這應該能夠更容易地在循環和/或功能中表達它們。然後，您可以將解決方案轉換爲中綴輸出;如果你不擔心多餘的括號，這很簡單。

您可以通過這種方式對搜索順序進行優化，但問題空間太小，我不打擾。

來源

2011-08-16 21:47:40 Simon

實現挑戰的理論24求解器

回答

相關問題