编程之美: 24点游戏的解法

曾经终败给现在 2022-07-12 06:43 125阅读 0赞

分治法:

把A=\{e,f,a,b\}分治成为B=\{e,f,a+b\}, C=\{e,f,a-b\}, D=\{e,f,b-a\}, E=\{e,f,a\*b\}, F=\{e,f,a/b\}, G=\{e,f,b/a\} 这样5个元素个数等于3的集合.

这样就把A中元素运算等于24, 转化为B或C或D或E或F或G中元素运算等于24.

这展示了有关集合运算的一种方法: 元素合并, 转化为元素更少的集合.

Code:

\#include <iostream> \#include <exception> \#include <string> \#include <stdexcept> \#include <cmath> using namespace std; const int N = 4; const double RESULT = 24.0; const double DEGREE = 1e-6; double num\[N\]; string strRet\[N\]; bool pointGame(int n) \{ if(n == 1) \{ if(fabs(num\[0\] - RESULT) < DEGREE) \{ cout << strRet\[0\] << endl; return true; \} else \{ return false; \} \} for(int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) \{ double tempA = num\[i\]; double tempB = num\[j\]; num\[j\] = num\[n-1\]; string expA = strRet\[i\]; string expB = strRet\[j\]; strRet\[j\] = strRet\[n-1\]; strRet\[i\] = '(' + expA + '+' + expB + ')'; num\[i\] = tempA + tempB; if(pointGame(n-1)) return true; strRet\[i\] = '(' + expA + '-' + expB + ')'; num\[i\] = tempA - tempB; if(pointGame(n-1)) return true; strRet\[i\] = '(' + expB + '-' + expA + ')'; num\[i\] = tempB - tempA; if(pointGame(n-1)) return true; strRet\[i\] = '(' + expA + '\*' + expB + ')'; num\[i\] = tempA \* tempB; if(pointGame(n-1)) return true; if(tempB) \{ strRet\[i\] = '(' + expA + '/' + expB + ')'; num\[i\] = tempA/tempB; if(pointGame(n-1)) return true; \} if(tempA) \{ strRet\[i\] = '(' + expB + '/' + expA + ')'; num\[i\] = tempB/tempA; if(pointGame(n-1)) return true; \} num\[i\] = tempA; num\[j\] = tempB; strRet\[i\] = expA; strRet\[j\] = expB; \} return false; \} int main() \{ while (scanf("%lf%lf%lf%lf", &num\[0\], &num\[1\], &num\[2\], &num\[3\]) != EOF) \{ for (int i = 0; i < N; ++i) \{ char buffer\[20\]; itoa((int)num\[i\], buffer, 10); strRet\[i\] = buffer; \} if(!pointGame(N)) cout << "No result" << endl; \} return 0; \}

集合的二进制表示法:

可以将元素个数为N集合的集合, 用0 ~ (2<<N)-1表示出所有子集.

从而可以利用二进制表示方便得到子集等操作.

对于本题, 还可以利用重复子问题, 减少重复计算.

Code:

\#include <iostream> \#include <exception> \#include <string> \#include <stdexcept> \#include <cmath> \#include <set> using namespace std; const int N = 4; const double RESULT = 24.0; const double DEGREE = 1e-6; double num\[N\]; set<double> s\[(1<<N)\]; void f(int n) \{ if(s\[n\].size() != 0) return; for(int i = 1; i < n; ++i) if((i&n) == i) \{ f(i); f(n-i); for (set<double>::iterator itr1 = s\[i\].begin(); itr1 != s\[i\].end(); ++itr1) for (set<double>::iterator itr2 = s\[n-i\].begin(); itr2 != s\[n-i\].end(); ++itr2) \{ double a = \*itr1; double b = \*itr2; s\[n\].insert(a + b); s\[n\].insert(a - b); s\[n\].insert(b - a); s\[n\].insert(a \* b); if(b) s\[n\].insert(a / b); if(a) s\[n\].insert(b / a); \} \} \} int main() \{ for (int i = 0; i < N; ++i) \{ cin >> num\[i\]; s\[(1<<i)\].insert((double)num\[i\]); \} for(int i = 1; i <= (1<<N)-1; ++i) f(i); for(set<double>::iterator itr = s\[(1<<N)-1\].begin(); itr != s\[(1<<N)-1\].end(); ++itr) if(fabs(\*itr - RESULT) < DEGREE) cout << "Has an result" << endl; return 0; \}