[问题]24点算法问题

系统安装、升级讨论
版面规则
我们都知道新人的确很菜，也喜欢抱怨，并且带有浓厚的Windows习惯，但既然在这里询问，我们就应该有责任帮助他们解决问题，而不是直接泼冷水、简单的否定或发表对解决问题没有任何帮助的帖子。乐于分享，以人为本，这正是Ubuntu的精神所在。
回复
delectate
帖子： 18311
注册时间： 2008-01-09 22:41

[问题]24点算法问题

#1

帖子 由 delectate » 2008-07-16 18:34

突然想玩24点了 :lol:

完了

都不会

想偷懒，让计算机算，我输出答案，有点 :oops:

然后呢，一直想算法，什么语言不重要，算法最重要 :roll:

问题就在算法了

四个数字，但是算法要穷举

也就是说把四个数字放到各种式子里边穷举

直到24出现

有没有别的办法呢？
页首
delectate
帖子： 18311
注册时间： 2008-01-09 22:41

#2

帖子 由 delectate » 2008-07-16 18:35

一个类似的帖子http://www.1-100.org/AspNet/12817.htm
页首
头像
BigSnake.NET
帖子： 12522
注册时间： 2006-07-02 11:16
来自： 廣州
联系：
联系 BigSnake.NET

#3

帖子 由 BigSnake.NET » 2008-07-16 18:43

代码： 全选

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
        int sub1,sub2;
        char op;
        double v;
        unsigned int mask;
} NODE;
#define A_SIZE 100000U

/*
 * initalize the array, and read the 4 numbers
 */
NODE * initalize(void) {
        NODE * const A = (NODE *)calloc(A_SIZE, sizeof(NODE));
        if (NULL==A) {
                printf("CAN NOT ALLOCATE MEMORY!\n");
                exit(-1);
        }
        int i=0;
        for (i=0;i<4;++i) {
                A[i].v=0;
                A[i].mask=0x1<<i;
                A[i].sub1=-1;
                A[i].sub2=-1;
                A[i].op='\0';
        }
        return A;
}

void readdata(NODE A[]) {
        int n=0;
        while (4 != n) {
                printf("Input 4 numbers, separated by spaces:\n");
                n = scanf("%lf %lf %lf %lf",&A[0].v, &A[1].v, &A[2].v, &A[3].v);
                if (feof(stdin)) exit(0);
                while ('\n' != getchar());
        }
}

/* 
 * make a new node with sub1 and sub2
 */
int mkNode(NODE A[], int sub1, int sub2, int dst, char op) {
        if (('/'==op) && (fabs(A[sub2].v)<1e-8)) {
                return -1;
        }
        A[dst].mask = A[sub1].mask | A[sub2].mask;
        A[dst].op = op;
        A[dst].sub1 = sub1;
        A[dst].sub2 = sub2;
        switch (op) {
                case '+':
                        A[dst].v = A[sub1].v + A[sub2].v;
                        break;
                case '*':
                        A[dst].v = A[sub1].v * A[sub2].v;
                        break;
                case '-':
                        A[dst].v = A[sub1].v - A[sub2].v;
                        break;
                case '/':
                        A[dst].v = A[sub1].v / A[sub2].v;
                        break;
        }
        return 0;
}

/*
 * print the answer in a human readable format
 */
void writeout(NODE A[], int node) {
        if ('\0'==A[node].op) {
                if (fabs(A[node].v-rint(A[node].v)) < 1e-8) {
                        printf("%d",(int)rint(A[node].v));
                } else {
                        printf("%lf",A[node].v);
                }
                return;
        }
        printf("(");
        writeout(A,A[node].sub1);
        printf(" %c ",A[node].op);
        writeout(A,A[node].sub2);
        printf(")");
        return;
}

int main(void) {
        NODE * const A = initalize();
        int counter = 1;
        while (!feof(stdin)) {
                printf("CASE %d\n",counter);
                ++counter;
                readdata(A);
                int ph=1,pt=4;
                int i;
                /* BFS */
                while (ph<pt) {
                        for (i=0;i<ph;++i) {
                                if (0==(A[i].mask & A[ph].mask)) {
                                        mkNode(A,i,ph,pt,'+');
                                        pt++;
                                        mkNode(A,i,ph,pt,'*');
                                        pt++;
                                        mkNode(A,i,ph,pt,'-');
                                        pt++;
                                        mkNode(A,ph,i,pt,'-');
                                        pt++;
                                        if (0 == mkNode(A,i,ph,pt,'/')) {
                                                pt++;
                                        }
                                        if (0 == mkNode(A,ph,i,pt,'/')) {
                                                pt++;
                                        }
                                }
                                if (pt > (A_SIZE-6)) {
                                        printf("TOO MANY RESULT!\n");
                                        return -1;
                                }
                        }
                        ++ph;
                }
                int n=0;
                for (i=0;i<pt;++i){
                        if ((0xF == A[i].mask) && (fabs(A[i].v-24.0) < 1e-8)) {
                                writeout(A,i);
                                printf(" = 24\n");
                                ++n;
                        }
                }
                if (n) {
                        printf("%d solutions found.\n",n);
                } else {
                        printf("No solution found.\n");
                }
        }
        free(A);
        return 0;
}
广度优先搜索
上次由 BigSnake.NET 在 2008-07-16 18:57，总共编辑 2 次。
^_^ ~~~
要理解递归，首先要理解递归。

地球人都知道，理论上，理论跟实际是没有差别的，但实际上，理论跟实际的差别是相当大滴。
页首
delectate
帖子： 18311
注册时间： 2008-01-09 22:41

#4

帖子 由 delectate » 2008-07-16 18:50

有点子晕

慢慢读代码先

谢谢
页首
头像
冲浪板
论坛版主
帖子： 7513
注册时间： 2007-05-06 8:19

#5

帖子 由 冲浪板 » 2008-07-16 19:07

算算这个:
5 5 5 1
看成否
页首
头像
BigSnake.NET
帖子： 12522
注册时间： 2006-07-02 11:16
来自： 廣州
联系：
联系 BigSnake.NET

#6

帖子 由 BigSnake.NET » 2008-07-16 19:12

(5 * (5 - (1 / 5))) = 24
^_^ ~~~
要理解递归，首先要理解递归。

地球人都知道，理论上，理论跟实际是没有差别的，但实际上，理论跟实际的差别是相当大滴。
页首
delectate
帖子： 18311
注册时间： 2008-01-09 22:41

#7

帖子 由 delectate » 2008-07-16 19:21

3388呢
页首
头像
BigSnake.NET
帖子： 12522
注册时间： 2006-07-02 11:16
来自： 廣州
联系：
联系 BigSnake.NET

#8

帖子 由 BigSnake.NET » 2008-07-16 19:34

(8 / (3 - (8 / 3))) = 24
^_^ ~~~
要理解递归，首先要理解递归。

地球人都知道，理论上，理论跟实际是没有差别的，但实际上，理论跟实际的差别是相当大滴。
页首
头像
lhw828
帖子： 2797
注册时间： 2007-03-15 16:58
来自： 湖北武汉
联系：
联系 lhw828

#9

帖子 由 lhw828 » 2008-07-16 22:02

算的不是很容易理解。。。。。
页首
sanebaby
帖子： 227
注册时间： 2006-09-23 6:27
来自： 火星
联系：
联系 sanebaby

#10

帖子 由 sanebaby » 2008-07-16 22:07

不是一般的晕，这种算法比较麻烦
页首
头像
lhw828
帖子： 2797
注册时间： 2007-03-15 16:58
来自： 湖北武汉
联系：
联系 lhw828

#11

帖子 由 lhw828 » 2008-07-16 22:13

看看这个，上面那个错误很多。。。。。。

代码： 全选

#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <stdlib.h>
#define V 64422
#define W 0.000001
double ys(double n1, double n2, int fh) {
if (fh == 0) {
return(n1+n2);
} else if (fh == 1) {
return(n1-n2);
} else if (fh == 2) {
return(n1*n2);
} else if (n2 != 0 && fh == 3) {
return(n1/n2);
}
return V;
}
char dq(int fh) {
if (fh == 0) {
return '+';
} else if (fh == 1) {
return '-';
} else if (fh == 2) {
return '*';
} else if (fh == 3) {
return '/';
}
}
int* str(int n) {
int arr[4] = {1, 1, 1, 1};
int i;
int *s;
int a=(n-1)/6,b,c,d;
s=(int*)malloc(sizeof(int)*4);
n++;
arr[a] = 0;
b = (n%6)/2;
if (b>=a) {
b++;
}
arr[b] = 0;
if (n%2 == 1) {
for (i=3; i>=0; i--) {
if (arr[i] == 1) {
c = i;
d = 6-a-b-c;
}
}
s[0]=a;
s[1]=b;
s[2]=c;
s[3]=d;
return s;
}
for (i=0; i<4; i++) {
if (arr[i] == 1) {
c = i;
d = 6-a-b-c;
}
}
s[0]=a;
s[1]=b;
s[2]=c;
s[3]=d;
return s;
}
void jsgc(double arr[], int jg){
int arri[4];
int i,j,x,y,z;
double **ysbl;
int *ysf1;
int *ysf2;
int *ysf3;
double *ys1;
double *ys2;
double *ys3;
double *ys4;
double num = 0;
int *s;
s=(int*)malloc(sizeof(int)*4);
ysbl=(double**)malloc(sizeof(double)*64*jg);
ysf1=(int*)malloc(sizeof(int)*64*jg);
ysf2=(int*)malloc(sizeof(int)*64*jg);
ysf3=(int*)malloc(sizeof(int)*64*jg);
ys1=(double*)malloc(sizeof(double)*64*jg);
ys2=(double*)malloc(sizeof(double)*64*jg);
ys3=(double*)malloc(sizeof(double)*64*jg);
ys4=(double*)malloc(sizeof(double)*64*jg);
for (j=0; j<64*jg; j++) {
ysbl[j] = (double*)malloc(sizeof(ysbl)*5);
}
for (j=0; j<jg; j++) {
s = str(j);
for (x=0; x<4; x++) {
arri[s[x]] = x;
}
for (x=0; x<4; x++) {
for (y=0; y<4; y++) {
for (z=0; z<4; z++) {
ysbl[j*64+x*16+y*4+z][0] = ys(ys(ys(arr[arri[0]], arr[arri[1]], x), arr[arri[2]], y), arr[arri[3]], z);
ysbl[j*64+x*16+y*4+z][1] = ys(ys(arr[arri[0]], arr[arri[1]], x), ys(arr[arri[2]], arr[arri[3]], z), y);
ysbl[j*64+x*16+y*4+z][2] = ys(ys(arr[arri[0]], ys(arr[arri[1]], arr[arri[2]], y), x), arr[arri[3]], z);
ysbl[j*64+x*16+y*4+z][3] = ys(arr[arri[0]], ys(ys(arr[arri[1]], arr[arri[2]], y), arr[arri[3]], z), x);
ysbl[j*64+x*16+y*4+z][4] = ys(arr[arri[0]], ys(arr[arri[1]], ys(arr[arri[2]], arr[arri[3]], z), y), x);
ysf1[j*64+x*16+y*4+z] = x;
ysf2[j*64+x*16+y*4+z] = y;
ysf3[j*64+x*16+y*4+z] = z;
ys1[j*64+x*16+y*4+z] = arr[arri[0]];
ys2[j*64+x*16+y*4+z] = arr[arri[1]];
ys3[j*64+x*16+y*4+z] = arr[arri[2]];
ys4[j*64+x*16+y*4+z] = arr[arri[3]];
}
}
}
}
for (i=0; i<jg*64; i++) {
if ((double)ysbl[i][0]>(double)jg-W&&(double)ysbl[i][0]<(double)jg+W) {
num++;
printf("((%lf%c%lf)%c%lf)%c%lf\n",ys1[i],dq(ysf1[i]),ys2[i],dq(ysf2[i]),ys3[i],dq(ysf3[i]),ys4[i]);
}
if ((double)ysbl[i][1]>(double)jg-W&&(double)ysbl[i][1]<(double)jg+W) {
num++;
printf("(%lf%c%lf)%c(%lf%c%lf)\n",ys1[i],dq(ysf1[i]),ys2[i],dq(ysf2[i]),ys3[i],dq(ysf3[i]),ys4[i]);
}
if ((double)ysbl[i][2]>(double)jg-W&&(double)ysbl[i][2]<(double)jg+W) {
num++;
printf("(%lf%c(%lf%c%lf))%c%lf\n",ys1[i],dq(ysf1[i]),ys2[i],dq(ysf2[i]),ys3[i],dq(ysf3[i]),ys4[i]);
}
if ((double)ysbl[i][3]>(double)jg-W&&(double)ysbl[i][3]<(double)jg+W) {
num++;
printf("%lf%c((%lf%c%lf)%c%lf)\n",ys1[i],dq(ysf1[i]),ys2[i],dq(ysf2[i]),ys3[i],dq(ysf3[i]),ys4[i]);
}
if ((double)ysbl[i][4]>(double)jg-W&&(double)ysbl[i][4]<(double)jg+W) {
num++;
printf("%lf%c(%lf%c(%lf%c%lf))\n",ys1[i],dq(ysf1[i]),ys2[i],dq(ysf2[i]),ys3[i],dq(ysf3[i]),ys4[i]);
}
}
if(num==0)printf("无答案\n");
else printf("共有%lf种方法\n",num);
}
void main(){
double arr[4];
printf("请输入4个小于14的数,数与数之间用空格分开:");
scanf("%lf%lf%lf%lf",&arr[0],&arr[1],&arr[2],&arr[3]);
jsgc(arr,24);
}
页首
回复

回到 “系统安装和升级”