闲的无聊,做这种比赛练练手。。当时也没注册比赛帐号,纯属打酱油= =
第一题,速算24
给定4个不大于10的正整数(范围1-10),要求在不改变数据先后顺序的情况下,采用加减乘除四种运算,找到一个表达式,使得最后的结果是24。
题目没说清楚,对于括号问题,每一步运算都要+括号。
当时我实现的方法很搓。。应该就是枚举每次进行的操作数位置i,将第i个操作数与第i+1个操作数作运算。然后更新操作数数组。将第i个操作数替换为i op i+1的结果,然后将第i+1以后的操作数前移1位。
具体看代码吧。。
1
# include <stdio.h>
2
# include <math.h>
3
# include <string.h>
4
# define zero(num) (fabs(num)<1e-6)
5
int d[4];
6
void print(int o,int t,int a,int b,int c)
7

{
8
int pos[4]=
{0,2,4,6},i,j;
9
int op[2],opf[2];
10
op[0]=o;
11
op[1]=t;
12
opf[0]=a;
13
opf[1]=b;
14
char ans[100];
15
for(i=0;i<4;i++) ans[pos[i]]=d[i]+48;
16
for(i=1;i<=5;i+=2) ans[i]=' ';
17
ans[7]='\0';
18
for(j=0;j<=1;j++)
19
{
20
for(i=strlen(ans)+1;i>pos[op[j]];i--) ans[i]=ans[i-1];
21
ans[pos[op[j]]]='(';
22
for(i=op[j];i<4-j;i++) pos[i]++;
23
for(i=strlen(ans)+1;i>pos[op[j]+1]+1;i--) ans[i]=ans[i-1];
24
ans[pos[op[j]+1]+1]=')';
25
for(i=op[j]+2;i<4-j;i++) pos[i]++;
26
for(i=pos[op[j]];ans[i]!=' ';i++);
27
switch(opf[j])
28
{
29
case 1:ans[i]='+';break;
30
case 2:ans[i]='-';break;
31
case 3:ans[i]='*';break;
32
case 4:ans[i]='/';break;
33
};
34
for(i=op[j];i<3-j;i++) pos[i]=pos[i+1];
35
}
36
for(i=pos[0];ans[i]!=' ';i++);
37
switch(c)
38
{
39
case 1:ans[i]='+';break;
40
case 2:ans[i]='-';break;
41
case 3:ans[i]='*';break;
42
case 4:ans[i]='/';break;
43
};
44
printf("%s\n",ans);
45
}
46
int main()
47

{
48
49
double t[5],t1[5];
50
int i,j,k,l,tmp;
51
for(i=0;i<4;i++)
52
scanf("%d",d+i);
53
for(i=0;i<3;i++)
54
{
55
for(j=0;j<2;j++)
56
{
57
for(k=1;k<=4;k++)
58
{
59
if(k==4&&d[i+1]==0) break;
60
for(tmp=0;tmp<i;tmp++) t[tmp]=d[tmp];
61
switch(k)
62
{
63
case 1:t[i]=d[i]+d[i+1];break;
64
case 2:t[i]=d[i]-d[i+1];break;
65
case 3:t[i]=d[i]*d[i+1];break;
66
case 4:t[i]=d[i]/(double)d[i+1];break;
67
};
68
for(tmp=i+2;tmp<4;tmp++) t[tmp-1]=d[tmp];
69
for(l=1;l<=4;l++)
70
{
71
if(l==4&&zero(t[j+1])) goto end;
72
for(tmp=0;tmp<j;tmp++) t1[tmp]=t[tmp];
73
switch(l)
74
{
75
case 1:t1[j]=t[j]+t[j+1];break;
76
case 2:t1[j]=t[j]-t[j+1];break;
77
case 3:t1[j]=t[j]*t[j+1];break;
78
case 4:t1[j]=t[j]/(double)t[j+1];break;
79
};
80
for(tmp=j+2;tmp<3;tmp++) t1[tmp-1]=t[tmp];
81
for(tmp=1;tmp<=4;tmp++)
82
switch(tmp)
83
{
84
case 1:
85
if(zero(t1[0]+t1[1]-24))
86
{
87
print(i,j,k,l,tmp);
88
goto success;
89
}
90
break;
91
case 2:
92
if(zero(t1[0]-t1[1]-24))
93
{
94
print(i,j,k,l,tmp);
95
goto success;
96
}
97
break;
98
case 3:
99
if(zero(t1[0]*t1[1]-24))
100
{
101
print(i,j,k,l,tmp);
102
goto success;
103
}
104
break;
105
case 4:
106
if(!zero(t1[1])&&zero(t1[0]/t1[1]-24))
107
{
108
print(i,j,k,l,tmp);
109
goto success;
110
}
111
break;
112
};
113
}
114
}
115
end:;
116
}
117
}
118
success:
119
return 0;
120
121
}
122
第二题:迷宫问题,经典BFS,不解释。。直接代码了。。
1
#include<stdio.h>
2
int map[5][5];
3
int q[100][2],s=-1,e=-1;
4
int pre[5][5][2];
5
# define legal(a,b) ((a)>=0&&(a)<5&&(b)>=0&&(b)<5&&map[(a)][(b)]==-1)
6
void print(int r,int c)
7

{
8
if(r==0&&c==0)
9
printf("(%d, %d)\n",r,c);
10
else
11
{
12
print(pre[r][c][0],pre[r][c][1]);
13
printf("(%d, %d)\n",r,c);
14
}
15
}
16
int main()
17

{
18
int i,j;
19
for(i=0;i<5;i++)
20
for(j=0;j<5;j++)
21
{
22
scanf("%d",&map[i][j]);
23
if(map[i][j]==1) map[i][j]=-2;
24
else map[i][j]=-1;
25
}
26
q[++e][0]=0;
27
q[e][1]=0;
28
map[0][0]=0;
29
while(s!=e)
30
{
31
int r=q[++s][0],c=q[s][1];
32
if(legal(r+1,c))
33
{
34
q[++e][0]=r+1;
35
q[e][1]=c;
36
map[q[e][0]][q[e][1]]=map[r][c]+1;
37
pre[q[e][0]][q[e][1]][0]=r;
38
pre[q[e][0]][q[e][1]][1]=c;
39
}
40
if(legal(r-1,c))
41
{
42
q[++e][0]=r-1;
43
q[e][1]=c;
44
map[q[e][0]][q[e][1]]=map[r][c]+1;
45
pre[q[e][0]][q[e][1]][0]=r;
46
pre[q[e][0]][q[e][1]][1]=c;
47
}
48
if(legal(r,c+1))
49
{
50
q[++e][0]=r;
51
q[e][1]=c+1;
52
map[q[e][0]][q[e][1]]=map[r][c]+1;
53
pre[q[e][0]][q[e][1]][0]=r;
54
pre[q[e][0]][q[e][1]][1]=c;
55
}
56
if(legal(r,c-1))
57
{
58
q[++e][0]=r;
59
q[e][1]=c-1;
60
map[q[e][0]][q[e][1]]=map[r][c]+1;
61
pre[q[e][0]][q[e][1]][0]=r;
62
pre[q[e][0]][q[e][1]][1]=c;
63
}
64
}
65
print(4,4);
66
return 0;
67
68
}
69