我正在尝试编写一个类似于游戏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;
}
因此,简单的方法是通过所有可能的组合进行置换.这有点棘手,数字的顺序可能很重要,当然操作的顺序也是如此.
一个观察是您尝试生成具有某些属性的所有可能的表达式树.一个属性是树总是有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个数字.
小智 6
您可以使用反向波兰表示法生成可能的表达式,这样可以消除对parantheses的需要.
绝对天真的方法是生成所有可能的4位数字符串和3个运算符(不注意作为RPN的有效性),假设它在RPN中并尝试对其进行评估.您将遇到一些错误情况(如在无效的RPN字符串中).可能性的总数(如果我正确计算)是~50,000.
一个更聪明的方法应该降低到~7500我相信(确切地说是64*24*5):生成数字的排列(24种方式),生成3个运算符的三元组(4 ^ 3 = 64种方式)和现在将运算符放在数字中以使其成为有效的RPN(有5种方法,请参阅Omnifarious的回答).
您应该能够在网上轻松找到排列发生器和RPN计算器.
希望有所帮助!
PS:仅供参考:RPN只是相应表达式树的后序遍历,对于d位数,数字是d!*4 ^(d-1)*选择(2(d-1),(d-1))/ d.(最后一个词是加泰罗尼亚语号).