学步园

分治法:

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

集合的二进制表示法:

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

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

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

Code:

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