c++ - 编写 C++ 版本的代数游戏 24

Question

我正在尝试编写一个像 24 游戏一样工作的 C++ 程序。对于那些不知道它是如何玩的人，基本上你试图通过 + 的四个代数运算符找到 4 个数字总和为 24 的任何方式、-、/、* 和括号。

举个例子，假设有人输入 2,3,1,5((2+3)*5) - 1 = 24

由于括号的位置有限，编写确定三个数字是否可以得到 24 的函数相对简单，但我不知道当输入四个变量时如何有效地编写代码。

---

我现在可以使用一些排列，但我仍然无法枚举所有情况，因为我不知道如何为操作相同的情况编写代码。

另外，计算 RPN 最简单的方法是什么？我遇到了很多页面，例如这一页: http://www.dreamincode.net/forums/index.php?showtopic=15406但作为初学者，我不确定如何实现它。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;





bool MakeSum(int num1, int num2, int num3, int num4)
{

  vector<int> vi;
  vi.push_back(num1);
  vi.push_back(num2);
  vi.push_back(num3);
  vi.push_back(num4);

  sort(vi.begin(),vi.end());


  char a1 = '+';
  char a2 = '-';
  char a3 = '*';
  char a4 = '/';
  vector<char> va;
  va.push_back(a1);
  va.push_back(a2);
  va.push_back(a3);
  va.push_back(a4);

  sort(va.begin(),va.end());
  while(next_permutation(vi.begin(),vi.end()))
    {

      while(next_permutation(va.begin(),va.end()))
    {

      cout<<vi[0]<<vi[1]<<vi[2]<<vi[3]<< va[0]<<va[1]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< vi[3]<<va[1]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< va[1]<<vi[3]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< vi[3]<<va[1]<<va[2]<<endl;

      cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< va[1]<<vi[3]<<va[2]<<endl; 


    }

    }

  return 0;

}

int main()
{

  MakeSum(5,7,2,1);
  return 0;
}

Answer 1

因此，简单的方法是排列所有可能的组合。这有点棘手，数字的顺序可能很重要，当然运算顺序也很重要。

一个观察结果是您正在尝试生成具有特定属性的所有可能的表达式树。一个属性是树总是恰好有 4 个叶子。这意味着树也将始终恰好有 3 个内部节点。这样一棵树只有 3 种可能的形状:

  A
 / \
 N  A
   / \      (and the mirror image)
  N   A
     / \
    N   N

  A
 / \
N   A
   / \
  A   N   (and the mirror image)
 / \
N   N

     A
   /` `\
  A     A
 / \   / \
N  N  N  N

在 A 的每个点中，您可以进行 4 种操作中的任何一种。在 N 的每个位置中，您可以有任何一个数字。但是每个数字只能出现一个N。

将其编码为暴力搜索应该不会太难，我认为在您以这种方式完成事情之后，考虑优化会变得更容易。

例如，+ 和* 是可交换的。这意味着翻转这些操作的左右子节点的镜像将不起作用。有可能减少对所有此类翻转的搜索。

其他人提到了 RPN 表示法。树直接映射到这个。以下是 RPN 中所有可能树的列表:

N N N N A A A
N N N A N A A
N N N A A N A
N N A N N A A
N N A N A N A

那是 4*3*2 = 24 种数字的可能性，4*4*4 = 64 种运算的可能性，24 * 64 * 5 = 7680 种给定的 4 个数字集合的总可能性。易于计数，并且可以在现代系统上在几分之一秒内进行评估。哎呀，即使在我的旧 Atari 8 位基础上，我敢打赌对于给定的一组 4 个数字，这个问题只需要几分钟。