Test SRM Level Two: CountExpressions， Brute Force

 

這道題目跟撲克牌算24的題目比較像，但要簡單一些。點擊查看 next_permutation 函數 的用法，使用這個函數減輕了不少工作量，而且算法很簡潔明了。

 

代碼如下：

#include <iostream> #include <vector> #include <algorithm> using namespace std; class CountExpressions { public: int calcExpressions(int x, int y, int val); }; int CountExpressions::calcExpressions(int x, int y, int val) { int i, j, k; int sum, count; vector <int> vnum; if (x > y) { swap(x, y); } /* 保證 x < y */ vnum.push_back(x); vnum.push_back(x); vnum.push_back(y); vnum.push_back(y); sum = 0; count = 0; do { for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { for (k = 0; k < 3; k++) { switch (i) { case 0: sum = vnum[0] + vnum[1]; break; case 1: sum = vnum[0] - vnum[1]; break; case 2: sum = vnum[0] * vnum[1]; break; } switch (j) { case 0: sum = sum + vnum[2]; break; case 1: sum = sum - vnum[2]; break; case 2: sum = sum * vnum[2]; break; } switch (k) { case 0: sum = sum + vnum[3]; break; case 1: sum = sum - vnum[3]; break; case 2: sum = sum * vnum[3]; break; } if (sum == val) { ++count; } } } } } while (next_permutation(vnum.begin(), vnum.end())); /* 4個數字不同的排列組合 */ return count; }