主题：【原创】将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 帖 引用 (帖内工具实现)
- 相关回复 上下关系8
🙂【原创】将24进行到底
🙂俺的程序惨不忍睹 面壁 字3335 2007-03-12 16:15:26
🙂看了N遍 泰让 字207 2007-03-13 20:08:18
🙂是的，就是输出搞不定 面壁 字2114 2007-03-14 07:54:43
🙂inline 1 泰让 字364 2007-03-15 06:54:23
😁哈，这下彻底清楚啦！ 牛！ 面壁 字0 2007-03-15 15:27:39
🙂为什么要用double类型，难道32位的整型不够么？另外， 请尽量 字144 2007-03-13 19:39:12
🙂整形？ 面壁 字394 2007-03-14 08:12:51