编写C ++版本的代数游戏24 [英] Writing a C++ version of the algebra game 24

问题描述

我正在尝试编写一个类似于游戏24的C ++程序.对于那些不知道如何玩的人，基本上，您会尝试通过+的四个代数运算符找到4个数字总计为24的任何方式，-，/，*和括号.

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

由于括号的位置数量有限，因此对函数进行编码以确定三个数字是否可以使24变为24相对简单，但是输入四个变量时，我无法确定如何有效地对其进行编码.

---

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

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

  #include< iostream>#include< vector>#include< algorithm>使用命名空间std;bool MakeSum(int num1，int num2，int num3，int num4){向量< 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 ='/';向量< 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;}}返回0;}int main(){MakeSum(5,7,2,1);返回0;} 

解决方案

因此，简单的方法是通过所有可能的组合进行置换.这有点棘手，数字的顺序可能很重要，当然运算的顺序也很重要.

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

  A/\A/\(和镜像)A/\N N一种/\A/\N(和镜像)/\N N一种/``\A A///N N N N 

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

将其编码为蛮力搜索应该不会太难，而且我认为以这种方式完成工作之后，考虑优化问题将变得更加容易.

例如， + 和 * 是可交换的.这意味着翻转那些操作的左子级和右子级的镜像将无效.可能可以减少所有此类翻转的搜索.

有人提到RPN表示法.树木直接映射到此.这是RPN中所有可能的树的列表:

  N N N N A A A AN N N A N A AN N N A A N AN N A N N A AN N A N A N A 

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

I am trying to write a C++ program that works like the game 24. For those who don't know how it is played, basically you try to find any way that 4 numbers can total 24 through the four algebraic operators of +, -, /, *, and parenthesis.

As an example, say someone inputs 2,3,1,5 ((2+3)*5) - 1 = 24

It was relatively simple to code the function to determine if three numbers can make 24 because of the limited number of positions for parenthesis, but I can not figure how code it efficiently when four variables are entered.

---

I have some permutations working now but I still cannot enumerate all cases because I don't know how to code for the cases where the operations are the same.

Also, what is the easiest way to calculate the RPN? I came across many pages such as this one: http://www.dreamincode.net/forums/index.php?showtopic=15406 but as a beginner, I am not sure how to implement it.

#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;
}

解决方案

So, the simple way is to permute through all possible combinations. This is slightly tricky, the order of the numbers can be important, and certainly the order of operations is.

One observation is that you are trying to generate all possible expression trees with certain properties. One property is that the tree will always have exactly 4 leaves. This means the tree will also always have exactly 3 internal nodes. There are only 3 possible shapes for such a tree:

  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

In each spot for A you can have any one of the 4 operations. In each spot for N you can have any one of the numbers. But each number can only appear for one N.

Coding this as a brute force search shouldn't be too hard, and I think that after you have things done this way it will become easier to think about optimizations.

For example, + and * are commutative. This means that mirrors that flip the left and right children of those operations will have no effect. It might be possible to cut down searching through all such flips.

Someone else mentioned RPN notation. The trees directly map to this. Here is a list of all possible trees in 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

That's 4*3*2 = 24 possibilities for numbers, 4*4*4 = 64 possibilities for operations, 24 * 64 * 5 = 7680 total possibilities for a given set of 4 numbers. Easily countable and can be evaluated in a tiny fraction of a second on a modern system. Heck, even in basic on my old Atari 8 bit I bet this problem would only take minutes for a given group of 4 numbers.

这篇关于编写C ++版本的代数游戏24的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！