C++算法实现24点游戏 |21xrx.com

C++算法实现24点游戏

2023-07-01 11:44:41 深夜i 120 0

C++ 算法实现 24点游戏数字计算循环嵌套

return c == '+' || c == '-' || c == '*' || c == '/';

24点游戏是一款智力类游戏，需要玩家通过组合运算使得四张扑克牌得到24点。在计算机科学中，可以使用C++算法实现24点游戏。

首先，我们需要明确一个知识点，即后缀表达式。后缀表达式也称为逆波兰表达式，是一种不依赖括号顺序即可确定运算顺序的表达式。例如，后缀表达式“3 4 + 5 *”等价于中缀表达式“3 + 4 * 5”。我们可以使用C++的栈来实现后缀表达式的计算。

接下来，我们考虑如何将四张扑克牌转换成后缀表达式。我们可以使用递归的思想，枚举每一对数字及其运算符号，将其转换成子表达式，然后递归求解子表达式，直到得到整个后缀表达式。

对于如何判断四张扑克牌能否得到24点，我们可以使用回溯法。从四张扑克牌中任选两张，进行加、减、乘、除四种运算，然后将得到的结果与剩余的两张扑克牌组合成新的四张扑克牌，重复上述过程，直到得到结果为24或者无法再进行运算为止。

下面是一份简单的C++代码实现24点游戏：

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
bool is_operator(char c) {
  return c == '+' || c == '-' || c == '*' || c == '/';
}
int calculate(int a, int b, char op) {
  if (op == '+') {
    return a + b;
  } else if (op == '-')
    return a - b;
   else if (op == '*') {
    return a * b;
  } else if (op == '/')
    return a / b;
  
  return 0; // should never and will never reach here
}
int evaluate(vector<string>& postfix) {
  stack<int> s;
  for (int i = 0; i < postfix.size(); i++) {
    if (!is_operator(postfix[i][0])) {
      int num = stoi(postfix[i]);
      s.push(num);
    } else {
      int b = s.top();
      s.pop();
      int a = s.top();
      s.pop();
      s.push(calculate(a, b, postfix[i][0]));
    }
  }
  return s.top();
}
bool search(vector<int>& nums, vector<char>& ops) {
  if (nums.size() == 1) {
    return nums[0] == 24;
  }
  for (int i = 0; i < nums.size(); i++) {
    for (int j = 0; j < nums.size(); j++) {
      if (i == j)
        continue;
      
      for (char op : ops) {
        if (op == '/' && nums[j] == 0)
          continue;
        
        vector<int> new_nums;
        for (int k = 0; k < nums.size(); k++) {
          if (k != i && k != j) {
            new_nums.push_back(nums[k]);
          }
        }
        new_nums.push_back(calculate(nums[i], nums[j], op));
        if (search(new_nums, ops))
          return true;
        
      }
    }
  }
  return false;
}
bool can_get_24(vector<int>& nums) {
  vector<char> ops{'+', '-', '*', '/'};
  return search(nums, ops);
}
bool dfs(vector<int>& nums, vector<string>& postfix) {
  if (postfix.size() == 7) {
    return evaluate(postfix) == 24;
  }
  for (int i = 0; i < nums.size(); i++) {
    for (int j = i + 1; j < nums.size(); j++) {
      int a = nums[i];
      int b = nums[j];
      int c = -1;
      postfix.push_back(to_string(a));
      postfix.push_back(to_string(b));
      for (char op : {'+', '-', '*', '/'}) {
        if (op == '/' && b == 0)
          continue;
        
        c = calculate(a, b, op);
        postfix.push_back(string(1, op));
        if (dfs(vector<int>{c}, postfix))
          return true;
        
        postfix.pop_back();
      }
      postfix.pop_back();
      postfix.pop_back();
    }
  }
  return false;
}
bool can_get_24(vector<int>& nums) {
  vector<string> postfix;
  return dfs(nums, postfix);
}
int main() {
  vector<int> nums 2;
  cout << can_get_24(nums) << endl;
  return 0;
}

这份代码实现了两种算法，一种是回溯法，一种是先将四张扑克牌转换成后缀表达式，然后使用栈来计算结果。两种算法都可以正确地解决24点游戏。

上一篇: idea打包java可执行jar包

下一篇: C++如何打印十六进制数

评论区

相似文章