在進行順序計算時保持操作順序

Question

我正在花費我的晚上從Kattis處理一些編程問題。有一部分問題4 thought，我卡住了。

給出一個數字，該程序應該返回4個數據之間所需的運算（+， - ，*或/）以實現該數字。

例如，輸入

9 

會導致輸出

4 + 4 + 4/4 = 9 

我的解決方案（效率不高，但是簡單）是評估所有可能的方式向運營商結合上面看如果任何組合達到想要的結果。

要做到這一點，我寫了下面的功能。它需要一組字符串，它們是要評估的運算符（uo[3]，可能看起來像{+, /, *}），並且需要的結果爲整數（expRes）。

bool check(char uo[3], int expRes) { 
    int res = 4; 
    for(int oPos = 2; oPos >= 0; oPos--) { 
     switch (uo[oPos]) { 
      case '+' : res += 4; break; 
      case '-' : res -= 4; break; 
      case '*' : res *= 4; break; 
      case '/' : res /= 4; break; 
     } 
    } 
    return res == expRes;  
} 

我意識到這種「順序」方法帶來一個問題：它不遵循操作順序。如果我打電話給 uo = {+, -, /} 和 expRes = 7這個函數，它會返回false，因爲4 + 4 = 8,8-4 = 4,4/4 = 1. 真正的答案顯然是真的，因爲4 + 4 - 4/4 = 7.

你們有沒有想過重寫函數的方法，以便評估遵循操作順序？

在此先感謝！

Answer 1

如果你看看它，這是一個簡單的問題。

你被四個4和3個操作員限制在中間，那你已經知道你的搜索空間了。因此，一種解決方案是生成完整的搜索空間，即O（n^3）= 4^3 = 64個總方程，其中n是運算符的數量。將這些解決方案的答案保留爲<key, value>對，以便查找測試用例的輸入爲O（1）。

明智的你會做。

1. 生成完整的序列，並將其存儲爲鍵，值對
2. 接受輸入從測試用例
3. 檢查是否存在的關鍵，如果是打印順序，否則打印序列不存在
4. 解將採取64點* 1000點的操作，其可以容易地與在第二計算，並能避免時間超出限制的錯誤，通常這些比賽在代碼形式具有

（大部分是不完全的）：

// C++ Syntax 
map<int, string> mp; 

void generateAll() { 
    // generate all equations 
} 

void main() { 
    generateAll(); 

    int n, t; scanf("%d", &t); 
    while (t--) { 
     scanf("%d", &n); 

     if (mp.find(n) != mp.end()) 
      // equation exists to the input 
     else 
      // equation doesn't exist for the input 
    } 
}