fork(1) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <set>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9. // 浮点数比较精度
  10. const double EPS = 1e-6;
  11.  
  12. // 判断两个浮点数是否相等
  13. bool equals(double a, double b) {
  14. return fabs(a - b) < EPS;
  15. }
  16.  
  17. // 递归计算所有可能的表达式
  18. void calculate(vector<double>& nums, vector<string>& exprs, set<string>& results) {
  19. if (nums.size() == 1) {
  20. // 如果结果等于24,添加到结果集
  21. if (equals(nums[0], 24.0)) {
  22. results.insert(exprs[0]);
  23. }
  24. return;
  25. }
  26.  
  27. // 尝试所有可能的两个数的组合
  28. for (int i = 0; i < nums.size(); ++i) {
  29. for (int j = i + 1; j < nums.size(); ++j) { // 只考虑i < j的情况,避免重复计算
  30. // 取出两个数
  31. double a = nums[i];
  32. double b = nums[j];
  33. string expr_a = exprs[i];
  34. string expr_b = exprs[j];
  35.  
  36. // 创建新的数字和表达式列表(排除已使用的两个数)
  37. vector<double> new_nums;
  38. vector<string> new_exprs;
  39. for (int k = 0; k < nums.size(); ++k) {
  40. if (k != i && k != j) {
  41. new_nums.push_back(nums[k]);
  42. new_exprs.push_back(exprs[k]);
  43. }
  44. }
  45.  
  46. // 加法 (满足交换律,只计算一次)
  47. new_nums.push_back(a + b);
  48. new_exprs.push_back("(" + expr_a + " + " + expr_b + ")");
  49. calculate(new_nums, new_exprs, results);
  50. new_nums.pop_back();
  51. new_exprs.pop_back();
  52.  
  53. // 减法 (不满足交换律,计算两种情况)
  54. new_nums.push_back(a - b);
  55. new_exprs.push_back("(" + expr_a + " - " + expr_b + ")");
  56. calculate(new_nums, new_exprs, results);
  57. new_nums.pop_back();
  58. new_exprs.pop_back();
  59.  
  60. new_nums.push_back(b - a);
  61. new_exprs.push_back("(" + expr_b + " - " + expr_a + ")");
  62. calculate(new_nums, new_exprs, results);
  63. new_nums.pop_back();
  64. new_exprs.pop_back();
  65.  
  66. // 乘法 (满足交换律,只计算一次)
  67. new_nums.push_back(a * b);
  68. new_exprs.push_back("(" + expr_a + " * " + expr_b + ")");
  69. calculate(new_nums, new_exprs, results);
  70. new_nums.pop_back();
  71. new_exprs.pop_back();
  72.  
  73. // 除法 (不满足交换律,计算两种情况,避免除以0)
  74. if (!equals(b, 0.0)) {
  75. new_nums.push_back(a / b);
  76. new_exprs.push_back("(" + expr_a + " / " + expr_b + ")");
  77. calculate(new_nums, new_exprs, results);
  78. new_nums.pop_back();
  79. new_exprs.pop_back();
  80. }
  81.  
  82. if (!equals(a, 0.0)) {
  83. new_nums.push_back(b / a);
  84. new_exprs.push_back("(" + expr_b + " / " + expr_a + ")");
  85. calculate(new_nums, new_exprs, results);
  86. new_nums.pop_back();
  87. new_exprs.pop_back();
  88. }
  89. }
  90. }
  91. }
  92.  
  93. // 处理结果,移除最外层括号
  94. vector<string> processResults(set<string>& results) {
  95. vector<string> res;
  96. for (const string& s : results) {
  97. if (s.front() == '(' && s.back() == ')') {
  98. res.push_back(s.substr(1, s.size() - 2));
  99. } else {
  100. res.push_back(s);
  101. }
  102. }
  103. return res;
  104. }
  105.  
  106. int main() {
  107. // 读取4个输入数字
  108. int nums[4];
  109. for (int i = 0; i < 4; ++i) {
  110. cin >> nums[i];
  111. // 检查输入是否为小于20的正整数
  112. if (nums[i] <= 0 || nums[i] >= 20) {
  113. cerr << "输入必须是小于20的正整数" << endl;
  114. return 1;
  115. }
  116. }
  117.  
  118. // 初始化数字和表达式列表
  119. vector<double> num_vec;
  120. vector<string> expr_vec;
  121. for (int i = 0; i < 4; ++i) {
  122. num_vec.push_back(double(nums[i]));
  123. expr_vec.push_back(to_string(nums[i]));
  124. }
  125.  
  126. // 存储所有有效的表达式
  127. set<string> results;
  128.  
  129. // 计算所有可能的表达式
  130. calculate(num_vec, expr_vec, results);
  131.  
  132. // 处理结果
  133. vector<string> final_results = processResults(results);
  134.  
  135. // 输出结果
  136. if (final_results.empty()) {
  137. cout << "No solution" << endl;
  138. } else {
  139. for (const string& s : final_results) {
  140. cout << s << endl;
  141. }
  142. }
  143.  
  144. return 0;
  145. }
  146.  
Success #stdin #stdout 0.01s 5288KB
stdin
 1 8 12 12
stdout
12 / ((12 / 8) - 1)