主题：【原创】将24进行到底 -- 泰让
家园 【原创】将24进行到底 这是答应过面壁同学的c原码，因为周末在玩新买的电视，加上犯懒，所以晚了.
稍后将给出算法的解释.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define TAGET 24
#define NOP 4
#define EOP NOP*2-1
int comp[EOP];
double op[NOP];
int validate(void ){
int top=0;
double stack[NOP];
int i=0;
for (i=0;i<EOP;i++) {
if (comp[i]<=NOP) {
stack[top]=op[comp[i]-1];
top++;
} else {
switch (comp[i]-NOP) {
case 1:
top--;
stack[top-1]+=stack[top];
break;
case 2:
top--;
stack[top-1]-=stack[top];
break;
case 3:
top--;
stack[top-1]*=stack[top];
break;
case 4:
top--;
if (stack[top]==0)
return 0;
stack[top-1]/=stack[top];
break;
}
}
}
if (fabs(stack[0]-TAGET)<=1e-5)
return 1;
else
return 0;
}
void output(void ) {
int i;
int top=0;
char* stack[EOP];
char tempstr[255];
for (i=0;i<EOP;i++) {
stack[i]=malloc(255*sizeof(char));
}
for (i=0;i<EOP;i++) {
if (comp[i]<=NOP) {
sprintf(stack[top]," %d ",(int)op[comp[i]-1]);
top++;
} else {
switch (comp[i]-NOP) {
case 1:
top--;
sprintf(tempstr,"(%s+%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 2:
top--;
sprintf(tempstr,"(%s-%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 3:
top--;
sprintf(tempstr,"(%s*%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 4:
top--;
sprintf(tempstr,"(%s/%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
}
}
}
printf("%s\n",stack[0]);
for (i=0;i<EOP;i++) {
free(stack[i]);
}
}
int expandable(int i, int j){
int repeat=0;
int k;
if (j<=NOP) {
repeat=0;
for (k=0;k<=i-1;k++)
if (comp[k]==j) {
return 0;
}
}
int op=0;
int act=0;
for (k=0;k<=i-1;k++) {
if (comp[k]<=NOP)
op++;
else
act++;
if (op<act)
return 0;
}
return 1;
}
void expand(int i) {
int j;
if (i==EOP){
if (validate())
output();
}
else {
for (j=1;j<=NOP+4;j++) {
if (expandable(i+1,j)==1) {
comp[i]=j;
expand(i+1);
}
}
}
}
int main(int argc,char **argv) {
int a;
int i;
for (i=0;i<=(NOP-1);i++) {
scanf("%d",&a);
op[i]=a;
}
expand(0);
}
本帖一共被 1 帖 引用 (帖内工具实现)家园 俺的程序惨不忍睹 忙活了一个星期天，参照highway兄得输出办法，终于把输出解决了，但程序已经惨不忍睹。早知花上一个周末，还不如把逆波兰表达式吃透。不敢再玩了，就先这样吧。这个程序如果没有输出的问题，我认为这个算法还是很不错的。4个数两两相运算，变成3个数，再两两相运算，变成2个数，最后得结果。如果没有输出，适用N个数。
#include<iostream>
#include<vector>
using namespace std;
#define N 4
int z = 0,k1=0,k2=0;
vector<double> Operand(4);
vector<int> Operator(3);
void print(vector<double> A,vector<int> op,int i);
void PRINT(vector<double> A,vector<int> op,int i); // (a#b)#(c#d)
void print_op(int i)
{
switch (i)
{
case 0 : cout<<" + "; break;
case 1 : cout<<" - "; break;
case 2 : cout<<" * "; break;
case 3 : cout<<" / "; break;
case 4 : cout<<" - "; break;
case 5 : cout<<" / "; break;
}
}
inline double operation(const double x,const double y,int i)
{
double res;
switch (i)
{
case 0 : res = x + y; break;
case 1 : res = x - y; break;
case 2 : res = x * y; break;
case 3 : res = x / y; break;
case 4 : res = y - x; break;
case 5 : res = y / x; break;
}
return res;
}
inline void rechnen(vector<double> a,int n)
{
if (n==2) // Rekursion end
{
for (int i=0;i<6;i++)
{
if (operation(a[0],a[1],i)==24.0)
{
z++;
int k3=0; if (i>3) k3++;
Operator[2]=i;
print(Operand,Operator,k1+k2+k3); cout<<endl;
break; // z.B. a+b=24, a#b(b#a)!=24
}
}
}
else
{
vector<double> b(n-1);
for (int u=0;u<n;u++)
{
for (int v=u+1;v<n;v++)
{
if (n==4) { Operand[0]=a[u]; Operand[1]=a[v]; }
if (n==3) { Operand[2]=a[v-u]; Operand[3]=a[3-v+u]; }
// A, B, C, D
for (int i=0,j=1;j<n-1;i++)
{ if (i!=u&&i!=v) b[j++]=a[i]; }
// "n=4" b[1],b[2]
// "n=3" b[1]
for (int i=0;i<6;i++)
{
Operator[4-n]=i;
// op[0], op[1]
b[0]=operation(a[u],a[v],i);
if (i>3) { if (n==4) k1=4; if (n==3) k2=2; }
if (n==3&&u==1)
// (a#b)#(c#d)
{
for (int i=0;i<6;i++)
{
if (operation(b[1],b[0],i)==24.0)
{
z++;
int k3=0; if (i>3) k3++;
Operator[2]=i;
PRINT(Operand,Operator,k1+k2+k3);
cout<<endl; break;
}
}
}
else rechnen(b,n-1);
k2=0;
if (n==4) k1=0;
}
}
}
}
}
int main()
{
while (1)
{
double f; vector<double> a(N);
cout<<"give me "<<N<<" nummer, please:"<<endl;
for (int i=0;i<N&&cin>>f;i++) a[i]=f;
// for (int i=0;i<4;i++) cout<<a[i]<<' ';
rechnen(a,N);
cout<<"\nso there are "<<z<<" kinds of ideas.\n\n";
}
return 0;
}
- 复 俺的程序惨不忍睹
家园 看了N遍 计算部分大略看明白了一些。输出部分仍没有头绪。
先说一个小的地方，rechnen（）是递归调用，为何定义成inline?
不知道你有没有测试过N<>4的时候的情况，我觉得可能不work,起码输出函数似乎已经定死所有的表达式型了。
- 复 看了N遍
家园 是的，就是输出搞不定 早知老兄要看得这么仔细，我就多写些注解了，实在对不住。我认为这个算法还过得去，去掉了交换律的冗余，1 2 3 4 5 6 这六个数只有82001个可能（当然其中还有冗余）。
就是因为输出问题搞不定，俺才拖了这么久才贴上来请教。inline 是因为原来写的递归很慢，我一厢情愿的认为加入inline好像能快点，忘了擦去，见笑了。inline的作用是否老兄再给个俺上个小灶？
没办法，我把4个数定为abcd，k1表示4个数时任意前俩个数运算时换了位；然后b[]用来存储3个数，k2表示3个数时任意前俩个数运算时换了位；k3表示2个数时运算时换了位。
对了，有什么好方法定义b[n-1]? 如果有，就不用vector这个蒙人的东东啦。
明天考试，先请教这么多啦。唉，为了上学，浪费了我多少学习的时光啊！
#define N 6
int z=0;
inline double operation(const double x,const double y,int i)
{
double res;
switch (i)
{
case 0 : res = x + y; break;
case 1 : res = x - y; break;
case 2 : res = x * y; break;
case 3 : res = x / y; break;
case 4 : res = y - x; break;
case 5 : res = y / x; break;
}
return res;
}
void rechnen(vector<double> a,int n)
{
if (n==2) // rekursion end
{
for (int i=0;i<6;i++)
{
if (operation(a[0],a[1],i)==24.0)
{
z++;
break; // a+b=24, a#b(b#a)!=24
}
}
}
else
{
vector<double> b(n-1);
for (int u=0;u<n;u++)
{
for (int v=u+1;v<n;v++)
{
for (int i=0,j=1;j<n-1;i++)
{ if (i!=u&&i!=v) b[j++]=a[i]; }
// "n=4" b[1],b[2]
// "n=3" b[1]
for (int i=0;i<6;i++)
{
b[0]=operation(a[u],a[v],i);
rechnen(b,n-1);
}
}
}
}
}
int main()
{
while (1)
{
double f; vector<double> a(N);
cout<<"give me "<<N<<" nummer, please:"<<endl;
for (int i=0;i<N&&cin>>f;i++) a[i]=f;
// for (int i=0;i<4;i++) cout<<a[i]<<' ';
rechnen(a,N);
cout<<"\nso there are "<<z<<" kinds of ideas.\n\n";
}
return 0;
}
- 复 俺的程序惨不忍睹
家园 为什么要用double类型，难道32位的整型不够么？另外， print等几个函数可以用const reference传参数，比如print可以申明为：
void print( vector< double > const& A, vector< double > const& op, int i );
家园 整形？ 如泰让兄所说，4/7 要是整形就等于0啊！
标准的写法参照泰让兄的：
fabs(stack[0]-TAGET)<=1e-5
和highway兄的：
private static final double SMALL = 0.0000001d
另外，"vector<T> const& A" 这种声明，呜呜，好像是指针常量，即保证此指针不能指向其它东东；还有就是指向常量的指针了，即保证所指的东东不变；最后就是指针常量指向常量了。 如果对于输出N个数有用还行，没用的话，呜呜，俺反正是晕了！
- 复 整形？
家园 关于使用整型，我忽视了需要存放除法操作的中间结果， 虽然理论上可以把除法操作都给“消掉”。不过那样就把问题搞得太复杂了。
在函数声明中，给形式参数加上引用符（&），比如vector< double > const &，是为了避免在传参时不必要地复制。
加上常数修饰符（const）是让编译器在函数定义里检查出试图修改这个形参的内容的语句。在象print这样的函数里，试图修改向量的内容应该是非法操作。
顺便说一下，如果想要防止某个引用或指针变量被重新赋值，可以这样声明：
T* const t = & someT;注意常数修饰符相对于星号的位置。
不过，这样的用法用于声明函数的形式参数没有实际意义，因为C++调用函数时，传值不传址。
家园 整形是不行的 因为有的解中间结果是非整数。