一、简介
本程序的思想和算法来自于C语言教材后的实训项目，程序通过用户输入四个整数计算出能够通过加减乘除得到数字24的所有表达式，程序的设计有别于一般通过穷举实现的方式，效率得到提高。算法介绍如下：
如用户输入1,2,3,4四个数字，先将其看成四个集合即{1}，{2}，{3}，{4}，整个叫做第一集群，后通过任意两个集合加减乘除{1,2}，{1,3}，{1,4}，{2,3}，{2,4}，{3,4}六个集合叫做第二集群，而第三集群由第一集群和第二集群产生，而第四集群可由第一集群和第三集群以及由第二集群自身产生，最后比较第四集群所得到的的值是否24，输出结果
二、程序流程如下：
程序调用input函数处理用户输入，并同时生成四个相应的集合
调用函数calc，通过其中的list_cross函数产生第二、三、四集群
调用含税output输出，并同时删除相同的表达式
删除所有集群所占的空间，程序结束
三、主要的数据结构以及算法
为了提高计算精度，使用分数表示每一次计算结果
分数的结构 FRACTION
typedef struct{int num;//分子
int den;//分母
}FRACTION; //注意分数的符号放在分子上
集群链表节点 s_ item
1 typedef char EXPRESS[40]; //存储具体的表达式，如2*3
2 typedef structs_item{3 FRACTION value; //集合的值 如expr为2*3，value.num=6,value.den=1
4 EXPRESS expr; //表达式
5 int flag[4]; //每一个元素代表是否使用相应的数字，如用户输入了1,2,3,4，flag{1,1,0,0}，表示
6 //集合含有数字1和2
7 struct s_item* next; //指向下一节点
8 }ITEM,*PITEM;
主要的算法
分数的四则运算：
1.声明
int commonDivisor(int a,int b);//最大公约数
int commonMultiple(int a,int b);//最小公倍数//公倍数和公约数用于化简和计算分数
FRACTION plus(FRACTION a,FRACTION b);//分数的加法
FRACTION sub(FRACTION a,FRACTION b);//分数的减法
FRACTION multiple(FRACTION a,FRACTION b);//分数乘法
FRACTION division(FRACTION a,FRACTION b);//分数的除法
2.定义
1 //最大公约数
2 int commonDivisor(int a,intb){3 int temp=0;4 while(b!=0){5 temp=a%b;6 a=b;7 b=temp;8 }9 returna;10 }11
12 //最小公倍数
13 int commonMultiple(int a,intb){14 return a*b/commonDivisor(a,b);15 }16
17
18 //分数的加法
19 FRACTION plus(FRACTION a,FRACTION b){20
21 if(a.den==b.den){ //分母相同
22
23 a.num=a.num+b.num;24 }else{25 int cm=commonMultiple(a.den,b.den);26 a.num=a.num*(cm/a.den)+b.num*(cm/b.den);27 a.den=cm;28 }29
30 //简化a,分子分母同除公约数
31 int cm=commonDivisor(abs(a.num),a.den);32 a.num/=cm;33 a.den/=cm;34
35 returna;36 }37
38 //分数减法
39 FRACTION sub(FRACTION a,FRACTION b){40
41 if(a.den==b.den){ //分母相同
42
43 a.num=a.num-b.num;44 }else{45 int cm=commonMultiple(a.den,b.den);46 a.num=a.num*(cm/a.den)-b.num*(cm/b.den);47 a.den=cm;48 }49 //简化a,分子分母同除公约数
50 int cm=commonDivisor(abs(a.num),a.den);51 a.num/=cm;52 a.den/=cm;53
54 returna;55 }56
57 //分数乘法
58 FRACTION multiple(FRACTION a,FRACTION b){59
60 a.num*=b.num;61 a.den*=b.den;62
63 int cm=commonDivisor(abs(a.num),a.den);64 a.num/=cm;65 a.den/=cm;66
67 returna;68 }69
70
71 //分数的除法
72 FRACTION division(FRACTION a,FRACTION b){73 inttemp;74 if(b.num==0){75 a.num=0;76 a.den=0;77 return a;//不能除0 ，返回分子，分母为0，作为标志
78 }else if(b.num>0){79 temp=b.num;80 b.num=b.den;81 b.den=temp;82 }else{83 temp =abs(b.num);84 b.num=b.den;85 b.den=temp;86 b.num*=-1;87 }88 returnmultiple(a,b);89 }
集合之间的加减乘除产生新集合
1.声明
PITEM add(PITEM a,PITEM b); //两个相加
PITEM divide(PITEM a,PITEM b); //两个相除
PITEM mutiply(PITEM a,PITEM b); //两个相乘
PITEM subtract(PITEM a,PITEM b); //两个相减
2.定义
1 PITEM add(PITEM a,PITEM b) //两个相加
2 {3
4 PITEM x=(struct s_item*)malloc(sizeof(structs_item));5 x->value=plus(a->value,b->value);6
7 intm;8 for(m=0;m<4;m++){9 x->flag[m]=0;10 }11
12
13 int k=0;14 x->expr[k]=‘(‘;15 intj;16 for(j=0;a->expr[j]!=‘\0‘;j++){17 x->expr[++k]=a->expr[j];18 }19 x->expr[++k]=‘+‘;20 for(j=0;b->expr[j]!=‘\0‘;j++){21 x->expr[++k]=b->expr[j];22 }23 x->expr[++k]=‘)‘;24 x->expr[++k]=‘\0‘;25
26
27 int i=0;28 for(i=0;i<4;i++){29 if(a->flag[i]==1){30 x->flag[i]=1;31 }32
33 if(b->flag[i]==1){34 x->flag[i]=1;35 }36
37
38 }39
40 x->next=NULL;41
42 returnx;43 }44
45
46 PITEM divide(PITEM a,PITEM b){ //集合相除
47 PITEM x=(struct s_item*)malloc(sizeof(structs_item));48 x->value=division(a->value,b->value);49
50 intm;51 for(m=0;m<4;m++){52 x->flag[m]=0;53 }54 if(x->value.num==0&&x->value.den==0){55 free(x);56 returnNULL;57 }58
59 int k=0;60 x->expr[k]=‘(‘;61 intj;62 for(j=0;a->expr[j]!=‘\0‘;j++){63 x->expr[++k]=a->expr[j];64 }65 x->expr[++k]=‘/‘;66 for(j=0;b->expr[j]!=‘\0‘;j++){67 x->expr[++k]=b->expr[j];68 }69 x->expr[++k]=‘)‘;70 x->expr[++k]=‘\0‘;71
72 int i=0;73 for(i=0;i<4;i++){74 if(a->flag[i]==1){75 x->flag[i]=1;76 }77
78 if(b->flag[i]==1){79 x->flag[i]=1;80 }81
82
83 }84
85 x->next=NULL;86 returnx;87 }88 PITEM mutiply(PITEM a,PITEM b)//两个相乘
89 {90 PITEM x=(struct s_item*)malloc(sizeof(structs_item));91 x->value=multiple(a->value,b->value);92 intm;93 for(m=0;m<4;m++){94 x->flag[m]=0;95 }96 int k=0;97 x->expr[k]=‘(‘;98 intj;99 for(j=0;a->expr[j]!=‘\0‘;j++){100 x->expr[++k]=a->expr[j];101 }102 x->expr[++k]=‘*‘;103 for(j=0;b->expr[j]!=‘\0‘;j++){104 x->expr[++k]=b->expr[j];105 }106 x->expr[++k]=‘)‘;107 x->expr[++k]=‘\0‘;108
109 int i=0;110 for(i=0;i<4;i++){111 if(a->flag[i]==1){112 x->flag[i]=1;113 }114
115 if(b->flag[i]==1){116 x->flag[i]=1;117 }118
119
120 }121
122 x->next=NULL;123 returnx;124 }125
126
127 PITEM subtract(PITEM a,PITEM b){ //相减
128 PITEM x=(struct s_item*)malloc(sizeof(structs_item));129 x->value=sub(a->value,b->value);130 intm;131 for(m=0;m<4;m++){132 x->flag[m]=0;133 }134 int k=0;135 x->expr[k]=‘(‘;136 intj;137 for(j=0;a->expr[j]!=‘\0‘;j++){138 x->expr[++k]=a->expr[j];139 }140 x->expr[++k]=‘-‘;141 for(j=0;b->expr[j]!=‘\0‘;j++){142 x->expr[++k]=b->expr[j];143 }144 x->expr[++k]=‘)‘;145 x->expr[++k]=‘\0‘;146
147 int i=0;148 for(i=0;i<4;i++){149 if(a->flag[i]==1){150 x->flag[i]=1;151 }152
153 if(b->flag[i]==1){154 x->flag[i]=1;155 }156
157
158 }159
160 x->next=NULL;161 returnx;162 }
View Code
核心代码
产生新集群 list_cross
1 //比较集群之间是否有相同数字
2 intcmp(PITEM left,PITEM right){3 inti;4 for(i=0;i<4;i++){5 if(left->flag[i]==1&&right->flag[i]==1){6 return 1;7 }8 }9 return 0;10 }11
12 //结合两个集群产生下一个集群
13 voidlist_cross(PITEM left,PITEM right,PITEM result){14
15 PITEM p,q;16 for(p=left->next;p!=NULL;p=p->next){ //循环调用两个集群中所有集合
17 for(q=right->next;q!=NULL;q=q->next)18 if(cmp(p,q)==0){ //只有两集合不含相同数字才运算
19 PITEM temp=NULL;20 if((temp=add(p,q))!=NULL){21 temp->next=result->next;22 result->next=temp;23 }24 if((temp=subtract(p,q))!=NULL){25 temp->next=result->next;26 result->next=temp;27 }28 if((temp=divide(p,q))!=NULL){29 temp->next=result->next;30 result->next=temp;31 }32 if((temp=mutiply(p,q))!=NULL){33 temp->next=result->next;34 result->next=temp;35 }36
37 }38 }39 }
因为用户有可能输入相同的数字，所以要消除相同的表达式：
消除重复表达式
1 PITEM p=p4_head->next; //p指向第四集群的头结点，第四集群即最后四个数字都已经使用的集合2
3 //消除重复的表达式
4
5 PITEM q,pre;6 for(;p!=NULL;p=p->next){7 for(q=p->next,pre=p;q!=NULL;){8 if(strcmp(p->expr,q->expr)==0){9
10 pre->next=q->next;11 PITEM temp=q; //pre为p的前一个节点
12 q=q->next;13
14 free(temp);//消失重复点;
15 temp=NULL;16
17 }else{18 q=q->next;19 pre=pre->next;20 }21 }22 }
判断集合的值，输出结果
//输出
p=p4_head->next;while(p!=NULL){if(p->value.num==24&&p->value.den==1){
puts(p->expr);
}
p=p->next;
}
四、运行
