如何設計一個算法來計算倒計時風格數學難題

Question

我一直都想這樣做，但每次我開始考慮這個問題時，都會因爲它的指數性而引起我的思考。

的解決問題的我希望能夠理解和代碼是倒計時的數學題：

給定數量的X1的設置爲X5算算他們可以利用數學運算，使Y. 您可以合併應用乘法，除法，加法和減法。

那麼，如何讓1,3,7,6,8,3348？

答案：(((8 * 7) + 3) -1) *6 = 348。

如何編寫一個可以解決這個問題的算法？當你試圖解決這樣的問題時，你從哪裏開始？在設計這樣的算法時，您需要考慮哪些重要的考慮事項？

Answer 1

在Java中非常快速和骯髒的解決方案：

public class JavaApplication1 
{ 

    public static void main(String[] args) 
    { 
     List<Integer> list = Arrays.asList(1, 3, 7, 6, 8, 3); 
     for (Integer integer : list) { 
      List<Integer> runList = new ArrayList<>(list); 
      runList.remove(integer); 
      Result result = getOperations(runList, integer, 348); 
      if (result.success) { 
       System.out.println(integer + result.output); 
       return; 
      } 
     } 
    } 

    public static class Result 
    { 

     public String output; 
     public boolean success; 
    } 

    public static Result getOperations(List<Integer> numbers, int midNumber, int target) 
    { 
     Result midResult = new Result(); 
     if (midNumber == target) { 
      midResult.success = true; 
      midResult.output = ""; 
      return midResult; 
     } 
     for (Integer number : numbers) { 
      List<Integer> newList = new ArrayList<Integer>(numbers); 
      newList.remove(number); 
      if (newList.isEmpty()) { 
       if (midNumber - number == target) { 
        midResult.success = true; 
        midResult.output = "-" + number; 
        return midResult; 
       } 
       if (midNumber + number == target) { 
        midResult.success = true; 
        midResult.output = "+" + number; 
        return midResult; 
       } 
       if (midNumber * number == target) { 
        midResult.success = true; 
        midResult.output = "*" + number; 
        return midResult; 
       } 
       if (midNumber/number == target) { 
        midResult.success = true; 
        midResult.output = "/" + number; 
        return midResult; 
       } 
       midResult.success = false; 
       midResult.output = "f" + number; 
       return midResult; 
      } else { 
       midResult = getOperations(newList, midNumber - number, target); 
       if (midResult.success) { 
        midResult.output = "-" + number + midResult.output; 
        return midResult; 
       } 
       midResult = getOperations(newList, midNumber + number, target); 
       if (midResult.success) { 
        midResult.output = "+" + number + midResult.output; 
        return midResult; 
       } 
       midResult = getOperations(newList, midNumber * number, target); 
       if (midResult.success) { 
        midResult.output = "*" + number + midResult.output; 
        return midResult; 
       } 
       midResult = getOperations(newList, midNumber/number, target); 
       if (midResult.success) { 
        midResult.output = "/" + number + midResult.output; 
        return midResult 
       } 
      } 

     } 
     return midResult; 
    } 
} 

UPDATE

它基本上只是簡單的蠻力算法指數複雜。 但是，通過利用一些啓發式功能可以獲得一些改進，這些功能將幫助您對數字序列或（和）操作進行排序，以便在函數遞歸的每個級別中進行處理。

這樣的啓發式函數的例子是例如中間結果和總目標結果之間的差異。

然而，只有最佳情況和平均情況的複雜性得到改善。最壞的情況複雜性保持不變。

最壞的情況下的複雜性可以通過某種分支切割來改善。我不確定在這種情況下是否可能。

Answer 2

確保它的指數，但它是微小所​​以一個好的（足夠的）天真的實施將是一個良好的開端。我建議你使用括號刪除通常的中綴表示法，並使用postfix，這樣編程起來更容易。你總是可以將輸出美化爲一個單獨的階段。

首先列出並評估所有（有效）的數字和運算符序列。例如（在後綴）：

1 3 7 6 8 3 + + + + + -> 28 
1 3 7 6 8 3 + + + + - -> 26 

我的Java是可笑的，我不來這兒，所以我會離開這個編碼由你來被人嘲笑。

要將所有聰明的人閱讀本：是的，我知道，這樣即使是很小的問題有更聰明的方法，其很可能會更快，我只是指着OP對初始工作的解決方案。其他人可以用更智能的解決方案寫出答案。

因此，要回答你的問題：

• 我開始一個算法，我想會很快導致我到一個有效的解決方案。在這種情況下，對我來說顯而易見的選擇是詳盡列舉和測試所有可能的計算。
• 如果顯而易見的算法由於性能原因看起來沒有吸引力，我會開始更深入地思考它，回想一下我知道哪些算法可能會提供更好的性能。相反，我可能會先開始編寫其中一個。
• 如果我堅持使用詳盡的算法，並發現運行時間實際上太長，那麼我可能會返回到上一步並再次編碼。但它必須是值得我的，有一個成本/效益評估 - 只要我的代碼可以勝過Rachel Riley我會很滿意。
• 的重要考慮因素包括我的時間VS電腦的時候，我的花費宏大得多。

Answer 3

我想，你需要首先嚴格定義問題。你被允許做什麼和你不是什麼。您可以先簡單化，只允許乘法，除法，減法和加法。

現在你知道你的問題與空間設置的投入，設置可用操作和所需的投入。如果您只有4個操作和x個輸入，則組合的數量少於：

您可以執行操作（x！）乘以每個步驟的可能操作選項的次數：4^x 。正如你所看到的6個數字，它給出了合理的2949120操作。這意味着這可能是您對蠻力算法的限制。

一旦你有蠻力，你知道它的工作原理，你可以開始改進你的算法與某種A* algorithm這需要你定義啓發式功能。

在我看來，最好的思考方式就是搜索問題。主要困難在於尋找好的啓發式方法，或者減少問題空間的方法（如果你的數字不能合計答案，至少需要一次乘法等）。從小處着手，一旦你有了一些代碼，就可以繼續提問。

Answer 4

輸入顯然是一組數字和運算符：D = {1,3,3,6,7,8,3}和Op = {+， - ，*，/}。最直接的算法將是一個brute force求解器，其中enumerates這些組合的所有可能的組合。如果集合Op的元素可以按照想要的頻率使用，但集合D中的元素只能使用一次。僞代碼：

D={1,3,3,6,7,8,3} 
Op={+,-,*,/} 
Solution=348 
for each permutation D_ of D: 
    for each binary tree T with D_ as its leafs: 
     for each sequence of operators Op_ from Op with length |D_|-1: 
      label each inner tree node with operators from Op_ 
      result = compute T using infix traversal 
      if result==Solution 
       return T 
return nil 

除此之外：請閱讀jedrus07和HPM的答案。

Answer 5

下面的C++ 11中的工作解決方案。

基本思想是使用基於堆棧的評估（請參閱RPN）並將可行解決方案轉換爲infix notation以僅用於顯示目的。

如果我們有N輸入數字，我們將使用(N-1)運算符，因爲每個運算符都是二進制的。

首先我們創建有效排列的操作數和運算符（selector_數組）。有效的置換是可以在沒有堆棧下溢的情況下進行評估並且以堆棧中的一個值（結果）結束的置換。因此1 1 +是有效的，但1 + 1不是。

我們用每個操作數排列（values_數組）和每個操作符組合（ops_數組）測試每個這樣的操作數運算符置換。匹配結果相當漂亮。

參數取自命令行[-s] <target> <digit>[ <digit>...]。 -s開關可防止詳盡搜索，只打印第一個匹配結果。

（使用./mathpuzzle 348 1 3 7 6 8 3得到答案了原來的問題）

此解決方案不允許串接輸入數字形成數字。這可以作爲額外的外部循環添加。

工作代碼可以從here下載。 （注：我更新了代碼，支持拼接輸入數字以形成解決方案）

請參閱代碼註釋以獲取更多解釋。

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <stack> 
#include <iterator> 
#include <string> 

namespace { 

enum class Op { 
    Add, 
    Sub, 
    Mul, 
    Div, 
}; 

const std::size_t NumOps = static_cast<std::size_t>(Op::Div) + 1; 
const Op FirstOp = Op::Add; 

using Number = int; 

class Evaluator { 
    std::vector<Number> values_; // stores our digits/number we can use 
    std::vector<Op> ops_; // stores the operators 
    std::vector<char> selector_; // used to select digit (0) or operator (1) when evaluating. should be std::vector<bool>, but that's broken 

    template <typename T> 
    using Stack = std::stack<T, std::vector<T>>; 

    // checks if a given number/operator order can be evaluated or not 
    bool isSelectorValid() const { 
     int numValues = 0; 
     for (auto s : selector_) { 
      if (s) { 
       if (--numValues <= 0) { 
        return false; 
       } 
      } 
      else { 
       ++numValues; 
      } 
     } 
     return (numValues == 1); 
    } 

    // evaluates the current values_ and ops_ based on selector_ 
    Number eval(Stack<Number> &stack) const { 
     auto vi = values_.cbegin(); 
     auto oi = ops_.cbegin(); 
     for (auto s : selector_) { 
      if (!s) { 
       stack.push(*(vi++)); 
       continue; 
      } 
      Number top = stack.top(); 
      stack.pop(); 
      switch (*(oi++)) { 
       case Op::Add: 
        stack.top() += top; 
        break; 
       case Op::Sub: 
        stack.top() -= top; 
        break; 
       case Op::Mul: 
        stack.top() *= top; 
        break; 
       case Op::Div: 
        if (top == 0) { 
         return std::numeric_limits<Number>::max(); 
        } 
        Number res = stack.top()/top; 
        if (res * top != stack.top()) { 
         return std::numeric_limits<Number>::max(); 
        } 
        stack.top() = res; 
        break; 
      } 
     } 
     Number res = stack.top(); 
     stack.pop(); 
     return res; 
    } 

    bool nextValuesPermutation() { 
     return std::next_permutation(values_.begin(), values_.end()); 
    } 

    bool nextOps() { 
     for (auto i = ops_.rbegin(), end = ops_.rend(); i != end; ++i) { 
      std::size_t next = static_cast<std::size_t>(*i) + 1; 
      if (next < NumOps) { 
       *i = static_cast<Op>(next); 
       return true; 
      } 
      *i = FirstOp; 
     } 
     return false; 
    } 

    bool nextSelectorPermutation() { 
     // the start permutation is always valid 
     do { 
      if (!std::next_permutation(selector_.begin(), selector_.end())) { 
       return false; 
      } 
     } while (!isSelectorValid()); 
     return true; 
    } 

    static std::string buildExpr(const std::string& left, char op, const std::string &right) { 
     return std::string("(") + left + ' ' + op + ' ' + right + ')'; 
    } 

    std::string toString() const { 
     Stack<std::string> stack; 
     auto vi = values_.cbegin(); 
     auto oi = ops_.cbegin(); 
     for (auto s : selector_) { 
      if (!s) { 
       stack.push(std::to_string(*(vi++))); 
       continue; 
      } 
      std::string top = stack.top(); 
      stack.pop(); 
      switch (*(oi++)) { 
       case Op::Add: 
        stack.top() = buildExpr(stack.top(), '+', top); 
        break; 
       case Op::Sub: 
        stack.top() = buildExpr(stack.top(), '-', top); 
        break; 
       case Op::Mul: 
        stack.top() = buildExpr(stack.top(), '*', top); 
        break; 
       case Op::Div: 
        stack.top() = buildExpr(stack.top(), '/', top); 
        break; 
      } 
     } 
     return stack.top(); 
    } 

public: 
    Evaluator(const std::vector<Number>& values) : 
      values_(values), 
      ops_(values.size() - 1, FirstOp), 
      selector_(2 * values.size() - 1, 0) { 
     std::fill(selector_.begin() + values_.size(), selector_.end(), 1); 
     std::sort(values_.begin(), values_.end()); 
    } 

    // check for solutions 
    // 1) we create valid permutations of our selector_ array (eg: "1 1 + 1 +", 
    // "1 1 1 + +", but skip "1 + 1 1 +" as that cannot be evaluated 
    // 2) for each evaluation order, we permutate our values 
    // 3) for each value permutation we check with each combination of 
    // operators 
    // 
    // In the first version I used a local stack in eval() (see toString()) but 
    // it turned out to be a performance bottleneck, so now I use a cached 
    // stack. Reusing the stack gives an order of magnitude speed-up (from 
    // 4.3sec to 0.7sec) due to avoiding repeated allocations. Using 
    // std::vector as a backing store also gives a slight performance boost 
    // over the default std::deque. 
    std::size_t check(Number target, bool singleResult = false) { 
     Stack<Number> stack; 

     std::size_t res = 0; 
     do { 
      do { 
       do { 
        Number value = eval(stack); 
        if (value == target) { 
         ++res; 
         std::cout << target << " = " << toString() << "\n"; 
         if (singleResult) { 
          return res; 
         } 
        } 
       } while (nextOps()); 
      } while (nextValuesPermutation()); 
     } while (nextSelectorPermutation()); 
     return res; 
    } 
}; 

} // namespace 

int main(int argc, const char **argv) { 
    int i = 1; 
    bool singleResult = false; 
    if (argc > 1 && std::string("-s") == argv[1]) { 
     singleResult = true; 
     ++i; 
    } 
    if (argc < i + 2) { 
     std::cerr << argv[0] << " [-s] <target> <digit>[ <digit>]...\n"; 
     std::exit(1); 
    } 
    Number target = std::stoi(argv[i]); 
    std::vector<Number> values; 
    while (++i < argc) { 
     values.push_back(std::stoi(argv[i])); 
    } 
    Evaluator evaluator{values}; 
    std::size_t res = evaluator.check(target, singleResult); 
    if (!singleResult) { 
     std::cout << "Number of solutions: " << res << "\n"; 
    } 
    return 0; 
} 

Answer 6

很久以前我在Oxford's Computer Science Docs（帶有Java源代碼）中發現了很好的算法。每次閱讀此解決方案時，我都很佩服它。我相信這會有所幫助。