当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 11 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : [问题]24点算法问题
帖子发表于 : 2008-07-16 18:34 

注册: 2008-01-09 22:41
帖子: 18311
送出感谢: 0 次
接收感谢: 6
突然想玩24点了 :lol:

完了

都不会

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

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

问题就在算法了

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

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

直到24出现

有没有别的办法呢?


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2008-07-16 18:35 

注册: 2008-01-09 22:41
帖子: 18311
送出感谢: 0 次
接收感谢: 6
一个类似的帖子http://www.1-100.org/AspNet/12817.htm


页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2008-07-16 18:43 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
代码:
#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 次

页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2008-07-16 18:50 

注册: 2008-01-09 22:41
帖子: 18311
送出感谢: 0 次
接收感谢: 6
有点子晕

慢慢读代码先

谢谢


页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2008-07-16 19:07 
头像

注册: 2007-05-06 8:19
帖子: 7433
送出感谢: 0 次
接收感谢: 4
算算这个:
5 5 5 1
看成否


页首
 用户资料  
 
6 楼 
 文章标题 :
帖子发表于 : 2008-07-16 19:12 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
(5 * (5 - (1 / 5))) = 24


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2008-07-16 19:21 

注册: 2008-01-09 22:41
帖子: 18311
送出感谢: 0 次
接收感谢: 6
3388呢


页首
 用户资料  
 
8 楼 
 文章标题 :
帖子发表于 : 2008-07-16 19:34 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
(8 / (3 - (8 / 3))) = 24


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
9 楼 
 文章标题 :
帖子发表于 : 2008-07-16 22:02 
头像

注册: 2007-03-15 16:58
帖子: 2796
地址: 湖北武汉
送出感谢: 2
接收感谢: 4
算的不是很容易理解。。。。。


_________________
引用:


页首
 用户资料  
 
10 楼 
 文章标题 :
帖子发表于 : 2008-07-16 22:07 

注册: 2006-09-23 6:27
帖子: 227
地址: 火星
送出感谢: 0 次
接收感谢: 0 次
不是一般的晕,这种算法比较麻烦


_________________
DEFE's BLOG


页首
 用户资料  
 
11 楼 
 文章标题 :
帖子发表于 : 2008-07-16 22:13 
头像

注册: 2007-03-15 16:58
帖子: 2796
地址: 湖北武汉
送出感谢: 2
接收感谢: 4
看看这个,上面那个错误很多。。。。。。


代码:
#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);
}


_________________
引用:


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 11 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:Sogou [Spider] 和 4 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译